REVIEW 10 cited by
A polynomial-time classical algorithm for noisy quantum circuits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g. the computational basis). Our approach is based upon the intuition that noise exponentially damps non-local correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by only keeping track of the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasi-polynomial time, so long as the distribution anti-concentrates. A number of practical implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: for constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
Forward citations
Cited by 10 Pith papers
-
Interplay of resources for universal continuous-variable quantum computing
The authors define symplectic coherence, show that circuits with little of it can be classically simulated, and map this resource to coherence in discrete-variable quantum computing via the GKP encoding.
-
Syndrome aware mitigation of logical errors
Conditioning logical error mitigation on the measured error-correcting syndromes cuts sampling overhead exponentially and can make error correction useful above its standard pseudo-threshold.
-
Spectral properties and coding transitions of Haar-random quantum codes
Haar-random quantum codes lose correctability exactly at the hashing bound, and the spectral band structure predicts a higher detection threshold for postselected error correction.
-
Pitfalls when tackling the exponential concentration of parameterized quantum models
Exponentially concentrated measurement outcomes are statistically indistinguishable from fixed noise after polynomial shots, so classical post-processing cannot fix them, and common proposed remedies do not escape this.
-
Integrals of motion as slow modes in dissipative many-body operator dynamics
Weakly noisy quantum dynamics makes small-support integrals of motion appear as the slowest-decaying operators, which can be used to identify exact and approximate conservation laws.
-
Improved Quantum Computation using Operator Backpropagation
By classically backpropagating an observable through part of a quantum circuit, the authors reduce the quantum circuit depth and achieve lower error for expectation values in a 127-qubit XY-model simulation.
-
Gram-Certified Resource Continuation for Structured Quantum Representation Audits
A coarse spectral flag that is δ_c-suboptimal transfers to a fine isometrically lifted problem with suboptimality at most δ_c+2ε, certified by a 2m amplitude Gram matrix, and continuation is justified only when mismat...
-
Characterizing Pauli Propagation via Operator Complexity
Truncation error in Pauli propagation is bounded by Operator Stabilizer Rényi entropy, giving a Top-K budget formula, and the 1D XY chain's evolved local operator has O(s²) Pauli terms.
-
Pauli Propagation: A Computational Framework for Simulating Quantum Systems
Pauli propagation, a classical method that evolves Pauli operators through quantum circuits, is presented as a unified algorithmic framework together with the Julia package PauliPropagation.jl that implements it.
-
A Framework for Quantum Advantage
A framework defining quantum advantage as verifiable plus classically superior, with a conclusion that random circuit sampling is not yet a satisfactory path.
Discussion (0). Continue with ORCID to comment.