The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again). (21st July 2017)

• Record Type: Journal Article
• Authors: Mandrà, Salvatore; Katzgraber, Helmut G; Thomas, Creighton
• Is Part Of: Quantum science and technology. Volume 2:Number 3(2017)
• Publication Date: 2017-07-21
• Subjects: quantum annealing -- spin glasses -- P versus NP -- exact algorithms -- benchmarking; 75.50.Lk -- 75.40.Mg -- 05.50.+q -- 03.67.Lx; Quantum theory -- Periodicals; Quantum theory; Periodicals; 530
• DOI: 10.1088/2058-9565/aa7877
• Languages: English
• ISSNs: 2058-9565

Abstract

Abstract: In an effort to overcome the limitations of random spin-glass benchmarks for quantum annealers, focus has shifted to carefully crafted gadget-based problems whose logical structure typically has a planar topology. Recent experiments on these gadget problems using a commercially available quantum annealer have demonstrated an impressive performance over a selection of commonly used classical optimisation heuristics. Here, we show that efficient classical optimisation techniques, such as minimum-weight-perfect matching, can solve these gadget problems exactly and in polynomial time. We present approaches on how to mitigate this shortcoming of commonly used benchmark problems based on planar logical topologies.