CoChat
Sign Up
PreprintCited by 218Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum Information and Cryptography

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Open access
Aaronson, Scott, Chen, Lijie·2016·arXiv
DOI 10.48550/arxiv.1612.05903arXiv 1612.05903
Open this paper in CoChat — free accountOpen PDF

Abstract

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the the Quantum AI group at Google. We show that there's a natural hardness assumption, which has nothing to do with sampling, yet implies that no efficient classical algorithm can pass a statistical test that the quantum sampling procedure's outputs do pass. Compared to previous work, the central advantage is that we can now talk directly about the observed outputs, rather than about the distribution being sampled. Second, in an attempt to refute our hardness assumption, we give a new algorithm, for simulating a general quantum circuit with n qubits and m gates in polynomial space and m^O(n) time. We then discuss why this and other known algorithms fail to refute our assumption. Third, resolving an open problem of Aaronson and Arkhipov, we show that any strong quantum supremacy theorem--of the form "if approximate quantum sampling is classically easy, then PH collapses"--must be non-relativizing. Fourth, refuting a conjecture by Aaronson and Ambainis, we show that the Fourier Sampling problem achieves a constant versus linear separation between quantum and randomized query complexities. Fifth, we study quantum supremacy relative to oracles in P/poly. Previous work implies that, if OWFs exist, then quantum supremacy is possible relative to such oracles. We show that some assumption is needed: if SampBPP=SampBQP and NP is in BPP, then quantum supremacy is impossible relative to such oracles.

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.1612.05903

Cites

Statistics

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?

  • 50 qubits is a significant milestone because it is beyond what can be simulated by brute force using the most powerful existing digital supercomputers.

    “50 qubits is a significant milestone, because that's beyond what can be simulated by brute force using the most powerful existing digital supercomputers.”

    From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [12]

    Section 1.2 (p. 4) describes 40–50 qubits as a range where classical simulation is difficult but not impossible, contrary to the claim that 50 qubits is beyond brute-force simulation. Section 1.3 (p. 7) also describes a classical simulation method and says its 2^n time is reasonable for a planned setup with roughly 40 or 50 qubits. (LLM, conf=0.86)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 48 · Cited by 218

