Boundaries of quantum supremacy via random circuit sampling

Abstract

Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling, that is beyond the practical reach of modern supercomputers. We examine the constraints of the observed quantum runtime advantage in an extrapolation to circuits with a larger number of qubits and gates. Due to the exponential decrease of the experimental fidelity with the number of qubits and gates, we demonstrate for current fidelities a theoretical classical runtime advantage for circuits deeper than a few hundred gates, while quantum runtimes for cross-entropy benchmarking limit the region of a quantum advantage to a few hundred qubits. However, the quantum runtime advantage boundary in circuit width and depth grows exponentially with respect to reduced error rates, and our work highlights the importance of continued progress along this line. Extrapolations of measured error rates suggest that the limiting circuit size for which a computationally feasible quantum runtime advantage in cross-entropy benchmarking can be achieved approximately coincides with expectations for early implementations of the surface code and other quantum error correction methods. Thus the boundaries of quantum supremacy via random circuit sampling may fortuitously coincide with the advent of scalable, error corrected quantum computing in the near term.

9 pages, 3 figures

References in corpus (23)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Simulated Quantum Computation of Molecular Energies
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Fault-tolerant quantum computation with high threshold in two dimensions
• Quantum advantage in learning from experiments
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• What limits the simulation of quantum computers?
• Hyper-optimized tensor network contraction
• Quantum computing and the entanglement frontier
• Efficient classical simulation of random shallow 2D quantum circuits
• Solving the sampling problem of the Sycamore quantum circuits
• Observation of classical-quantum crossover of 1/f flux noise and its paramagnetic temperature dependence
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Classical Simulation of Quantum Supremacy Circuits
• Simulation of low-depth quantum circuits as complex undirected graphical models
• Classical algorithms for quantum mean values
• Robust entanglement renormalization on a noisy quantum computer
• On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
• Noise-resilient preparation of quantum many-body ground states

Cited by in corpus (23)

• Computational advantage of quantum random sampling
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Beyond-classical computation in quantum simulation
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Phase transition in Random Circuit Sampling
• Classical Simulation of Quantum Supremacy Circuits
• NISQ Computers: A Path to Quantum Supremacy
• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Demonstration of algorithmic quantum speedup
• Simulating the Sycamore quantum supremacy circuits
• Benchmarking Quantum Computer Simulation Software Packages: State Vector Simulators
• Information processing at the speed of light
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Benchmarking quantum gates and circuits
• Lifetime-based Optimization for Simulating Quantum Circuits on a New Sunway Supercomputer
• Minimal informationally complete measurements for probability representation of quantum dynamics
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Projected ensemble in a system with conserved charges with local support
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Virtual Z gates and symmetric gate compilation
• Low overhead universality and quantum supremacy using only $Z$-control
• Implementation of Tensor Network Simulation TN-Sim under NWQ-Sim
• Structural encoding with classical codes for computational-basis bit-flip correction in the early fault-tolerant regime