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…”
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective. https://app.cochat.ai/papers/10.1016/j.physrep.2012.10.002
- The paper
- Bapst, V., Foini, L., Krzakala, F., Semerjian, G., & Zamponi, F. (2013). The quantum adiabatic algorithm applied to random optimization problems: The quantum spin glass perspective. Physics Reports. https://doi.org/10.1016/j.physrep.2012.10.002
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.