How many qubits are needed for quantum computational supremacy?

Abstract

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 $\ne$ 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 assumption. Each version is parameterized by a constant $a$ and asserts that certain specific computational problems with input size $n$ require $2^{an}$ time steps to be solved by a non-deterministic algorithm. Then, we choose a specific value of $a$ for each version that we argue makes the assumption plausible, and based on these conjectures we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and boson sampling circuits (i.e. linear optical networks) with 98 photons are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. In the first two cases, we extend this to constant additive error by introducing an average-case fine-grained conjecture.

arXiv comment24 pages + 3 appendices, 8 figures. v2: number of qubits calculation updated and conjectures clarified after becoming aware of Ref. [42]. v3: Section IV and Appendix C added to incorporate additive-error simulations

References in corpus (18)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Computational Supremacy
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• No imminent quantum supremacy by boson sampling
• Instantaneous Quantum Computation
• On the hardness of classically simulating the one clean qubit model
• Architectures for quantum simulation showing a quantum speedup
• A Linear-Optical Proof that the Permanent is #P-Hard
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Anticoncentration theorems for schemes showing a quantum speedup
• Quantum circuits and low-degree polynomials over F_2
• Power of Quantum Computation with Few Clean Qubits
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Complexity Classification of Conjugated Clifford Circuits
• Additive-error fine-grained quantum supremacy

Cited by in corpus (42)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Computational advantage of quantum random sampling
• Theory of quantum system certification: a tutorial
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Biology and medicine in the landscape of quantum advantages
• Random quantum circuits anti-concentrate in log depth
• NISQ Computers: A Path to Quantum Supremacy
• On the statistical complexity of quantum circuits
• Maximal entanglement velocity implies dual unitarity
• Boundaries of quantum supremacy via random circuit sampling
• Classical simulation of linear optics subject to nonuniform losses
• An entanglement perspective on the quantum approximate optimization algorithm
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Efficient verification of Boson Sampling
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• A preprocessing perspective for quantum machine learning classification advantage using NISQ algorithms
• Approaches to Constrained Quantum Approximate Optimization
• Effects of quantum resources on the statistical complexity of quantum circuits
• Classical simulation of quantum circuits by half Gauss sums
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Fast, high precision dynamics in quantum optimal control theory
• A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer
• Quantum supremacy of the many-body fluctuations in the occupations of the excited particle states in a Bose-Einstein-condensed gas
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Error estimation in current noisy quantum computers
• Ion native variational ansatz for quantum approximate optimization
• Self-Adaptive Quantum Kernel Principal Components Analysis for Compact Readout of Chemiresistive Sensor Arrays
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• Quantum computing for data science
• Quantum Extremal Learning
• Wasserstein Complexity of Quantum Circuits
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Additive-error fine-grained quantum supremacy
• Boson sampling with random numbers of photons
• Boson sampling with ultracold atoms in a programmable optical lattice
• Low Depth Virtual Distillation of Quantum Circuits by Deterministic Circuit Decomposition
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Role of overparametrization in quantum approximate optimization
• A Useful Metric for the NISQ Era: Qubit Error Probability and Its Role in Zero Noise Extrapolation