A polynomial-time classical algorithm for noisy random circuit sampling
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
Unbiased Hamiltonian Simulation by Reversing Trotter Error Dynamics
PTER removes Trotter errors in quantum Hamiltonian simulation via quasi-probabilistic reversal of the error dynamics, producing unbiased results with constant overhead.
-
Noise-induced Simulability Transition from Operator Scrambling
Above a critical noise strength, operator scrambling in random circuits is suppressed leading to classical simulability; below it, simulation stays exponentially hard.
-
General framework for anticoncentration and linear cross-entropy benchmarking in photonic quantum advantage experiments
A representation-theoretic framework computes LXEB scores and proves anticoncentration for Fock-state Boson Sampling in the saturated regime using irrep decompositions of bosonic spaces.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.