CoChat
Sign Up
PreprintCited by 96Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsMetaheuristic Optimization Algorithms Research

Classical and Quantum Bounded Depth Approximation Algorithms

Open access
Hastings, M. B.·2019·arXiv
DOI 10.48550/arxiv.1905.07047arXiv 1905.07047
Open this paper in CoChat — free accountOpen PDF

Abstract

We consider some classical and quantum approximate optimization algorithms with bounded depth. First, we define a class of "local" classical optimization algorithms and show that a single step version of these algorithms can achieve the same performance as the single step QAOA on MAX-3-LIN-2. Second, we show that this class of classical algorithms generalizes a class previously considered in the literature, and also that a single step of the classical algorithm will outperform the single-step QAOA on all triangle-free MAX-CUT instances. In fact, for all but $4$ choices of degree, existing single-step classical algorithms already outperform the QAOA on these graphs, while for the remaining $4$ choices we show that the generalization here outperforms it. Finally, we consider the QAOA and provide strong evidence that, for any fixed number of steps, its performance on MAX-3-LIN-2 on bounded degree graphs cannot achieve the same scaling as can be done by a class of "global" classical algorithms. These results suggest that such local classical algorithms are likely to be at least as promising as the QAOA for approximate optimization.

Integrity signals

Registry

DataCite · 10.48550/arxiv.1905.07047

Cites

Statistics

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

Claims the paper makes

We couldn’t retrieve this paper’s full text, 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?

  • For specific instances of the Max-Cut problem, QAOA for p=1 was shown to perform equally well or worse than classical algorithms.

    “For specific instances of the Max-Cut problem, QAOA for p = 1 was shown to perform equally well or worse than classical algorithms (Bravyi et al. , 2019; Hastings, 2019).”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Hastings, 2019

Cited by

Sorted by citations

Authors
Hastings, M. B.
Affiliations
Microsoft (United States) (US)
Corresponding author
Hastings, M. B.
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
19
Issue
13&14
Pages
1116-1140
ISSN
1533-7146 (ISSN-L)
DOI
10.48550/arxiv.1905.07047
arXiv
1905.07047
OpenAlex
W2982304552
Cited by
96
References
0
Citations by year
2026: 7 · 2025: 9 · 2024: 11 · 2023: 8 · 2022: 22 · 2021: 22 · 2020: 14 · 2019: 3
FWCI
6.96
Type
journal article
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • Quantum Information and Computation (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
quantum approximate optimization algorithm, MaxCut, triangle-free graphs, bounded degree graphs, local optimization algorithms, global optimization algorithms, quantum annealing, combinatorial optimization

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