CoChat
Sign Up
Cited by 110Quantum Computing Algorithms and ArchitectureQuantum many-body systemsComplexity and Algorithms in Graphs

The quantum adiabatic optimization algorithm and local minima

Reichardt, Ben W.·2004·Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
DOI 10.1145/1007352.1007428
Open this paper in CoChat — free account

Abstract

The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.

Integrity signals

Registry

Crossref · 10.1145/1007352.1007428

Cites

17 of 17 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

  • Many interesting problems have been found with an exponentially vanishing gap with increasing problem sizes.

    “Unfortunately, many interesting problems have been found with an exponentially vanishing gap with increasing problem sizes [183-185].”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [185]

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Reichardt, B. W.
Affiliations
University of California, Berkeley (US)
Corresponding author
Reichardt, Ben W.
ORCID
Reichardt, Ben W.
Venue
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
Publisher
ACM
Published
2004-06-13
Pages
502-510
DOI
10.1145/1007352.1007428
OpenAlex
W2040469943
Cited by
110
References
17
Citations by year
2026: 2 · 2025: 6 · 2024: 5 · 2023: 3 · 2022: 2 · 2021: 10 · 2020: 8 · 2019: 8 · 2018: 5 · 2017: 4 · 2016: 7 · 2015: 8 · 2014: 7 · 2013: 2 · 2012: 2
FWCI
3.46
Type
conference paper
Language
en
Open access
closed
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
ACM Symposium on Theory of Computing (STOC) (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
local minima, adiabatic theorem, spectral gap, transverse field, SAT problem, computational complexity, ground state energy

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