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 accessAbstract
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.
Integrity signals
Registry
Cites
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.
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?
The cited source says what the claim attributes to it.
In the citing paper
“The quantum advantage of QAOA algorithm has been studied in (Farhi and Harrow, 2016), where they showed that the efficient sampling of the output distribution of QAOA, even for the lowest depth case of p = 1 , implies the collapse of the polynomial hierarchy (see Sec. I.A).”
From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Farhi and Harrow, 2016
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
Ladd, T. D., Jelezko, F., Laflamme, R., Nakamura, Y., Monroe, C., & O’Brien, J. L. (2010) · Nature · doi:10.1038/nature08812 · Cited by 3,592
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,374
Quantum annealing in the transverse Ising model
Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789
Self-citationEvidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
Defining and detecting quantum speedup
Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601 · cited 2×
“In fact this procedure can be viewed as a classical algorithm for finding the minimum of −C and is sometimes referred to as SQA for Simulated Quantum Annealing [8, 15,21,31].”
MethodQuantum 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 6×
“With the Quantum Adiabatic Algorithm in optimization mode, we are seeking the maximum of the cost function C given by (2).”
MethodInfluentialSelf-citationAdiabatic Quantum Computation is Equivalent to Standard Quantum Computation
Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447323 · Cited by 457
What is the Computational Value of Finite-Range Tunneling?
Denchev, V. S., Boixo, S., Isakov, S. V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., & Neven, H. (2016) · Physical Review X · doi:10.1103/physrevx.6.031015 · Cited by 399
Unambiguous discrimination between linearly independent quantum states
Chefles, A. (1998) · Physics Letters A · doi:10.1016/s0375-9601(98)00064-4 · Cited by 396
Entanglement in a Quantum Annealing Processor
Lanting, T., Przybysz, A. J., Smirnov, A. Y., Spedalieri, F. M., Amin, M. H., Berkley, A. J., Harris, R., Altomare, F., Boixo, S., Bunyk, P., et al. (2014) · Physical Review X · doi:10.1103/physrevx.4.021041 · Cited by 317
Quantum computing, postselection, and probabilistic polynomial-time
Aaronson, S. (2005) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2005.1546 · Cited by 312
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.080501 · Cited by 299
A Simple Proof that Toffoli and Hadamard are Quantum UniversalPreprint
Aharonov, D. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0301040 · Cited by 259
Thermally assisted quantum annealing of a 16-qubit problem
Dickson, N. G., Johnson, M. W., Amin, M. H. S., Harris, R., Altomare, F., Berkley, A. J., Bunyk, P., Cai, J., Chapple, E. M., Chavez, P., et al. (2013) · Nature Communications · doi:10.1038/ncomms2920 · Cited by 235
Computational multiqubit tunnelling in programmable quantum annealers
Boixo, S., Smelyanskiy, V., Shabani, A., Isakov, S. V., Dykman, M. I., Denchev, V. S., Amin, M. H. S., Smirnov, A. Y., Mohseni, M., & Neven, H. (2016) · Nature Communications · doi:10.1038/ncomms10327 · Cited by 232
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., Shepherd, D. J., et al. (2010) · Cited by 216
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Terhal, B. M., & Divincenzo, D. P. (2004) · Quantum Information and Computation · doi:10.26421/qic4.2-5 · Cited by 171
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011772.2011773 · Cited by 141
A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1412.6062 · Cited by 131
Self-citationFarhi, E., Gosset, D., Hen, I., Sandvik, A. W., Shor, P. W., Young, A. P., & Zamponi, F. (2012) · Physical Review A · doi:10.1103/physreva.86.052334 · Cited by 114
Self-citationSimulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
Crosson, E., & Harrow, A. W. (2016) · CaltechAUTHORS (California Institute of Technology) · Cited by 89
Self-citationDetermining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Fenner, S., Green, F., Homer, S., & Pruim, R. J. (1999) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1999.0485 · Cited by 80
Obstructions to classically simulating the quantum adiabatic algorithm
Hastings, M. B. (2013) · Quantum Information and Computation · doi:10.26421/qic13.11-12-8 · Cited by 55
Beating the random assignment on constraint satisfaction problems of bounded degree
Barak, B., Moitra, A., O’Donnell, R., Raghavendra, P., Regev, O., Steurer, D., Trevisan, L., Vijayaraghavan, A., Witmer, D. K., & Wright, J. C. (2015) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 32
Complexity of simulating constant-depth BosonSampling
Brod, D. J. (2015) · Physical Review A · doi:10.1103/physreva.91.042316 · Cited by 24
The Equivalence of Sampling and Searching
Aaronson, S. (2013) · Theory of Computing Systems · doi:10.1007/s00224-013-9527-3 · Cited by 18
Threshold computation and cryptographic security
Han, Y., Hemaspaandra, L. A., & Thierauf, T. (1993) · Lecture notes in computer science · doi:10.1007/3-540-57568-5_253 · Cited by 9
Computational Complexity of Some Quantum Theories in $1+1$ DimensionsPreprint
Mehraban, S. A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.09243 · Cited by 4
Research works printed but not linked: 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
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385
Probing many-body dynamics on a 51-atom quantum simulator
Bernien, H., Schwartz, S., Keesling, A., Levine, H., Omran, A., Pichler, H., Choi, S., Zibrov, A. S., Endres, M., Greiner, M., et al. (2017) · Nature · doi:10.1038/nature24622 · Cited by 2,460
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Mitarai, K., Negoro, M., Kitagawa, M., & Fujii, K. (2018) · Physical Review A · doi:10.1103/physreva.98.032309 · Cited by 1,639
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Metadata
- Authors
- Farhi, E., & Harrow, A. W.
- Affiliations
- Google (United States) (US)
- Massachusetts Institute of Technology (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2016
- Volume
- 2017
- ISSN
- 2331-8422 (ISSN-L)
- 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
- green
- arxiv.org
- 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
