CoChat
Sign Up
PreprintCited by 131Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum many-body systems

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

Open access
Farhi, Edward, Goldstone, Jeffrey, Gutmann, Sam·2014·arXiv
DOI 10.48550/arxiv.1412.6062arXiv 1412.6062
Open this paper in CoChat — free accountOpen PDF

Abstract

We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of linear equations each of which contains exactly three boolean variables and each equation says that the sum of the variables mod 2 is 0 or is 1. Every variable is in no more than D equations. A random string will satisfy 1/2 of the equations. We show that the level one QAOA will efficiently produce a string that satisfies $\left(\frac{1}{2} + \frac{1}{101 D^{1/2}\, l n\, D}\right)$ times the number of equations. A recent classical algorithm achieved $\left(\frac{1}{2} + \frac{constant}{D^{1/2}}\right)$. We also show that in the typical case the quantum computer will output a string that satisfies $\left(\frac{1}{2}+ \frac{1}{2\sqrt{3e}\, D^{1/2}}\right)$ times the number of equations.

Integrity signals

Registry

DataCite · 10.48550/arxiv.1412.6062

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?

  • Farhi, Goldstone and Gutmann gave the first quantum algorithm for a combinatorial task of simultaneously satisfying many linear equations of a certain form that outperformed the best efficient classical algorithm known in terms of accuracy, measured by the fraction of equations satisfied.

    “Recent work of Farhi, Goldstone and Gutmann 24 gave the fi rst quantum algorithm for a combinatorial task (simultaneously satisfying many linear equations of a certain form) which outperformed the best ef fi cient classical algorithm known in terms of accuracy; in this case, measured by the fraction of equations satis fi ed.”

    From Quantum algorithms: an overview (2016) · cites this paper as [24]

Cited by

Sorted by citations

Authors
Farhi, E., Goldstone, J., & Gutmann, S.
ORCID
Farhi, Edward
Venue
arXiv
Publisher
arXiv
Published
2014
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1412.6062
arXiv
1412.6062
OpenAlex
W1752349928
Cited by
131
References
0
Citations by year
2026: 2 · 2025: 3 · 2024: 16 · 2023: 14 · 2022: 20 · 2021: 19 · 2020: 18 · 2019: 18 · 2018: 8 · 2017: 7 · 2016: 4 · 2015: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • 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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum approximate optimization algorithm, combinatorial optimization, quantum algorithms, satisfiability

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