A polynomial-time classical algorithm for noisy random circuit sampling

Abstract

We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments.

27 pages, 2 figures

References in corpus (3)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Strong quantum computational advantage using a superconducting quantum processor
• A polynomial-time classical algorithm for noisy random circuit sampling

Cited by in corpus (41)

• A Race Track Trapped-Ion Quantum Processor
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Beyond-classical computation in quantum simulation
• Phase transition in Random Circuit Sampling
• Does provable absence of barren plateaus imply classical simulability?
• A polynomial-time classical algorithm for noisy random circuit sampling
• Variational Benchmarks for Quantum Many-Body Problems
• Classical algorithm for simulating experimental Gaussian boson sampling
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Artificial Intelligence for Quantum Computing
• Bell sampling from quantum circuits
• Spoofing cross entropy measure in boson sampling
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Classically estimating observables of noiseless quantum circuits
• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Pauli path simulations of noisy quantum circuits beyond average case
• Quantum many-body simulations with PauliStrings.jl
• Noise-induced shallow circuits and absence of barren plateaus
• On the Pauli Spectrum of QAC0
• Robust sparse IQP sampling in constant depth
• Learning a quantum channel from its steady-state
• Quantum Ruzsa Divergence to Quantify Magic
• Verifiable measurement-based quantum random sampling with trapped ions
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Designs from magic-augmented Clifford circuits
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Fast pseudorandom quantum state generators via inflationary quantum gates
• Calibrating quantum gates up to 52 qubits in a superconducting processor
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Survey on Computational Applications of Tensor Network Simulations
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• Macroproperties vs. Microstates in the Classical Simulation of Critical Phenomena in Quench Dynamics of 1D Ising Models
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Artificial intelligence for representing and characterizing quantum systems
• A graph-theoretic approach to chaos and complexity in quantum systems
• Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
• Sampling (noisy) quantum circuits through randomized rounding
• Utility-Scale Quantum State Preparation: Classical Training using Pauli Path Simulation