The pitfalls of planar spin-glass benchmarks: raising the bar for quantum annealers (again)

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 ann...

Full description

Saved in:
Bibliographic Details
Published in:Quantum science and technology 2017-09, Vol.2 (3), p.38501
Main Authors: Mandrà, Salvatore, Katzgraber, Helmut G, Thomas, Creighton
Format: Article
Language:English
Subjects:
benchmarking
exact algorithms
P versus NP
quantum annealing
spin glasses
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2058-9565
2058-9565
DOI:10.1088/2058-9565/aa7877