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.

arXiv comment9 pages, 3 figures

References in corpus (54)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Simulated Quantum Computation of Molecular Energies
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Characterizing Quantum Supremacy in Near-Term Devices
• Fault-tolerant quantum computation with high threshold in two dimensions
• Quantum Computational Supremacy
• Elucidating Reaction Mechanisms on Quantum Computers
• Defining and detecting quantum speedup
• Qubit architecture with high coherence and fast tunable coupling
• Quantum advantage in learning from experiments
• Procedure for systematically tuning up crosstalk in the cross resonance gate
• Simulating quantum computation by contracting tensor networks
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum advantage with shallow circuits
• Complete universal quantum gate set approaching fault-tolerant thresholds with superconducting qubits
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• 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
• Solving strongly correlated electron models on a quantum computer
• What is the Computational Value of Finite Range Tunneling?
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• What limits the simulation of quantum computers?
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Hyper-optimized tensor network contraction
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Quantum computing and the entanglement frontier
• Efficient classical simulation of random shallow 2D quantum circuits
• Solving the sampling problem of the Sycamore quantum circuits
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• 64-Qubit Quantum Circuit Simulation
• Correcting coherent errors with surface codes
• Observation of classical-quantum crossover of 1/f flux noise and its paramagnetic temperature dependence
• Massively parallel quantum computer simulator, eleven years later
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• Efficient classical simulation of noisy random quantum circuits in one dimension
• The surface code with a twist
• Classical Simulation of Quantum Supremacy Circuits
• Simulation of low-depth quantum circuits as complex undirected graphical models
• How many qubits are needed for quantum computational supremacy?
• Classical Simulation of Intermediate-Size Quantum Circuits
• A deceptive step towards quantum speedup detection
• Classical algorithms for quantum mean values
• Quantum Supremacy Is Both Closer and Farther than It Appears
• 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