Research works printed but not linked: 58

  1. [AA13] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Theory of Computing , 9(4):143-252, 2013. Earlier version in Proc. ACM STOC'2011. ECCC TR10170, arXiv:1011.3245. · arXiv
  2. [AA15] Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing , pages 307-316. ACM, 2015.
  3. [Aar10] S. Aaronson. BQP and the polynomial hierarchy. In Proc. ACM STOC , 2010. arXiv:0910.4698. · arXiv
  4. [Aar14] Scott Aaronson. The equivalence of sampling and searching. Theory of Computing Systems , 55(2):281-298, 2014.
  5. [AB09] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009.
  6. [ABDK15] Scott Aaronson, Shalev Ben-David, and Robin Kothari. Separations in query complexity using cheat sheets. arXiv preprint arXiv:1511.01937 , 2015. · arXiv
  7. [ABKM16] Scott Aaronson, Adam Bouland, Greg Kuperberg, and Saeed Mehraban. The computational complexity of ball permutations. arXiv preprint arXiv:1610.06646 , 2016. · arXiv
  8. [ABO97] D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proc. ACM STOC , pages 176-188, 1997. quant-ph/9906129. · arXiv
  9. [ABOE08] D. Aharonov, M. Ben-Or, and E. Eban. Interactive proofs for quantum computations. arXiv:0810.5375, 2008. · arXiv
  10. [Amb05] Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing , 1(1):37-46, 2005.
  11. [AS04] S. Aaronson and Y. Shi. Quantum lower bounds for the collision and the element distinctness problems. J. of the ACM , 51(4):595-605, 2004.
  12. [AW09] S. Aaronson and A. Wigderson. Algebrization: a new barrier in complexity theory. ACM Trans. on Computation Theory , 1(1), 2009. Earlier version in Proc. ACM STOC'2008.
  13. [BBBV97] C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput. , 26(5):1510-1523, 1997. quant-ph/9701001. · arXiv
  14. [BFK09] A. Broadbent, J. Fitzsimons, and E. Kashefi. Universal blind quantum computation. In Proc. IEEE FOCS , 2009. arXiv:0807.4154. · arXiv
  15. [BG16] Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by clifford gates. arXiv preprint arXiv:1601.07601 , 2016. · arXiv
  16. [BGS75] Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P=?NP question. SIAM Journal on computing , 4(4):431-442, 1975.
  17. [BHH16] Fernando GSL Brand˜ ao, Aram W Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics , 346(2):397-434, 2016.
  18. [BIS + 16] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. arXiv preprint arXiv:1608.00263 , 2016. · arXiv
  19. [BJS10] M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. London , A467(2126):459-472, 2010. arXiv:1005.1407. · arXiv
  20. [BL95] Dan Boneh and Richard J Lipton. Quantum cryptanalysis of hidden linear functions. In Annual International Cryptology Conference , pages 424-437. Springer, 1995.
  21. [BMS15] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. arXiv preprint arXiv:1504.07999 , 2015. · arXiv
  22. [BMS16] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. arXiv preprint arXiv:1610.01808 , 2016. · arXiv
  23. [BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput. , 26(5):14111473, 1997. Earlier version in Proc. ACM STOC'1993.
  24. [Che16] Lijie Chen. A note on oracle separations for BQP. arXiv preprint arXiv:1605.00619 , 2016. · arXiv
  25. [CHS + 15] Jacques Carolan, Christopher Harrold, Chris Sparrow, Enrique Mart´ ın-L´ opez, Nicholas J Russell, Joshua W Silverstone, Peter J Shadbolt, Nobuyuki Matsuda, Manabu Oguma, Mikitaka Itoh, Graham D Marshall, Mark G Thompson, Jonathan C F Matthews, Toshikazu Hashimoto, Jeremy L O'Brien, and Anthony Laing. Universal linear optics. Science , 349(6249):711-716, 2015.
  26. [FFKL03] Stephen Fenner, Lance Fortnow, Stuart A Kurtz, and Lide Li. An oracle builders toolkit. Information and Computation , 182(2):95-136, 2003.
  27. [FH16] Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674 , 2016. · arXiv
  28. [FR99] L. Fortnow and J. Rogers. Complexity limitations on quantum computation. J. Comput. Sys. Sci. , 59(2):240-252, 1999. cs.CC/9811023. · arXiv
  29. [Fuj16] Keisuke Fujii. Noise threshold of quantum supremacy. arXiv preprint arXiv:1610.03632 , 2016. · arXiv
  30. [GGM86] O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. J. of the ACM , 33(4):792-807, 1986. Earlier version in Proc. IEEE FOCS'1984, pp. 464-479.
  31. [GL89] Oded Goldreich and Leonid A Levin. A hard-core predicate for all one-way functions. In Proceedings of the twenty-first annual ACM symposium on Theory of computing , pages 2532. ACM, 1989.
  32. [Has86] Johan Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the eighteenth annual ACM symposium on Theory of computing , pages 6-20. ACM, 1986.
  33. [HILL99] J. H˚ astad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM J. Comput. , 28(4):1364-1396, 1999.
  34. [IW97] R. Impagliazzo and A. Wigderson. P=BPP unless E has subexponential circuits: derandomizing the XOR Lemma. In Proc. ACM STOC , pages 220-229, 1997.
  35. [Kal11] Gil Kalai. How quantum computers fail: quantum codes, correlations in physical systems, and noise accumulation. arXiv preprint arXiv:1106.0485 , 2011. · arXiv
  36. [KBF + 15] J Kelly, R Barends, AG Fowler, A Megrant, E Jeffrey, TC White, D Sank, JY Mutus, B Campbell, Yu Chen, et al. State preservation by repetitive error detection in a superconducting quantum circuit. Nature , 519(7541):66-69, 2015.
  37. [Kut05] Samuel Kutin. Quantum lower bound for the collision problem with small range. Theory of Computing , 1(1):29-36, 2005.
  38. [Lev03] Leonid A Levin. The tale of one-way functions. Problems of Information Transmission , 39(1):92-103, 2003.
  39. [LR88] Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing , 17(2):373-386, 1988.
  40. [MFF14] Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical review letters , 112(13):130502, 2014.
  41. [MS08] Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing , 38(3):963-981, 2008.
  42. [NW94] Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of computer and System Sciences , 49(2):149-167, 1994.
  43. [PGHAG15] Borja Peropadre, Gian Giacomo Guerreschi, Joonsuk Huh, and Al´ an Aspuru-Guzik. Microwave boson sampling. arXiv preprint arXiv:1510.08064 , 2015. · arXiv
  44. [Pre12] John Preskill. Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813 , 2012. · arXiv
  45. [RR97] A. A. Razborov and S. Rudich. Natural proofs. J. Comput. Sys. Sci. , 55(1):24-35, 1997. Earlier version in Proc. ACM STOC'1994, pp. 204-213.
  46. [RST15] Benjamin Rossman, Rocco A Servedio, and Li-Yang Tan. An average-case depth hierarchy theorem for boolean circuits. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on , pages 1030-1048. IEEE, 2015.
  47. [Rud16] Terry Rudolph. Why I am optimistic about the silicon-photonic route to quantum computing. arXiv preprint arXiv:1607.08535 , 2016. · arXiv
  48. [Sav70] W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Sys. Sci. , 4(2):177-192, 1970.
  49. [SG04] Rocco A Servedio and Steven J Gortler. Equivalences and separations between quantum and classical learnability. SIAM Journal on Computing , 33(5):1067-1092, 2004.
  50. [Sha92] A. Shamir. IP=PSPACE. J. of the ACM , 39(4):869-877, 1992. Earlier version in Proc. IEEE FOCS'1990, pp. 11-15.
  51. [Sho97] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. , 26(5):1484-1509, 1997. Earlier version in Proc. IEEE FOCS'1994. quant-ph/9508027. · arXiv
  52. [SV03] Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM (JACM) , 50(2):196-249, 2003.
  53. [TD04] B. M. Terhal and D. P. DiVincenzo. Adaptive quantum computation, constant-depth circuits and Arthur-Merlin games. Quantum Information and Computation , 4(2):134-145, 2004. quant-ph/0205133. · arXiv
  54. [Tod91] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. , 20(5):865-877, 1991. Earlier version in Proc. IEEE FOCS'1989, pp. 514-519.
  55. [Vap98] Vladimir Naumovich Vapnik. Statistical learning theory , volume 1. Wiley New York, 1998.
  56. [Yao85] Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) , 1985.
  57. [Zha12] Mark Zhandry. How to construct quantum random functions. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , pages 679-687. IEEE, 2012.
  58. [Zha16] Mark Zhandry. A note on quantum-secure prps. arXiv preprint arXiv:1611.05564 , 2016. · arXiv

Authors
Aaronson, S., & Chen, L.
Affiliations
  • The University of Texas at Austin (US)
  • Tsinghua University (CN)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2016
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1612.05903
arXiv
1612.05903
OpenAlex
W2949719769
Cited by
218
References
48
Citations by year
2026: 5 · 2025: 13 · 2024: 22 · 2023: 18 · 2022: 24 · 2021: 43 · 2020: 44 · 2019: 21 · 2018: 16 · 2017: 12
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • Leibniz international proceedings in informatics (cc-by)
  • Open Collections
Funders
  • U.S. Department of Defense
  • Simons Foundation
  • National Natural Science Foundation of China (61361136003)
  • Tsinghua University
  • National Key Research and Development Program of China (2011CBA00301, 2011CBA00300, 2011CBA00301, 61361136003, 2011CBA00300)
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 › Quantum Information and Cryptography
Keywords
quantum advantage, oracle separation, polynomial hierarchy, quantum query complexity, random quantum circuits, approximate sampling, computational complexity

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