American Physical Society Sites|APS|Journals|PhysicsCentral|Physics

Session S28: Quantum Annealing: Algorithms & Applications

11:15 AM–2:15 PM, Thursday, March 8, 2018
LACC Room: 405

Sponsoring Unit: DQI
Chair: Davide Venturelli, NASA/Ames Res Ctr

Abstract: S28.00007 : A deceptive step towards quantum speedup detection*

12:51 PM–1:03 PM

    Abstract  

Presenter:

Salvatore Mandra
(Quantum Artificial Intelligence Lab (QuAIL), NASA/Ames Res Ctr - SGT)

Authors:

Salvatore Mandra
(Quantum Artificial Intelligence Lab (QuAIL), NASA/Ames Res Ctr - SGT)

Helmut Katzgraber
(Texas A&M Univ)

There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing machines. To date, classical heuristics have consistently outperformed quantum-annealing based approaches. Here we introduce a class of problems based on frustrated cluster loops — deceptive cluster loops — for which all currently known state-of-the-art classical heuristics are outperformed by the DW2000Q quantum annealing machine. While there is a sizable constant speedup over all known classical heuristics, a noticeable improvement in the scaling remains elusive. These results represent the first steps towards a detection of potential quantum speedup, albeit without a scaling improvement and for synthetic benchmark problems.

*H. G. K. acknowledges support from the National Science Foundation (Grant No. DMR-1151387). This research is based upon work supported by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via Interagency Umbrella Agreement IA1-1198.