The DOI matches its Crossref record; 54 of the 54 references it cites were found in a registry or an index.
Evidence for quantum annealing with more than one hundred qubits
Open accessAbstract
Quantum technology is maturing to the point where quantum devices, such as quantum communication systems, quantum random number generators and quantum simulators may be built with capabilities exceeding classical computers. A quantum annealer, in particular, solves optimization problems by evolving a known initial configuration at non-zero temperature towards the ground state of a Hamiltonian encoding a given problem. Here, we present results from tests on a 108 qubit D-Wave One device based on superconducting flux qubits. By studying correlations we find that the device performance is inconsistent with classical annealing or that it is governed by classical spin dynamics. In contrast, we find that the device correlates well with simulated quantum annealing. We find further evidence for quantum annealing in the form of small-gap avoided level crossings characterizing the hard problems. To assess the computational power of the device we compare it against optimized classical algorithms. Quantum annealing is expected to solve certain optimization problems more efficiently, but there are still open questions regarding the functioning of devices such as D-Wave One. A numerical and experimental investigation of its performance shows evidence for quantum annealing with 108 qubits.
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 check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“For example, the achievable rate for the transmission of classical information over a noisy quantum channel is given by the Holevo-Schumacher-Westmorel (HSW) coding theorem [136], which generalizes the Shannon's theorem in quantum settings.”
From Quantum Machine Learning for 6G Communication Networks: State-of-the-Art and Vision for the Future (2019) · cites this paper as [136]
Experimental — accuracy not yet measured
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 · cited 1×
“Mimicking this process in computer simulations is the idea behind simulated annealing as an optimisation method [8], which views the cost function of an optimisation problem as the energy of a physical system.”
MethodEquation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
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 · cited 3×
“Unlike adiabatic quantum computing [16], which has a similar schedule but assumes fully coherent adiabatic ground state evolution at zero temperature, quantum annealing [4–6, 10] is a positive temperature method involving an open quantum system coupled to a thermal bath.”
BackgroundMethodQuantum simulations with ultracold quantum gases
Bloch, I., Dalibard, J., & Nascimbène, S. (2012) · Nature Physics · doi:10.1038/nphys2259 · Cited by 2,339 · cited 1×
“At a time when quantum effects start to pose limits to further miniaturisation of devices and the exponential performance increase due to Moore’s law, quantum technology is maturing to the point where quantum devices, such as quantum communication systems [1], quantum random number generators [2] and quantum simulator…”
BackgroundA 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 · cited 1×
“Unlike adiabatic quantum computing [16], which has a similar schedule but assumes fully coherent adiabatic ground state evolution at zero temperature, quantum annealing [4–6, 10] is a positive temperature method involving an open quantum system coupled to a thermal bath.”
MethodQuantum 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 · cited 3×
“In this work we report on computer simulations and experimental tests on a D-Wave One device [13] in order to address central open questions about quantum annealers: is the device actually a quantum annealer, i.”
BackgroundMethodInfluentialEquation of state calculations by fast computing machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · doi:10.2172/4390578 · Cited by 1,701
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 · cited 1×
“This problem is nondeterministic polynomially (NP) hard [15], meaning that it is at least as hard as the hardest problems in NP, a class which includes notoriously difficult problems such as traveling salesman, satisfiablity of logical formulas, and ar X iv :1 30 4.”
BackgroundTheory of Quantum Annealing of an Ising Spin Glass
Santoro, G. E., Martoňák, R., Tosatti, E., & Car, R. (2002) · Science · doi:10.1126/science.1068774 · Cited by 734 · cited 3×
“[11], we also observe that the simulated quantum annealer here scales slightly worse than the simulated classical annealer.”
BackgroundMethodInfluentialQuantum annealing: A new method for minimizing multidimensional functions
Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (1994) · Chemical Physics Letters · doi:10.1016/0009-2614(94)00117-0 · Cited by 644 · cited 3×
“[5] Finnila, A.”
BackgroundMethodBucket elimination: A unifying framework for reasoning
Dechter, R. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00059-4 · Cited by 583 · cited 4×
“In addition to belief propagation using bucket sort [26], we implemented an exact divide-and-conquer algorithm specifically designed for the chimera graph, generalising divide-and-conquer for the square lattice.”
MethodInfluentialQuantum Annealing of a Disordered Magnet
Brooke, J., Bitko, D., F., T., Rosenbaum, & Aeppli, G. (1999) · Science · doi:10.1126/science.284.5415.779 · Cited by 518 · cited 1×
“Further speedup is expected in physical quantum annealing, either as an experimental technique for annealing a quantum spin glass [12], or – and this is what we will focus on here – as a computational technique in a programmable quantum device.”
MethodMinor-embedding in adiabatic quantum computation: I. The parameter setting problem
Choi, V. (2008) · Quantum Information Processing · doi:10.1007/s11128-008-0082-9 · Cited by 410 · cited 4×
“[33] Choi, V.”
BackgroundMethodInfluentialIsing models of quantum frustration
Moessner, R., & Sondhi, S. L. (2001) · Physical Review B · doi:10.1103/physrevb.63.224401 · Cited by 397 · cited 2×
“[41] Moessner, R.”
BackgroundFinding low-energy conformations of lattice protein models by quantum annealing
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00571 · Cited by 366 · cited 1×
“Instead of trying to map specific optimisation problem to the connectivity graph of the chip [20, 21], our strategy has been to choose random (NP hard) spin glass problems that can directly be realised.”
BackgroundExperimental signature of programmable quantum annealing
Boixo, S., Albash, T., Spedalieri, F. M., Chancellor, N., & Lidar, D. A. (2013) · Nature Communications · doi:10.1038/ncomms3067 · Cited by 293
Self-citationMinor-embedding in adiabatic quantum computation: II. Minor-universal graph design
Choi, V. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0200-3 · Cited by 278 · cited 1×
“The tree width of this graph is 17 for the ideal (128 qubit) Rainier chip and scales as √ N for an N -qubit Chimera graph [16, 17].”
MethodExperimental investigation of an eight-qubit unit cell in a superconducting optimization processor
Harris, R., Johnson, M. W., Lanting, T., Berkley, A. J., Johansson, J., Bunyk, P., Tolkacheva, E., Ladizinsky, E., Ladizinsky, N., Oh, T., et al. (2010) · Physical Review B · doi:10.1103/physrevb.82.024511 · Cited by 273 · cited 1×
“We attribute these to calibration errors of the couplers in the device which vary by about 10% [31].”
MethodSolving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations
Rendl, F., Rinaldi, G., & Wiegele, A. (2010) · Mathematical Programming · doi:10.1007/s10107-008-0235-8 · Cited by 264 · cited 3×
“[39] Rendl, F.”
MethodAnderson localization makes adiabatic quantum optimization fail
Altshuler, B., Krovi, H., & Roland, J. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1002116107 · Cited by 246 · cited 1×
“Many spins would need to be flipped to reach a ground state, which results in small tunneling matrix elements between the state found and the true ground state and thus small gap avoided level crossings [26].”
BackgroundThermally assisted quantum annealing of a 16-qubit problem
Dickson, N. G., Johnson, M. W., Amin, M. H., Harris, R., Altomare, F., Berkley, A. J., Bunyk, P., Cai, J., Chapple, E. M., Chavez, P., et al. (2013) · Nature Communications · doi:10.1038/ncomms2920 · Cited by 225 · cited 1×
“, do the quantum effects observed on 8 [11, 12] and 16 qubits [13] persist when scaling problems up to more than 100 qubits, or do short coherence times turn the device into a classical, thermal annealer? Which problems are easy and which problems are hard for a quantum annealer, for a simulated classical annealer, fo…”
BackgroundRay, P., Chakrabarti, B. K., & Chakrabarti, A. (1989) · Physical Review B · doi:10.1103/physrevb.39.11828 · Cited by 209 · cited 3×
“Unlike adiabatic quantum computing [16], which has a similar schedule but assumes fully coherent adiabatic ground state evolution at zero temperature, quantum annealing [4–6, 10] is a positive temperature method involving an open quantum system coupled to a thermal bath.”
BackgroundMethodBapst, V., Foini, L., Krząkała, F., Semerjian, G., & Zamponi, F. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.10.002 · Cited by 192 · cited 2×
“This phenomenon has been previously observed in the random subcubes model, a specially constructed toy model [43].”
MethodRieger, H., & Kawashima, N. (1999) · The European Physical Journal B · doi:10.1007/s100510050761 · Cited by 185
Experimental demonstration of a robust and scalable flux qubit
Harris, R., Johansson, J., Berkley, A. J., Johnson, M. W., Lanting, T., Han, S., Bunyk, P., Ladizinsky, E., Oh, T., Perminov, I., et al. (2010) · Physical Review B · doi:10.1103/physrevb.81.134510 · Cited by 177 · cited 2×
“[30] Harris, R.”
MethodQuantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model
Martoňák, R., Santoro, G. E., & Tosatti, E. (2002) · Physical review. B, Condensed matter · doi:10.1103/physrevb.66.094203 · Cited by 171
Experimental evaluation of an adiabiatic quantum system for combinatorial optimization
McGeoch, C. C., & Wang, C. (2013) · Proceedings of the ACM International Conference on Computing Frontiers · doi:10.1145/2482767.2482797 · Cited by 166 · cited 2×
“We note that even then the simulated annealer finds solutions in few milliseconds, which is faster than first benchmarks reported for a next-generation 512 qubit D-Wave device [28].”
BackgroundResultThe beginning of the use of metals and alloys
Samuels, L. E. (1990) · Materials Characterization · doi:10.1016/1044-5803(90)90075-u · Cited by 150
Optimization by quantum annealing: Lessons from hard satisfiability problems
Battaglia, D. A., Santoro, G. E., & Tosatti, E. (2005) · Physical Review E · doi:10.1103/physreve.71.066707 · Cited by 136 · cited 1×
“A similar behavior has previously been reported for k-satisfiablity problems [27].”
BackgroundSize Dependence of the Minimum Excitation Gap in the Quantum Adiabatic Algorithm
Young, A. P., Knysh, S., & Smelyanskiy, V. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.170503 · Cited by 127 · cited 1×
“[24, 25].”
First-order quantum phase transition in adiabatic quantum computation
Amin, M. H. S., & Choi, V. (2009) · Physical Review A · doi:10.1103/physreva.80.062326 · Cited by 123 · cited 2×
“[42] Amin, M.”
BackgroundBapst, V., Foini, L., Krząkała, F., Semerjian, G., & Zamponi, F. (2012) · HAL · Cited by 123
Farhi, E., Gosset, D., Hen, I., Sandvik, A. W., Shor, P. W., Young, A. P., & Zamponi, F. (2012) · Physical Review A · doi:10.1103/physreva.86.052334 · Cited by 116 · cited 1×
“In hard optimisation problems, the smallest gaps of avoided level crossings are expected to close exponentially fast with increasing problem size [18, 19], implying an exponential scaling of the required annealing time with problem size.”
BackgroundA scalable readout system for a superconducting adiabatic quantum optimization system
Berkley, A. J., Johnson, M. W., Bunyk, P., Harris, R., Johansson, J., Lanting, T. M., Ladizinsky, E., Tolkacheva, E., Amin, M. H. S., & Rose, G. (2010) · Superconductor Science and Technology · doi:10.1088/0953-2048/23/10/105014 · Cited by 112
Experimental Determination of Ramsey Numbers
Bian, Z., Chudak, F. A., Macready, W. G., Clark, L., & Gaitan, F. (2013) · Physical Review Letters · doi:10.1103/physrevlett.111.130505 · Cited by 105
Adiabatic quantum programming: minor embedding with hard faults
Klymko, C., Sullivan, B. D., & Humble, T. S. (2014) · Quantum Information Processing · doi:10.1007/s11128-013-0683-9 · Cited by 99 · cited 1×
“[44] Klymko, C.”
First-Order Transitions and the Performance of Quantum Algorithms in Random Optimization Problems
Jörg, T., Krząkała, F., Semerjian, G., & Zamponi, F. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.207206 · Cited by 98 · cited 2×
“[17] Jörg, T.”
BackgroundThe Beginnings of the Use of Metals and Alloys
Westbrook, J. H., & Maddin, R. (1990) · Technology and Culture · doi:10.2307/3106088 · Cited by 92
Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems
Hen, I., & Young, A. P. (2011) · Physical Review E · doi:10.1103/physreve.84.061152 · Cited by 89 · cited 1×
“In hard optimisation problems, the smallest gaps of avoided level crossings are expected to close exponentially fast with increasing problem size [18, 19], implying an exponential scaling of the required annealing time with problem size.”
BackgroundImproved Exact Solver for the Weighted MAX-SAT Problem
Kügel, A. (2018) · EPiC series in computing · doi:10.29007/38lm · Cited by 88 · cited 2×
“We investigated four exact solvers, akmaxsat [38], the biqmac algorithm [39] used in the spin glass server [40], exact belief propagation using bucket sort [27] and a related divide-and-conquer algorithm.”
MethodClassical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79 · cited 1×
“Similarly, there are poor correlations [22] with a classical spin dynamics model of reference [23].”
BackgroundA fast algorithm for the Cyber 205 to simulate the 3D Ising model
Bhanot, G., Duke, D. W., & Salvador, R. (1986) · Journal of Statistical Physics · doi:10.1007/bf01011918 · Cited by 65 · cited 1×
“[34, 35], uses multi-spin coding to simultaneously perform 64 simulations in parallel on a single CPU core: each bit of a 64-bit integer represents the state of a spin in one of the 64 simulations and all 64 spins are updated at once.”
MethodQuantum spin chains in a magnetic field
Kashurnikov, V. А., Prokof'ev, N. V., Svistunov, B. V., & Troyer, M. (1999) · Physical review. B, Condensed matter · doi:10.1103/physrevb.59.1162 · Cited by 40 · cited 1×
“[24, 25].”
Self-citationHeuer, H.-O. (1990) · Computer Physics Communications · doi:10.1016/0010-4655(90)90186-5 · Cited by 26 · cited 1×
“[34, 35], uses multi-spin coding to simultaneously perform 64 simulations in parallel on a single CPU core: each bit of a 64-bit integer represents the state of a spin in one of the 64 simulations and all 64 spins are updated at once.”
MethodComment on: "Classical signature of quantum annealing"
Wang, L., Rønnow, T. F., Boixo, S., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.5837 · Cited by 23 · cited 1×
“Similarly, there are poor correlations [22] with a classical spin dynamics model of reference [23].”
BackgroundSelf-citationQuantum annealing: A new method for minimizing multidimensional functions
Finnila, A. B., Gomez, M. A., Sebenik, C., Stenson, C., & Doll, J. D. (2007) · doi:10.1093/oso/9780195310108.003.0095 · Cited by 23
Excitation gap from optimized correlation functions in quantum Monte Carlo simulations
Hen, I. (2012) · Physical Review E · doi:10.1103/physreve.85.036705 · Cited by 22 · cited 1×
“[45] Hen, I.”
Experimental determination of Ramsey numbers with quantum annealingPreprint
Bian, Z., Chudak, F. A., Macready, W. G., et al. (2012) · arXiv (Cornell University) · Cited by 12
Classical signature of quantum annealingPreprint
Smolin, J. A., & Smith, G. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.4904 · Cited by 10 · cited 1×
“Similarly, there are poor correlations [22] with a classical spin dynamics model of reference [23].”
BackgroundExperimental Signature of Programmable Quantum Annealing (Author's Manuscript)
Boixo, S., Albash, T., Spedalieri, F. M., et al. (2013) · Cited by 4
Self-citationAdiabatic Quantum Programming: Minor Embedding With Hard FaultsPreprint
Klymko, C., Sullivan, B. D., & Humble, T. S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1210.8395 · Cited by 3 · cited 1×
“[44] Klymko, C.”
Experimental signature of programmable quantum annealing
Boixo, S., Albash, T., Spedalieri, F. M., Chancellor, N., & Lidar, D. A. (2012) · arXiv · doi:10.48550/arxiv.1212.1739
Self-citationIsing formulations of many NP problems
Lucas, A. (2013) · arXiv · doi:10.48550/arxiv.1302.5843
Research works printed but not linked: 1
- McGeoch, C. C. & Wang, C. Proc. 2013 ACM Conf. Comput. Frontiers (ACM, 2013).
Cited by
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
“The scaling of the algorithm with n is then determined from the scaling with n of TTSopt, as, e.g., in (Boixo et al., 2014).”
MethodSelf-citationTrapped-ion quantum computing: Progress and challenges
Bruzewicz, C. D., Chiaverini, J., McConnell, R., & Sage, J. M. (2019) · Applied Physics Reviews · doi:10.1063/1.5088164 · Cited by 1,483
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
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Self-citation
Metadata
- Authors
- Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M.
- Affiliations
- University of Southern California (US)
- ETH Zurich (CH)
- Microsoft (United States) (US)
- University of California, Santa Barbara (US)
- Corresponding author
- Troyer, Matthias
- Venue
- Nature Physics
- Published
- 2014-02-28
- Volume
- 10
- Issue
- 3
- Pages
- 218-224
- ISSN
- 1745-2473 (ISSN-L)
- 1745-2481
- OpenAlex
- W2117762142
- Cited by
- 810
- References
- 49
- Citations by year
- 2026: 35 · 2025: 49 · 2024: 49 · 2023: 51 · 2022: 68 · 2021: 71 · 2020: 67 · 2019: 71 · 2018: 66 · 2017: 97 · 2016: 67 · 2015: 68 · 2014: 41
- FWCI
- 90.73
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Nature Physics (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 annealing, superconducting flux qubit, avoided crossings, spin correlations, optimization problems, ground state, simulated quantum annealing
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.