A deceptive step towards quantum speedup detection

作者：Mandra Salvatore^*; Katzgraber Helmut G

来源：Quantum Science and Technology, 2018, 3(4): UNSP 04LT01.

DOI：10.1088/2058-9565/aac8b2

• quantum annealing
• quantum optimization
• benchmark

There have been multiple attempts to design synthetic benchmark problems with the goal of detecting quantum speedup in current quantum annealing (QA) 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 QA 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.

• 出版日期2018-10