Defining and detecting quantum speedup
Open accessThe DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Abstract
How to benchmark a quantum computer: Quantum machines offer the possibility of performing certain computations much faster than their classical counterparts. However, how to define and measure quantum speedup is a topic of debate. Rønnow et al. describe methods for fairly evaluating the difference in computational power between classical and quantum processors. They define various types of quantum speedup and consider quantum processors that are designed to solve a specific class of problems. Science , this issue p. 420
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“as of now we don't have a convincing theoretical argument or persuasive experimental evidence indicating that quantum annealers can really speed up the time to solution compared to the best classical hardware running the best algorithms for the same problems [28, 29].”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [28]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“although the speedup (or otherwise) seems to have a rather subtle dependence on the problem instance, classical solver compared, and measure of comparison. 38,39”
From Quantum algorithms: an overview (2016) · cites this paper as [39]
In the citing paper
“Furthermore, it is currently believed that quantum computers cannot offer an exponential speedup to NP-complete and harder problems [207], although they can offer scaling advantages that have been known in the literature as “limited quantum speedup” [208].”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [208]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
On the computational complexity of Ising spin glass models
Barahona, F. (1982) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/15/10/028 · Cited by 1,306
Research works printed but not linked: 8
- P. W. Shor in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE New York 1994) pp. 124–134.
- S. Boixo T. Albash F. M. Spedalieri N. Chancellor D. A. Lidar http://arxiv.org/abs/1212.1739 (2012). · arXiv
- W. Vinci T. Albash A. Mishra P. A. Warburton D. A. Lidar http://arxiv.org/abs/1403.4228 (2014). · arXiv
- J. A. Smolin G. Smith http://arxiv.org/abs/1305.4904 (2013). · arXiv
- S. W. Shin G. Smith J. A. Smolin U. Vazirani http://arxiv.org/abs/1401.7087 (2014). · arXiv
- S. Isakov I. Zintchenko T. Rønnow M. Troyer http://arxiv.org/abs/1401.1084 (2014). · arXiv
- C. C. McGeoch C. Wang in Proceedings of the ACM Conference on Computing Frontiers (ACM New York 2013) pp. XX–XX.
- S. Santra G. Quiroz G. V. Steeg D. A. Lidar http://arxiv.org/abs/1307.3931 (2013). · arXiv
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
“But as of now we don’t have a convincing theoretical argument or persuasive experimental evidence indicating that quantum annealers can really speed up the time to solution compared to the best classical hardware running the best algorithms for the same problems [28, 29].”
BackgroundBiamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
“This is known as a quantum speedup [106].”
Probing many-body dynamics on a 51-atom quantum simulator
Bernien, H., Schwartz, S., Keesling, A., Levine, H., Omran, A., Pichler, H., Choi, S., Zibrov, A. S., Endres, M., Greiner, M., et al. (2017) · Nature · doi:10.1038/nature24622 · Cited by 2,460
“perconducting [13] and optical [14] systems, but these realizations lack either coherence or quantum nonlinearity, which are essential for achieving full quantum speedup.”
BackgroundAlbash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
“Moreover, its role in (Boixo et al., 2016; Denchev et al., 2016) is limited to a prefactor, and does not translate into a scaling advantage, i.e., it does not qualify as a speedup according to the classification of (Rønnow et al., 2014).”
BackgroundMethodSelf-citationSuperconducting Qubits: Current State of Play
Kjaergaard, M., Schwartz, M. E., Braumüller, J., Krantz, P., Wang, J. I.-J., Gustavsson, S., & Oliver, W. D. (2020) · Annual Review of Condensed Matter Physics · doi:10.1146/annurev-conmatphys-031119-050605 · Cited by 1,544
Microwave photonics with superconducting quantum circuits
Gu, X., Kockum, A. F., Miranowicz, A., Liu, Y.-X., & Nori, F. (2017) · Physics Reports · doi:10.1016/j.physrep.2017.10.002 · Cited by 1,307
Superconducting Qubits: Current State of PlayPreprint
Kjærgaard, M., Schwartz, M. E., Braumüller, J., Krantz, P., Wang, J. I.-J., Gustavsson, S., & Oliver, W. D. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1,194
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
“The key phrase here is \slowly enough"; for some instances of CSPs on n bits, the time required for this evolution might be exponential in n .”
Quantum information processing with superconducting circuits: a review
Wendin, G. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa7e1a · Cited by 890
“In general, however, speedup of a computation is an asymptotic scaling property [109].”
BackgroundZhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913
A fully programmable 100-spin coherent Ising machine with all-to-all connections
McMahon, P. L., Marandi, A., Haribara, Y., Hamerly, R., Langrock, C., Tamate, S., Inagaki, T., Takesue, H., Utsunomiya, S., Aihara, K., et al. (2016) · Science · doi:10.1126/science.aah5178 · Cited by 702
“Benchmarking relatively small Ising problem instances is fraught with difficulty (12), and it is not even particularly obvious what benchmarks are appropriate in any given situation.”
BackgroundQuantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564
Self-citationQuantum spin dynamics and entanglement generation with hundreds of trapped ions
Bohnet, J. G., Sawyer, B. C., Britton, J. W., Wall, M. L., Rey, A. M., Foss-Feig, M., & Bollinger, J. J. (2016) · Science · doi:10.1126/science.aad9958 · Cited by 546
Network of time-multiplexed optical parametric oscillators as a coherent Ising machine
Marandi, A., Wang, Z., Takata, K., Byer, R. L., & Yamamoto, Y. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.249 · Cited by 541
Self-citationPerspectives of quantum annealing: methods and implementations
Hauke, P., Katzgraber, H. G., Lechner, W., Nishimori, H., & Oliver, W. D. (2020) · Reports on Progress in Physics · doi:10.1088/1361-6633/ab85b8 · Cited by 507
Limits on fundamental limits to computation
Markov, I. L. (2014) · Nature · doi:10.1038/nature13570 · Cited by 494
High‐Dimensional Quantum Communication: Benefits, Progress, and Future Challenges
Cozzolino, D., Da Lio, B., Bacco, D., & Oxenløwe, L. K. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900038 · Cited by 470
Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
Aramon, M., Rosenberg, G., Valiante, E., Miyazawa, T., Tamura, H., & Katzgraber, H. G. (2019) · Frontiers in Physics · doi:10.3389/fphy.2019.00048 · Cited by 442
“Efforts to benchmark quantum annealers against classical counterparts such as simulated annealing (SA) [15] have abounded [14, 16–30].”
BackgroundQuantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399
“We note that for instances with more qubits, more quantum hardware resources are brought to bear and therefore a fair comparison needs to take this into account [12,15].”
BackgroundInfluentialSelf-citationQuantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341
“While the question of whether QA can provide a quantum speed-up over classical approaches is still subject of a scientific debate (see, for example, [71, 109, 145] and references therein), there is ongoing dedicated effort to use QA hardware to solve application-motivated problems.”
Harnessing Disordered-Ensemble Quantum Dynamics for Machine Learning
Fujii, K., & Nakajima, K. (2017) · Physical Review Applied · doi:10.1103/physrevapplied.8.024030 · Cited by 337
Hamerly, R., Inagaki, T., McMahon, P. L., Venturelli, D., Marandi, A., Onodera, T., Ng, E., Langrock, C., Inaba, K., Honjo, T., et al. (2019) · Science Advances · doi:10.1126/sciadv.aau0823 · Cited by 328
“This makes clear that, as in quantum annealing, there is a tradeoff between success probability and annealing time [18].”
BackgroundInfluentialQuantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331
“In fact this procedure can be viewed as a classical algorithm for finding the minimum of −C and is sometimes referred to as SQA for Simulated Quantum Annealing [8, 15,21,31].”
MethodCoherent Ising machines—optical neural networks operating at the quantum limit
Yamamoto, Y., Aihara, K., Leleu, T., Kawarabayashi, K.-I., Kako, S., Fejer, M., Inoue, K., & Takesue, H. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0048-9 · Cited by 258
Quantum Computer Systems for Scientific Discovery
Alexeev, Y., Bacon, D., Brown, K. R., Calderbank, R., Carr, L. D., Chong, F. T., DeMarco, B., Englund, D., Farhi, E., Fefferman, B., et al. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.017001 · Cited by 248
“universal, and there is a current debate over the advantage such models can have over classical computation [18].”
BackgroundHamerly, R., Inagaki, T., McMahon, P. L., Venturelli, D., Marandi, A., Onodera, T., Ng, E., Langrock, C., Inaba, K., Honjo, T., et al. (2019) · CaltechAUTHORS (California Institute of Technology) · Cited by 257
A quantum annealing architecture with all-to-all connectivity from local interactions
Lechner, W., Hauke, P., & Zoller, P. (2015) · Science Advances · doi:10.1126/sciadv.1500838 · Cited by 256
Quantum critical dynamics in a 5,000-qubit programmable spin glass
King, A. D., Raymond, J., Lanting, T., Harris, R., Zucca, A., Altomare, F., Berkley, A. J., Boothby, K., Ejtemaee, S., Enderud, C., et al. (2023) · Nature · doi:10.1038/s41586-023-05867-2 · Cited by 242
Quantum Computer Systems for Scientific Discovery
Alexeev, Y., Bacon, D., Brown, K. R., Calderbank, R., Carr, L. D., Chong, F. T., DeMarco, B., Englund, D., Farhi, E., Fefferman, B., et al. (2021) · DSpace@MIT (Massachusetts Institute of Technology) · doi:10.6082/h7fqg-6vt65 · Cited by 240
Computational multiqubit tunnelling in programmable quantum annealers
Boixo, S., Smelyanskiy, V. N., Shabani, A., Isakov, S. V., Dykman, M., Denchev, V. S., Amin, M. H., Smirnov, A. Y., Mohseni, M., & Neven, H. (2016) · Nature Communications · doi:10.1038/ncomms10327 · Cited by 233
“As in other lines of work, we will choose the number of sweeps to obtain a good correlation with the probability of success of the D-Wave chip for a benchmark of random Ising models with binary couplings J mn A {1, (cid:2) 1} (refs 15,18,20,23).”
BackgroundSelf-citationReverse quantum annealing approach to portfolio optimization problems
Venturelli, D., & Kondratyev, A. (2019) · Quantum Machine Intelligence · doi:10.1007/s42484-019-00001-w · Cited by 233
Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network
Goto, H. (2016) · Scientific Reports · doi:10.1038/srep21686 · Cited by 226
A case study in programming a quantum annealer for hard operational planning problems
Rieffel, E. G., Venturelli, D., O’Gorman, B., Do, M. B., Prystay, E. M., & Smelyanskiy, V. N. (2015) · Quantum Information Processing · doi:10.1007/s11128-014-0892-x · Cited by 218
“In all cases, we used an annealing time of 20 μsec, the fastest annealing time currently available on the machine, which is also D-Wave’s recommended annealing time given that current data suggests that an even faster annealing time would be optimal [39].”
MethodQuantum versus classical annealing of Ising spin glasses
Heim, B., Rønnow, T. F., Isakov, S. V., & Troyer, M. (2015) · Science · doi:10.1126/science.aaa4170 · Cited by 193
Self-citationThe prospects of quantum computing in computational molecular biology
Outeiral, C., Strahm, M., Shi, J., Morris, G. M., Benjamin, S. C., & Deane, C. M. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1481 · Cited by 232
“Furthermore, it is currently believed that quantum computers cannot offer an exponential speedup to NP-complete and harder problems [207], although they can offer scaling advantages that have been known in the literature as “limited quantum speedup” [208].”
BackgroundQuantum Optimization of Fully Connected Spin Glasses
Venturelli, D., Mandrà, S., Knysh, S., O’Gorman, B., Biswas, R., & Smelyanskiy, V. (2015) · Physical Review X · doi:10.1103/physrevx.5.031040 · Cited by 209
“For these reasons groups around the world have started to experimentally benchmark the machine [9–11], nurturing a lively discussion on whether the device is making functional use of quantum mechanics for computation [12] and how to properly measure speedups between different computational/experimental algorithms [13,…”
BackgroundMethodInfluentialMaterial platforms for defect qubits and single-photon emitters
Zhang, G., Cheng, Y., Chou, J.-P., & Gali, A. (2020) · Applied Physics Reviews · doi:10.1063/5.0006075 · Cited by 207
Li, R. Y., Di Felice, R., Rohs, R., & Lidar, D. A. (2018) · npj Quantum Information · doi:10.1038/s41534-018-0060-8 · Cited by 202
“Much attention has been paid to whether the DW devices are capable of delivering quantum speedups [32–36].”
BackgroundSelf-citationWhen does a physical system compute?
Horsman, D., Stepney, S., Wagner, R. C., & Kendon, V. (2014) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2014.0182 · Cited by 196
“The availability or otherwise of embedding steps tells us about the physical capabilities of our necessarily finite computers, as opposed to the arbitrarily large computations that can be described abstractly.”
BackgroundDemonstration of a Scaling Advantage for a Quantum Annealer over Simulated Annealing
Albash, T., & Lidar, D. A. (2018) · Physical Review X · doi:10.1103/physrevx.8.031016 · Cited by 238
“We note that our results are robust to modifying the SA annealing schedule from a quadratic to a linear function in β (seeAppendixE), and under a change of themetric to the socalled “quantile-of-ratios speedup” [18] (see Appendix F).”
BackgroundMethodResultInfluentialSelf-citationEfficient partition of integer optimization problems with one-hot encoding
Okada, S., Ohzeki, M., & Taguchi, S. (2019) · Scientific Reports · doi:10.1038/s41598-019-49539-6 · Cited by 190
Designing metamaterials with quantum annealing and factorization machines
Kitai, K., Guo, J., Ju, S., Tanaka, S., Tsuda, K., Shiomi, J., & Tamura, R. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013319 · Cited by 181
Open source software in quantum computing
Fingerhuth, M., Babej, T., & Wittek, P. (2018) · PLOS ONE · doi:10.1371/journal.pone.0208561 · Cited by 185
OIM: Oscillator-Based Ising Machines for Solving Combinatorial Optimisation Problems
Wang, T., & Roychowdhury, J. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-19311-9_19 · Cited by 186
“While many question their advantages over simulated annealing run on classical computers [25], proponents believe that through a mechanism known as quantum tunnelling, they can offer large speedups on problems with certain energy landscapes [26].”
BackgroundChallenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
Application of Quantum Annealing to Training of Deep Neural Networks
Adachi, S. H., & Henderson, M. P. (2015) · arXiv · doi:10.48550/arxiv.1510.06356 · Cited by 176
“[ 19] Similarly in this case, it is conceivable that the behavior on the right hand side of these figures could be reproduced by a cleverly-designed classical algorithm.”
MethodInfluentialSolving the Optimal Trading Trajectory Problem Using a Quantum Annealer
Rosenberg, G., Haghnegahdar, P., Goddard, P., Carr, P., Wu, K., & de Prado, M. L. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2574703 · Cited by 171
Probing for quantum speedup in spin-glass problems with planted solutions
Hen, I., Job, J., Albash, T., Rønnow, T. F., Troyer, M., & Lidar, D. A. (2015) · Physical Review A · doi:10.1103/physreva.92.042325 · Cited by 167
Self-citationSearching for quantum speedup in quasistatic quantum annealers
Amin, M. H. S. (2015) · Physical Review A · doi:10.1103/physreva.92.052323 · Cited by 154
Superconductor Electronics: Status and Outlook
Braginski, A. I. (2018) · Journal of Superconductivity and Novel Magnetism · doi:10.1007/s10948-018-4884-4 · Cited by 160
“lems such as optimization, see for example [144, 145].”
BackgroundOptimised simulated annealing for Ising spin glasses
Isakov, S., Zintchenko, I., Rønnow, T. F., & Troyer, M. (2014) · Computer Physics Communications · doi:10.1016/j.cpc.2015.02.015 · Cited by 164
“The ground state energies of all instances were verified by exact solvers [17].”
MethodSelf-citationAdiabatic Quantum Computation and Quantum Annealing: Theory and Practice
McGeoch, C. C. (2014) · Synthesis lectures on quantum computing · doi:10.2200/s00585ed1v01y201407qmc008 · Cited by 288
Bando, Y., Susa, Y., Oshiyama, H., Shibata, N., Ohzeki, M., Gómez-Ruiz, F. J., Lidar, D. A., Suzuki, S., del Campo, A., & Nishimori, H. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033369 · Cited by 151
Self-citationQuantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
Benedetti, M., Realpe-Gómez, J., Biswas, R., & Perdomo‐Ortiz, A. (2017) · Physical Review X · doi:10.1103/physrevx.7.041052 · Cited by 217
Katzgraber, H. G., Hamze, F., & Andrist, R. S. (2014) · Physical Review X · doi:10.1103/physrevx.4.021008 · Cited by 180
King, A. D., Raymond, J., Lanting, T., Isakov, S. V., Mohseni, M., Poulin-Lamarre, G., Ejtemaee, S., Bernoudy, W., Ozfidan, I., Smirnov, A. Y., et al. (2021) · Nature Communications · doi:10.1038/s41467-021-20901-5 · Cited by 208
Self-citationNonnegative/Binary matrix factorization with a D-Wave quantum annealer
O’Malley, D., Vesselinov, V. V., Alexandrov, B. S., & Alexandrov, L. B. (2018) · PLOS ONE · doi:10.1371/journal.pone.0206653 · Cited by 140
Prospects for quantum enhancement with diabatic quantum annealing
Crosson, E., & Lidar, D. A. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00313-6 · Cited by 195
Self-citationBeyond-classical computation in quantum simulation
King, A. D., Nocera, A., Rams, M. M., Dziarmaga, J., Wiersema, R., Bernoudy, W., Raymond, J., Kaushal, N., Heinsdorf, N., Harris, R., et al. (2025) · Science · doi:10.1126/science.ado6285 · Cited by 138
Quantum-inspired algorithms in practice
Arrazola, J. M., Delgado, A., Bardhan, B. R., & Lloyd, S. (2020) · Quantum · doi:10.22331/q-2020-08-13-307 · Cited by 182
Consistency tests of classical and quantum models for a quantum annealer
Albash, T., Vinci, W., Mishra, A., Warburton, P. A., & Lidar, D. A. (2015) · Physical Review A · doi:10.1103/physreva.91.042314 · Cited by 151
Self-citationModernizing quantum annealing using local searches
Chancellor, N. (2017) · New Journal of Physics · doi:10.1088/1367-2630/aa59c4 · Cited by 123
Machine Learning Algorithms in Quantum Computing: A Survey
Ramezani, S. B., Sommers, A., Manchukonda, H. K., Rahimi, S., & Amirlatifi, A. (2020) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn48605.2020.9207714 · Cited by 185
“…unique feature of QC, results in their ability to pursue several parallel paths simultaneously in a single calculation unit, a concept that is not physically possible in classical machines, and would rather require several passes to be achieved, hence causing higher orders of complexity [2]–[4].”
BackgroundPower of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
Marshall, J., Venturelli, D., Hen, I., & Rieffel, E. G. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.11.044083 · Cited by 126
Coherent Coupled Qubits for Quantum Annealing
Weber, S. J., Samach, G., Hover, D. J., Gustavsson, S., Kim, D. K., Melville, A. J., Rosenberg, D., Sears, A., Yan, F., Yoder, J., et al. (2017) · Physical Review Applied · doi:10.1103/physrevapplied.8.014004 · Cited by 122
Yamamoto, K., Kawamura, K., Ando, K., Mertig, N., Takemoto, T., Yamaoka, M., Teramoto, H., Sakai, A., Takamaeda-Yamazaki, S., & Motomura, M. (2020) · IEEE Journal of Solid-State Circuits · doi:10.1109/jssc.2020.3027702 · Cited by 142
“Time-to-solution (TTS) tts(P), time required for obtaining a near-optimal solution with a probability of P , is typically used to evaluate the annealing performance [23], [24] and is calculated as follows: tts(P) = t × ln (1 − P) ln (1 − Pa(t)) (9)”
Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
Willsch, D., Willsch, M., Gonzalez Calaza, C. D., Jin, F., De Raedt, H., Svensson, M., & Michielsen, K. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03476-y · Cited by 114
Mandrà, S., Zhu, Z., Wang, W., Perdomo‐Ortiz, A., & Katzgraber, H. G. (2016) · Physical Review A · doi:10.1103/physreva.94.022337 · Cited by 128
“[47]: first, we expand the notion of “limited quantum speedup” [22] to take into account different classes of algorithms (see Sec.”
BackgroundInfluentialUnderstanding Quantum Tunneling through Quantum Monte Carlo Simulations
Isakov, S. V., Mazzola, G., Smelyanskiy, V., Zhang, J., Boixo, S., Neven, H., & Troyer, M. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.180402 · Cited by 102
Self-citationQuantum annealing correction for random Ising problems
Pudenz, K. L., Albash, T., & Lidar, D. A. (2015) · Physical Review A · doi:10.1103/physreva.91.042302 · Cited by 99
Self-citationQuantum machine learning: from physics to software engineering
Melnikov, A. A., Kordzanganeh, M., Alodjants, A. P., & Lee, R. (2023) · Advances in Physics X · doi:10.1080/23746149.2023.2165452 · Cited by 178
Wittek, P. (2014) · Elsevier eBooks · doi:10.1016/b978-0-12-800953-6.00004-9 · Cited by 103
Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians
Nishimori, H., & Takada, K. (2017) · Frontiers in ICT · doi:10.3389/fict.2017.00002 · Cited by 126
“counterpart, simulated annealing, according to the criterion of “limited quantum speedup” (Rønnow et al., 2014) as well as on how a non-stoquastic Hamiltonian compares with its stoquastic counterpart.”
MethodQuantum annealing correction with minor embedding
Vinci, W., Albash, T., Paz-Silva, G. A., Hen, I., & Lidar, D. A. (2015) · Physical Review A · doi:10.1103/physreva.92.042310 · Cited by 102
Self-citationAlbash, T., Rønnow, T. F., Troyer, M., & Lidar, D. A. (2015) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2015-02346-0 · Cited by 96
Self-citationA NASA perspective on quantum computing: Opportunities and challenges
Biswas, R., Zhang, J., Kechezhi, K., Knysh, S., Mandrà, S., O’Gorman, B., Perdomo‐Ortiz, A., Petukhov, A. G., Realpe-Gómez, J., Rieffel, E. G., et al. (2016) · Parallel Computing · doi:10.1016/j.parco.2016.11.002 · Cited by 102
“[33] defines four classes of quantum speedups: • Provable quantum speedup: It is rigorously proven that no classical algo-rithm can scale better than a given quantum algorithm.”
BackgroundSelf-citationA single shot coherent Ising machine based on a network of injection-locked multicore fiber lasers
Babaeian, M., Nguyen, D. T., Demir, V., Akbulut, M., Blanche, P., Kaneda, Y., Guha, S., Neifeld, M. A., & Peyghambarian, N. N. (2019) · Nature Communications · doi:10.1038/s41467-019-11548-4 · Cited by 100
Quantum simulation of transverse Ising models with Rydberg atoms
Schauß, P. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aa9c59 · Cited by 118
Quantum Computing: Circuits, Algorithms, and Applications
Shafique, M. A., Munir, A., & Latif, I. (2024) · IEEE Access · doi:10.1109/access.2024.3362955 · Cited by 111
“Bits in classical computing are restricted to zero or one whereas quantum computing employ units (qubits) that are capable of existing in states of zero, one, or any intermediate value [10], [11], [12].”
BackgroundQuantum Annealing amid Local Ruggedness and Global Frustration
King, J., Yarkoni, S., Raymond, J., Ozfidan, I., King, A. D., Nevisi, M. M., Hilton, J., & McGeoch, C. C. (2019) · Journal of the Physical Society of Japan · doi:10.7566/jpsj.88.061007 · Cited by 120
Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
Katzgraber, H. G., Hamze, F., Zhu, Z., Ochoa, A. J., & Munoz-Bauza, H. (2015) · Physical Review X · doi:10.1103/physrevx.5.031026 · Cited by 145
“…technologies is slowly coming to an end mostly due to manufacturing and material constraints [4], interest in developing faster optimization methods has shifted to the development of new state-of-the-art algorithms, as well as novel computing paradigms, e.g., based on quantum architectures.”
BackgroundInfluentialImproving solutions by embedding larger subproblems in a D-Wave quantum annealer
Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S. (2019) · Scientific Reports · doi:10.1038/s41598-018-38388-4 · Cited by 125
Binary optimization by momentum annealing
Okuyama, T., Sonobe, T., Kawarabayashi, K., & Yamaoka, M. (2019) · Physical review. E · doi:10.1103/physreve.100.012111 · Cited by 118
Solving combinatorial optimisation problems using oscillator based Ising machines
Wang, T., Wu, L., Nobel, P., & Roychowdhury, J. (2021) · Natural Computing · doi:10.1007/s11047-021-09845-3 · Cited by 131
“While some question their advantages over simulated annealing run on classical computers (Rønnow et al. 2014), proponents believe that through a mechanism known as quantum annealing, they can offer large speedups on problems with certain energy landscapes (Denchev et al. 2016).”
BackgroundBayesian network structure learning using quantum annealing
O’Gorman, B., Babbush, R., Perdomo‐Ortiz, A., Aspuru‐Guzik, A., & Smelyanskiy, V. (2015) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2015-02349-9 · Cited by 105
“The recent availability of quantum annealing devices from D-Wave Systems has sparked interest in the experimental determination of whether or not the current generation of the device provides such speedup [9, 10].”
BackgroundBenchmarking Quantum Annealing Controls with Portfolio Optimization
Grant, E., Humble, T. S., & Stump, B. (2021) · Physical Review Applied · doi:10.1103/physrevapplied.15.014012 · Cited by 90
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
“see [58, 59]), for our purposes, we simply state that a theoretical quantum advantage is defined by four key properties:”
BackgroundMapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis
Bian, Z., Chudak, F. A., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016) · Frontiers in ICT · doi:10.3389/fict.2016.00014 · Cited by 91
Quantum Cryptography and Quantum Key Distribution Protocols: A Survey
Padamvathi, V., Vardhan, B. V., & Krishna, A. V. N. (2016) · IEEE International Conference on Advanced Computing (IACC) · doi:10.1109/iacc.2016.109 · Cited by 107
Experimental statistical signature of many-body quantum interference
Giordani, T., Flamini, F., Pompili, M., Viggianiello, N., Spagnolo, N., Crespi, A., Osellame, R., Wiebe, N., Walschaers, M., Buchleitner, A., et al. (2018) · Nature Photonics · doi:10.1038/s41566-018-0097-4 · Cited by 83
“For both input states A = (1,4,5) and B = (1,3,6) we measure three-photon data samples (orange) and compare them with the expected distribution from the reconstructed transformation (blue).”
Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
Katzgraber, H. G., Hamze, F., Zhu, Z., Ochoa, A. J., & Munoz-Bauza, H. (2015) · OakTrust (Texas A&M University Libraries) · Cited by 86
Tunneling and Speedup in Quantum Optimization for Permutation-Symmetric Problems
Muthukrishnan, S., Albash, T., & Lidar, D. A. (2016) · Physical Review X · doi:10.1103/physrevx.6.031010 · Cited by 86
Self-citationQuantum Bits with Josephson Junctions
Kockum, A. F., & Nori, F. (2019) · Springer series in materials science · doi:10.1007/978-3-030-20726-7_17 · Cited by 111
A deceptive step towards quantum speedup detection
Mandrà, S., & Katzgraber, H. G. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aac8b2 · Cited by 82
“There have been multiple attempts to define quantum speedup [7, 8], as well as quantify any “quantumness” and problem-solving efficacy of current commercially-available quantum annealers [7, 9–22].”
BackgroundA 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
Takata, K., Marandi, A., Hamerly, R., Haribara, Y., Maruo, D., Tamate, S., Hiromasa, S., Utsunomiya, S., & Yamamoto, Y. (2016) · Scientific Reports · doi:10.1038/srep34089 · Cited by 87
Optimal structure and parameter learning of Ising models
Lokhov, A. Y., Vuffray, M., Misra, S., & Chertkov, M. (2018) · Science Advances · doi:10.1126/sciadv.1700791 · Cited by 109
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79
“[2] that simulated annealing is competitive with the D-Wave One machine even on desktop CPUs (this has expanded on in great detail including new experiments on the D-Wave Two processor [13]).”
BackgroundClassical variational simulation of the Quantum Approximate Optimization Algorithm
Medvidović, M., & Carleo, G. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00440-z · Cited by 79
Zero-temperature quantum annealing bottlenecks in the spin-glass phase
Knysh, S. (2016) · Nature Communications · doi:10.1038/ncomms12370 · Cited by 93
“Benchmarking of a hardware implementation of QA, courtesy of D-Wave Systems, shows no improvement in the scaling of the performance 13,14 .”
Method
Metadata
- Authors
- Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M.
- Affiliations
- ETH Zurich (CH)
- University of Southern California (US)
- Google (Switzerland) (CH)
- Microsoft (United States) (US)
- University of California, Santa Barbara (US)
- Corresponding author
- Troyer, Matthias
- Venue
- Science
- Published
- 2014-07-25
- Volume
- 345
- Issue
- 6195
- Pages
- 420-424
- ISSN
- 0036-8075 (ISSN-L)
- 1095-9203
- OpenAlex
- W2028918948
- Semantic Scholar
- d4836804ee59c483943cc8f5e1eb88b58e4f52fc
- Cited by
- 601
- References
- 37
- Citations by year
- 2026: 35 · 2025: 50 · 2024: 47 · 2023: 50 · 2022: 45 · 2021: 54 · 2020: 47 · 2019: 54 · 2018: 45 · 2017: 44 · 2016: 55 · 2015: 51 · 2014: 24
- FWCI
- 57.83
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Science (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum advantage, quantum annealing, superconducting qubits
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.