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
A polynomial-time classical algorithm for noisy quantum circuits
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
-
Long-lived local quantum coherences from hydrodynamic large deviations
Quantum coherences bind to hydrodynamic voids forming polaron-like objects, parametrically enhancing lifetimes and producing subdiffusive Green's functions in charge-conserving dynamics.
-
Bra-ket entanglement, an indicator bridging entanglement, magic, and coherence
Bra-ket entanglement indicates a shift from coherence-dominated to magic-dominated entanglement generation as its value increases.
-
Quantum-to-Classical Computability Transition via Negative Markov Chains
For unitaries from local or pairwise interactions, depolarizing noise above a critical strength makes open quantum spin chain dynamics exactly classically simulable by halting growth in the negative Markov chain repre...
-
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.
-
Sampling (noisy) quantum circuits through randomized rounding
Gaussian randomized rounding on two-qubit marginals of depth-D circuits with local depolarizing noise p yields samples whose expected Max-Cut cost matches the noisy quantum device up to an approximation ratio of 1-O[(1-p)^D].
-
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.
-
Mind the gaps: The fraught road to quantum advantage
The authors identify four transitions needed to reach fault-tolerant application-scale quantum computing from current NISQ devices.
-
Mind the gaps: The fraught road to quantum advantage
The paper identifies four key hurdles in the transition from NISQ to FASQ quantum computers and argues that targeting them will accelerate progress toward useful quantum advantage.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.