The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective
Open accessThe DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Abstract
Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.
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.
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
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · cited 50×
“An example of a problem in P is deciding the satisfiability of XORSAT formulas: thanks to the mapping onto a problem of linear equations, for any choice of the hyper-graph and of the constants Ja one can use Gaussian elimination and check in a number of operations growing as N3 whether or not there exists a configurat…”
InfluentialAbsence of Diffusion in Certain Random Lattices
Anderson, P. W. (1958) · Physical Review · doi:10.1103/physrev.109.1492 · Cited by 12,468 · cited 3×
“Physical systems defined via random constructions have been studied for decades in physics (an early example being the Anderson model [139] of localization); in that context the randomness in the energy function of one instance (for instance the choice of the graph in random coloring) is usually called quenched disord…”
BackgroundInfluentialAlgorithms 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
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702 · cited 3×
“For one-dimensional systems, MPS are at the basis of many numerical algorithms, most notably the Density Matrix Renormalization Group (DMRG) [254] or the Time Evolving Block Decimation (TEBD) [255].”
MethodSimulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Georges, A., Kotliar, G., Krauth, W., & Rozenberg, M. J. (1996) · Reviews of Modern Physics · doi:10.1103/revmodphys.68.13 · Cited by 6,901
Non-Abelian anyons and topological quantum computation
Nayak, C., Simon, S. H., Stern, A., Freedman, M., & Das Sarma, S. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1083 · Cited by 6,861 · cited 1×
“In the topological quantum computation scheme (see [79] for a review) the quantum states that shall be used as qubits are encoded in non-local (topological) degrees of freedom, that increase their tolerance to local decoherence caused by an imperfect decoupling from the environment.”
BackgroundFactor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 1×
“For each of the interactions ∂a denotes the set of variables that interact through a with the energy term εa; a convenient representation of such an energy function is provided by factor graphs [233], see left panel of Fig.”
MethodQuantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Non-adiabatic crossing of energy levels
Zener, C. (1932) · Proceedings of the Royal Society of London Series A Containing Papers of a Mathematical and Physical Character · doi:10.1098/rspa.1932.0165 · Cited by 4,572 · cited 1×
“The advantage of this simplified formulation is that it is exactly solvable in the limit of an evolution going from s = −∞ to s =∞, the Landau-Zener formula [97, 98] giving the probability P of a diabatic transition to an excited state as P = e−2T πγ 2/b, which has for consequence the necessary condition for an adiaba…”
BackgroundRaussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
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
Edwards, S. F., & Anderson, P. W. (1975) · Journal of Physics F: Metal Physics · doi:10.1088/0305-4608/5/5/017 · Cited by 3,991 · cited 2×
“For spin glasses this was first investigated, after [141], by Sherrington and Kirkpatrick (SK) [142].”
BackgroundMethodQuantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · cited 1×
“Finally, other quantum algorithms have been developed to solve systems of linear equations, see in particular [69, 70].”
BackgroundRapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368
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 24×
“In some models they are of the first order type, thus accompanied by an exponentially small gap that implies an exponentially large running time for the QAA.”
BackgroundMethodInfluentialA 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
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Appearance of Gauge Structure in Simple Dynamical Systems
Wilczek, F., & Zee, A. (1984) · Physical Review Letters · doi:10.1103/physrevlett.52.2111 · Cited by 1,775 · cited 3×
“For the case in which the ground state of Ĥ(s) is degenerate with the same degeneracy for all values of the interpolation parameter s, sufficient and necessary conditions for adiabaticity have recently been proposed in [94], extending the work of Wilczek and Zee [95].”
MethodExperimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738
Born, M., & Fock, V. (1928) · Zeitschrift f�r Physik · doi:10.1007/bf01343193 · Cited by 1,494
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 · cited 1×
“Grover’s algorithm is known to be optimal [67] and has been experimentally tested, see [68] and references therein.”
BackgroundQuantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Quantum computation and decision trees
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.58.915 · Cited by 1,215 · cited 1×
“Let us finally mention the quantum walk strategy (see [81, 82, 83, 84, 85] and references therein) that promotes the classical random walk procedure to explore some configuration space to the quantum level, allowing to exploit interference effects between the paths followed by the walk.”
BackgroundTwo-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069 · cited 1×
“Fortunately it has been shown [56, 57, 58, 59] that any unitary operator can be factorized (with arbitrary precision) as a product of simple operators, called gates in this context, that act only on one or two qubits (this is similar, in the classical case, to the reducibility of any Boolean function as a combination…”
BackgroundUniversal Computation by Quantum Walk
Childs, A. M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.102.180501 · Cited by 1,002 · cited 1×
“Let us finally mention the quantum walk strategy (see [81, 82, 83, 84, 85] and references therein) that promotes the classical random walk procedure to explore some configuration space to the quantum level, allowing to exploit interference effects between the paths followed by the walk.”
BackgroundColloquium : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700 · cited 2×
“Despite its length this review has no pretension of exhaustivity; complementary point of views on the quantum adiabatic algorithm can be found in the reviews [21, 22, 23, 24, 50, 51, 52] and references therein.”
BackgroundMethodInfluentialAlmost Any Quantum Logic Gate is Universal
Lloyd, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.346 · Cited by 690
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632 · cited 1×
“Let us finally mention the quantum walk strategy (see [81, 82, 83, 84, 85] and references therein) that promotes the classical random walk procedure to explore some configuration space to the quantum level, allowing to exploit interference effects between the paths followed by the walk.”
BackgroundQuantum search by local adiabatic evolution
Roland, J., & Cerf, N. J. (2002) · Physical Review A · doi:10.1103/physreva.65.042308 · Cited by 629
Quantum Computer Science: An Introduction
Mermin, N. D. (2007) · doi:10.1017/cbo9780511813870 · Cited by 592
Classical simulation of quantum many-body systems with a tree tensor network
Shi, Y.-Y., Duan, L.-M., & Vidal, G. (2006) · Physical Review A · doi:10.1103/physreva.74.022320 · Cited by 577
Quantum 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
Optimal Control at the Quantum Speed Limit
Caneva, T., Murphy, M., Calarco, T., Fazio, R., Montangero, S., Giovannetti, V., & Santoro, G. E. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.240501 · Cited by 509
On the power of quantum computation
Simon, D. R. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365701 · Cited by 491 · cited 2×
“Simon’s algorithm [10] is given as an input a function f from {0, 1}N to {0, 1}N , with the promise that either f is bijective, or that it is “periodic” in the (unusual) sense that there exists a binary string τ 6= 0 such that f(σ) = f(σ′)⇔ σ = σ′⊕ τ , with again ⊕ the bitwise addition modulo 2.”
BackgroundMethodAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
Mathematical foundation of quantum annealing
Morita, S., & Nishimori, H. (2008) · Journal of Mathematical Physics · doi:10.1063/1.2995837 · Cited by 381 · cited 4×
“The relevant gap is in the latter case the one of the quantum Hamiltonian Ĥ , while in the former case it is the one of the Fokker-Planck generator of the PIMC dynamics on the space of path configurations; we refer to [24, 246] for further analysis of this PIMC annealing.”
BackgroundMethodInfluentialOptimization using quantum mechanics: quantum annealing through adiabatic evolution
Santoro, G. E., & Tosatti, E. (2006) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/39/36/r01 · Cited by 354
Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement
Lanyon, B. P., Weinhold, T. J., Langford, N. K., Barbieri, M., James, D. F. V., Gilchrist, A., & White, A. G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.250505 · Cited by 327 · cited 1×
“Hence the construction of a large quantum computer would have drastic consequences for the security of encrypted communications (see [62, 63, 64, 65] for small-scale experimental demonstrations).”
BackgroundComputing prime factors with a Josephson phase qubit quantum processor
Lucero, E., Barends, R., Chen, Y., Kelly, J., Mariantoni, M., Megrant, A., O’Malley, P., Sank, D., Vainsencher, A., Wenner, J., et al. (2012) · Nature Physics · doi:10.1038/nphys2385 · Cited by 311 · cited 1×
“107 5.6.2 Extracting the gap from the specific heat . . . . . . . . . 108 5.6.3 Imaginary time annealing . . . . . . . . . . . . . . . . . . 108”
InfluentialQuantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space
Poulin, D., Qarry, A., Somma, R., & Verstraete, F. (2011) · Physical Review Letters · doi:10.1103/physrevlett.106.170501 · Cited by 265 · cited 1×
“gives rise to an error in operator norm ‖A‖ ≡ supX,‖X=1‖ ‖AX‖ bounded by [264, 265]:”
How powerful is adiabatic quantum computation?
van Dam, W., Mosca, M., & Vazirani, U. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959902 · Cited by 175 · cited 1×
“Keywords: Quantum spin glasses, Quantum annealing, Quantum adiabatic algorithm, Computational complexity Contents”
MethodZero-temperature quantum phase transition of a two-dimensional Ising spin glass
Rieger, H., & Young, A. P. (1994) · Physical Review Letters · doi:10.1103/physrevlett.72.4141 · Cited by 165
HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
FARHI, E., GOLDSTONE, J., GUTMANN, S., & NAGAJ, D. (2008) · International Journal of Quantum Information · doi:10.1142/s021974990800358x · Cited by 81
Speeding up critical system dynamics through optimized evolution
Caneva, T., Calarco, T., Fazio, R., Santoro, G. E., & Montangero, S. (2011) · Physical Review A · doi:10.1103/physreva.84.012312 · Cited by 78 · cited 1×
“In general it is more difficult to find the best annealing rate for a fixed evolution time T ; such questions are related to quantum optimal control, as presented in [107, 108, 109].”
Background
Cited by
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
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
Evidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
“This phenomenon has been previously observed in the random subcubes model, a specially constructed toy model [43].”
MethodQuantum 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
Metadata
- Authors
- Bapst, V., Foini, L., Krzakala, F., Semerjian, G., & Zamponi, F.
- Venue
- Physics Reports
- Publisher
- Elsevier BV
- Published
- 2013-02
- Volume
- 523
- Issue
- 3
- Pages
- 127-205
- ISSN
- 0370-1573 (ISSN-L)
- OpenAlex
- W2090946156
- Cited by
- 127
- References
- 48
- FWCI
- 6.97
- Type
- journal article
- Language
- en
- Open access
- green
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.