Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Abstract
The observation of an unequivocal quantum speedup remains an elusive objective for quantum computing. A more modest goal is to demonstrate a scaling advantage over a class of classical algorithms for a computational problem running on quantum hardware. The D-Wave quantum annealing processors have been at the forefront of experimental attempts to address this goal, given their relatively large numbers of qubits and programmability. A complete determination of the optimal time-to-solution using these processors has not been possible to date, preventing definitive conclusions about the presence of a scaling advantage. The main technical obstacle has been the inability to verify an optimal annealing time within the available range. Here, we overcome this obstacle using a class of problem instances constructed by systematically combining many spin frustrated loops with few-qubit gadgets exhibiting a tunneling event a combination that we find to promote the presence of tunneling energy barriers in the relevant semiclassical energy landscape of the full problem and we observe an optimal annealing time using a D-Wave 2000Qprocessor over a range spanning up to more than 2000 qubits. We identify the gadgets as being responsible for the optimal annealing time, whose existence allows us to perform an optimal time-to-solution benchmarking analysis. We perform a comparison to several classical algorithms, including simulated annealing, spin-vector Monte Carlo, and discrete-time simulated quantum annealing (SQA), and establish the first example of a scaling advantage for an experimental quantum annealer over classical simulated annealing. Namely, we find that the D-Wave device exhibits certifiably better scaling than simulated annealing, with 95 confidence, over the range of problem sizes that we can test.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 19, 2018
- Accession Number
- AD1092051
Entities
People
- Daniel A. Lidar
- Tameem Albash
Organizations
- University of Southern California