Quantum Supremacy and the Complexity of Random Circuit Sampling

Abstract

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Characterizing Quantum Supremacy in Near-Term Devices
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• Boson Sampling on a Photonic Chip
• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Random Quantum Circuits are Approximate 2-designs
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• No imminent quantum supremacy by boson sampling
• On the hardness of classically simulating the one clean qubit model
• Anticoncentration theorems for schemes showing a quantum speedup
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• On the Complexity of Random Quantum Computations and the Jones Polynomial

Cited by in corpus (175)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Strong quantum computational advantage using a superconducting quantum processor
• Logical quantum processor based on reconfigurable atom arrays
• Theory of the phase transition in random unitary circuits with measurements
• Random Quantum Circuits
• The randomized measurement toolbox
• Quantum certification and benchmarking
• Hybrid integration methods for on-chip quantum photonics
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Hyper-optimized tensor network contraction
• Preparing random states and benchmarking with many-body quantum chaos
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Quantum advantage with noisy shallow circuits in 3D
• Theory of quantum system certification: a tutorial
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• A general framework for randomized benchmarking
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Exact emergent quantum state designs from quantum chaotic dynamics
• Phase transition in Random Circuit Sampling
• Emergent quantum state designs from individual many-body wavefunctions
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Quantum Machine Learning: from physics to software engineering
• Variational Quantum Unsampling on a Quantum Photonic Processor
• Theoretical and Experimental Perspectives of Quantum Verification
• Classical Simulation of Quantum Supremacy Circuits
• A volumetric framework for quantum computer benchmarks
• Random quantum circuits anti-concentrate in log depth
• Dynamical purification and the emergence of quantum state designs from the projected ensemble
• A polynomial-time classical algorithm for noisy random circuit sampling
• How many qubits are needed for quantum computational supremacy?
• NISQ Computers: A Path to Quantum Supremacy
• Variational Benchmarks for Quantum Many-Body Problems
• Computational power of one- and two-dimensional dual-unitary quantum circuits
• Nonstabilizerness determining the hardness of direct fidelity estimation
• Quantum coding with low-depth random circuits
• Classical algorithms for quantum mean values
• Subspace Variational Quantum Simulator
• Contracting projected entangled pair states is average-case hard
• Probabilistic Simulation of Quantum Circuits with the Transformer
• Classical algorithm for simulating experimental Gaussian boson sampling
• Variational inference with a quantum computer
• Boundaries of quantum supremacy via random circuit sampling
• Classically-Verifiable Quantum Advantage from a Computational Bell Test
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Classical simulation of lossy boson sampling using matrix product operators
• Efficient classical simulation of Clifford circuits with nonstabilizer input states
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Variational Quantum Algorithm for Non-equilibrium Steady States
• Sample complexity of device-independently certified "quantum supremacy"
• Simulating the Sycamore quantum supremacy circuits
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Expressibility and trainability of parameterized analog quantum systems for machine learning applications
• Physical-Layer Supervised Learning Assisted by an Entangled Sensor Network
• Quantum Entropy and Central Limit Theorem
• Quantum circuits for exact unitary $t$-designs and applications to higher-order randomized benchmarking
• Noise and the frontier of quantum supremacy
• Quantum Phase Recognition via Quantum Kernel Methods
• A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models
• Variational quantum process tomography
• Closing gaps of a quantum advantage with short-time Hamiltonian dynamics
• Quantum-Noise-Driven Generative Diffusion Models
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Finite-time teleportation phase transition in random quantum circuits
• The computational power of random quantum circuits in arbitrary geometries
• Quantum Sampling Algorithms for Near-Term Devices
• Measurement induced entanglement transition in two dimensional shallow circuit
• Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Scrambling and quantum chaos indicators from long-time properties of operator distributions
• Energy-Consumption Advantage of Quantum Computation
• Bell sampling from quantum circuits
• Crystalline Quantum Circuits
• Spoofing cross entropy measure in boson sampling
• Self-testing of a single quantum device under computational assumptions
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Hilbert space delocalization under random unitary circuits
• Information processing at the speed of light
• Growth of genuine multipartite entanglement in random unitary circuits
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Classical models may be a better explanation of the Jiuzhang 1.0 Gaussian Boson Sampler than its targeted squeezed light model
• Random-matrix models of monitored quantum circuits
• Quantum algorithms for scientific computing
• Depth-efficient proofs of quantumness
• Pauli path simulations of noisy quantum circuits beyond average case
• Theory of Ergodic Quantum Processes
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Volumetric Benchmarking of Error Mitigation with Qermit
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• The principle of majorization: application to random quantum circuits
• Quantum Algorithms for Inverse Participation Ratio Estimation in multi-qubit and multi-qudit systems
• On the sampling complexity of open quantum systems
• Complexity of Fermionic Dissipative Interactions and Applications to Quantum Computing
• Simulation of Quantum Computing on Classical Supercomputers
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Quantum supremacy and quantum phase transitions
• Unitary k-designs from random number-conserving quantum circuits
• Robust sparse IQP sampling in constant depth
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Fault-tolerant quantum speedup from constant depth quantum circuits
• A game of quantum advantage: linking verification and simulation
• Exploring Shallow-Depth Boson Sampling: Towards Scalable Quantum Supremacy
• Fermionic Magic Resources of Quantum Many-Body Systems
• Quantum advantage from energy measurements of many-body quantum systems
• Verifiable measurement-based quantum random sampling with trapped ions
• Fault-tolerant compiling of classically hard IQP circuits on hypercubes
• Quantum supremacy in driven quantum many-body systems
• Forging quantum data: classically defeating an IQP-based quantum test
• Quantum complexity phase transitions in monitored random circuits
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• On Certified Randomness from Fourier Sampling or Random Circuit Sampling
• Theory of Quantum Path Computing with Fourier Optics and Future Applications for Quantum Supremacy, Neural Networks and Nonlinear Schrödinger Equations
• Non-Randomness of Google's Quantum Supremacy Benchmark
• Anticoncentration and State Design of Doped Real Clifford Circuits and Tensor Networks
• Classical simulability of Clifford+T circuits with Clifford-augmented matrix product states
• Deviations from the Porter-Thomas Distribution due to Nonstatistical $\gamma$ Decay below the ${}^{150}$Nd Neutron Separation Threshold
• Non-Clifford Cost of Random Unitaries
• Non-Haar random circuits form unitary designs as fast as Haar random circuits
• Locality-aware Pauli-based computation for local magic state preparation
• Architectures and random properties of symplectic quantum circuits
• Classical simulation of bosonic linear-optical random circuits beyond linear light cone
• High performance Boson Sampling simulation via data-flow engines
• Applications of Certified Randomness
• Efficient approximation of experimental Gaussian boson sampling
• Additive-error fine-grained quantum supremacy
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Benchmarking the performance of a high-Q cavity qudit using random unitaries
• Unconditionally separating noisy ${\mathsf{QNC}}^0$ from bounded polynomial threshold circuits of constant depth
• Pseudochaotic Many-Body Dynamics as a Pseudorandom State Generator
• On Computational Complexity of Unitary and State Design Properties
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Estimating the Number of States via the Rodeo Algorithm for Quantum Computation
• Error Mitigation Thresholds in Noisy Random Quantum Circuits
• Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models
• Simulating quantum computation: how many "bits" for "it"?
• Pseudorandom Unitaries in the Haar Random Oracle Model
• Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits
• Boson sampling with ultracold atoms in a programmable optical lattice
• Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudo-Magic States
• Low overhead universality and quantum supremacy using only $Z$-control
• Classical simulation of circuits with realistic odd-dimensional Gottesman-Kitaev-Preskill states
• On computational complexity and average-case hardness of shallow-depth boson sampling
• Sampling and the complexity of nature
• Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity
• Quantum Circuit Unoptimization
• Impossibility of blind quantum sampling for classical client
• Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Quantum computational advantage of noisy boson sampling with partially distinguishable photons
• k-Contextuality as a Heuristic for Memory Separations in Learning
• Classical algorithms for measurement-adaptive Gaussian circuits
• Measurement-induced entanglement in noisy 2D random circuits
• Approximate Quantum Error Correction with 1D Log-Depth Circuits
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Quantum Oracle Separations from Complex but Easily Specified States
• Counting with the quantum alternating operator ansatz
• Hardware-efficient random circuits to classify noise in a multi-qubit system
• Distribution of Non-Locality On Quantum Random Circuits
• Hardness of efficiently generating ground states in postselected quantum computation
• Quantum Cryptography and Meta-Complexity
• Quantum coherence and counterdiabatic quantum computing
• Cryptographic Characterization of Quantum Advantage
• Polynomial speedup in Torontonian calculation by a scalable recursive algorithm
• Unraveling Rodeo Algorithm Through the Zeeman Model
• Challenges and opportunities in the supervised learning of quantum circuit outputs