CoChat
Sign Up
PreprintCited by 346Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The DOI matches its DataCite record; 32 of the 34 references it cites were found in a registry or an index.

Quantum Supremacy through the Quantum Approximate Optimization Algorithm

Open access
Farhi, Edward, Harrow, Aram W·2016·arXiv
DOI 10.48550/arxiv.1602.07674arXiv 1602.07674
Open this paper in CoChat — free accountOpen PDF

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1602.07674

Cites

32 of 32 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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?

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

Show all 34 references

Research works printed but not linked: 1

  1. [3][3] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing , 9(4):143-252, 2013, arXiv:1011.3245 . - · arXiv

Cited by

Sorted by citations

Items 301–346 of 346

Related

See all

Metadata

Authors
Farhi, E., & Harrow, A. W.
Affiliations
  • Google (United States) (US)
  • Massachusetts Institute of Technology (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2016
Volume
2017
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1602.07674
arXiv
1602.07674
OpenAlex
W2297565774
Cited by
331
References
34
Citations by year
2026: 1 · 2025: 21 · 2024: 32 · 2023: 47 · 2022: 46 · 2021: 68 · 2020: 40 · 2019: 33 · 2018: 24 · 2017: 18 · 2016: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • Bulletin of the American Physical Society
Funders
  • National Science Foundation (1452616, 1111382, 1218176)
  • Intelligence Advanced Research Projects Activity (D15PC00242)
  • Army Research Office (W911NF-12-1-0486, W911NF)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum advantage, quantum approximate optimization algorithm, adiabatic quantum computation, stoquastic Hamiltonians, gapped Hamiltonians, polynomial hierarchy collapse, 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