A Caltech Library Service

How many qubits are needed for quantum computational supremacy?

Dalzell, Alexander M. and Harrow, Aram W. and Koh, Dax Enshan and La Placa, Rolando L. (2020) How many qubits are needed for quantum computational supremacy? Quantum, 4 . Art. No. 264. ISSN 2521-327X. doi:10.22331/q-2020-05-11-264.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (PH) does not collapse, a stronger version of the statement that P≠NP, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH(a) and per-int-NSETH(b) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in n variables over F₂ or the permanent of an n×n integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires 2^(cn) time steps, where c∈{a,b}. A third conjecture poly3-ave-SBSETH(a′) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class SBP. We analyze evidence for these conjectures and argue that they are plausible when a=1/2, b=0.999 and a′=1/2. Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring 10⁴ to 10⁷ gates.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Dalzell, Alexander M.0000-0002-3756-8500
Harrow, Aram W.0000-0003-3220-7682
Koh, Dax Enshan0000-0002-8968-591X
La Placa, Rolando L.0000-0001-7867-226X
Additional Information:© 2020 This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. Published: 2020-05-11. We are grateful to Ashley Montanaro for important suggestions and conversations about degree-3 polynomials and the computational problem underlying this work. We would also like to thank Virginia Williams and Ryan Williams for useful discussions, and for pointing out Ref. [42] and correcting an error in an earlier version of the paper. Finally, we acknowledge Richard Kueng for suggesting the proof strategy in Lemma 9, as well as Tomoyuki Morimae and Suguru Tamaki for comments on a draft of this paper. AMD acknowledges support from the Undergraduate Research Opportunities Program (UROP) at MIT, the Dominic Orr Fellowship at Caltech, and the National Science Foundation Graduate Research Fellowship under Grant No. DGE-1745301. AWH was funded by NSF grants CCF-1452616 and CCF-1729369, ARO contract W911NF-17-1-0433 and the MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert space. DEK was supported by the National Science Scholarship from the Agency for Science, Technology and Research (A*STAR) and Enabling Practical-scale Quantum Computation (EPiQC), a National Science Foundation (NSF) Expedition in Computing, under grant CCF-1729369. RLP was funded by the MIT School of Science Fellowship, the MIT Department of Physics, and the MIT-IBM Watson AI Lab.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Dominic Orr Graduate FellowshipUNSPECIFIED
NSF Graduate Research FellowshipDGE-1745301
Army Research Office (ARO)W911NF-17-1-0433
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Record Number:CaltechAUTHORS:20200605-083021823
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103727
Deposited By: Tony Diaz
Deposited On:05 Jun 2020 15:50
Last Modified:16 Nov 2021 18:24

Repository Staff Only: item control page