Adiabatic quantum computing for random satisfiability problems
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
Abstract
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to 1 for problem sizes feasible to evaluate via simulation on current computers. However, for these sizes the minimum energy gaps of most instances are fairly large, so the good performance scaling seen for small problems may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than for other methods. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.
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
Quantum 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
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
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
DiVincenzo, D. P. (1995) · Science · doi:10.1126/science.270.5234.255 · Cited by 1,651
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×
“Quantum computers [1, 2, 3, 4] can rapidly evaluate all search states of nondeterministic polynomial (NP) problems [5], but appear unlikely to give short worst-case solu-tion times [6].”
BackgroundSteane, A. (1998) · Reports on Progress in Physics · doi:10.1088/0034-4885/61/2/002 · Cited by 1,391
Steane, A. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9708022 · Cited by 1,390
Quantum search by local adiabatic evolution
Roland, J., & Cerf, N. J. (2002) · Physical Review A · doi:10.1103/physreva.65.042308 · Cited by 629
Quantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · cited 3×
“To compare with other algorithms, we use the algorithmically equivalent discrete formulation [14, 15] acting on the amplitude vector initially in the ground state of H (0) , i.e., ψ (0) s = 2 n/ 2 .”
BackgroundMethod
Research works printed but not linked: 10
- G. E. Santoro, 2002, Science, 295, 2427, 10.1126/science.1068774 · DOI · Paper page
- S. Kirkpatrick, 1994, Science, 264, 1297, 10.1126/science.264.5163.1297 · DOI · Paper page
- R. Monasson, 1999, Nature (London), 400, 133, 10.1038/22055 · DOI · Paper page
- T. Hogg, 2000, Phys. Rev. A, 61, 052311, 10.1103/PhysRevA.61.052311 · DOI · Paper page
- J. Frank, 1997, J. Artif. Intell. Res., 7, 249, 10.1613/jair.445 · doi:10.1613/jair.445
- S. F. Edwards, 1976, J. Phys. A, 9, 1595, 10.1088/0305-4470/9/10/011 · DOI · Paper page
- Z. Furedi, 1981, Combinatorica, 1, 233, 10.1007/BF02579329 · DOI · Paper page
- J. K. L. MacDonald, 1933, Phys. Rev., 43, 830, 10.1103/PhysRev.43.830 · DOI
- P.-O. Lowdin, 1965, Phys. Rev., 139, A357, 10.1103/PhysRev.139.A357 · DOI · Paper page
- S. M. Maurer, 2001, Phys. Rev. Lett., 87, 257901, 10.1103/PhysRevLett.87.257901 · DOI
Cited by
Finding 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
Simulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352
Experimental 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
Adiabatic Quantum Simulation of Quantum Chemistry
Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · Scientific Reports · doi:10.1038/srep06603 · Cited by 191
A study of heuristic guesses for adiabatic quantum computation
Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0168-z · Cited by 111
Metadata
- Authors
- Hogg, T.
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2003-02-28
- Volume
- 67
- Issue
- 2
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2031963870
- Cited by
- 93
- References
- 9
- FWCI
- 5.30
- 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: Adiabatic quantum computing for random satisfiability problems. https://app.cochat.ai/papers/10.1103/physreva.67.022314
- The paper
- Hogg, T. (2003). Adiabatic quantum computing for random satisfiability problems. Physical Review A. https://doi.org/10.1103/physreva.67.022314
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.