Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
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 be...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2018-07-01
|
| Series: | Physical Review X |
| Online Access: | http://doi.org/10.1103/PhysRevX.8.031016 |
| _version_ | 1819141062334087168 |
|---|---|
| author | Tameem Albash Daniel A. Lidar |
| author_facet | Tameem Albash Daniel A. Lidar |
| author_sort | Tameem Albash |
| collection | DOAJ |
| description | 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 2000Q processor 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. However, we do not find evidence for a quantum speedup: SQA exhibits the best scaling for annealing algorithms by a significant margin. This is a finding of independent interest, since we associate SQA’s advantage with its ability to transverse energy barriers in the semiclassical energy landscape by mimicking tunneling. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes based on a similar principle of promoting the presence of energy barriers that can be overcome more efficiently using quantum rather than thermal fluctuations, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices. |
| first_indexed | 2024-12-22T11:48:29Z |
| format | Article |
| id | doaj.art-cf69ce1050a745f1a975fe64b5c53ae5 |
| institution | Directory Open Access Journal |
| issn | 2160-3308 |
| language | English |
| last_indexed | 2024-12-22T11:48:29Z |
| publishDate | 2018-07-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review X |
| spelling | doaj.art-cf69ce1050a745f1a975fe64b5c53ae52022-12-21T18:27:05ZengAmerican Physical SocietyPhysical Review X2160-33082018-07-018303101610.1103/PhysRevX.8.031016Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated AnnealingTameem AlbashDaniel A. LidarThe 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 2000Q processor 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. However, we do not find evidence for a quantum speedup: SQA exhibits the best scaling for annealing algorithms by a significant margin. This is a finding of independent interest, since we associate SQA’s advantage with its ability to transverse energy barriers in the semiclassical energy landscape by mimicking tunneling. Our construction of instance classes with verifiably optimal annealing times opens up the possibility of generating many new such classes based on a similar principle of promoting the presence of energy barriers that can be overcome more efficiently using quantum rather than thermal fluctuations, paving the way for further definitive assessments of scaling advantages using current and future quantum annealing devices.http://doi.org/10.1103/PhysRevX.8.031016 |
| spellingShingle | Tameem Albash Daniel A. Lidar Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing Physical Review X |
| title | Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing |
| title_full | Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing |
| title_fullStr | Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing |
| title_full_unstemmed | Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing |
| title_short | Demonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing |
| title_sort | demonstration of a scaling advantage for a quantum annealer over simulated annealing |
| url | http://doi.org/10.1103/PhysRevX.8.031016 |
| work_keys_str_mv | AT tameemalbash demonstrationofascalingadvantageforaquantumannealeroversimulatedannealing AT danielalidar demonstrationofascalingadvantageforaquantumannealeroversimulatedannealing |