A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics
quant-ph
Submitted: 2026-09-30
Updated: 2026-10-05
Terminology
Sources
- Limitations of Noisy Reversible Computation
- Limitations of Noisy Geometrically Local Quantum Circuits
- Efficient classical simulation of noisy quantum computation
- Classical simulation of noisy random circuits from exponential decay of correlation
- Matrix product state approach to lossy boson sampling and noisy IQP sampling
- Efficient simulation of noisy IQP circuits with amplitude-damping noise
- Quantum Refrigerator
- A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations
- Polynomial-time classical sampling of high-temperature quantum Gibbs states
- Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
- Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
- Convergence of the Cumulant Expansion and Polynomial-Time Algorithm for Weakly Interacting Fermions
- SYK thermal expectations are classically easy at any temperature
- Algorithmic Locality via Provable Convergence in Quantum Tensor Networks
- Complexity of tensor network simulation for noisy quantum circuits
- When quantum thermal states look classical
- Spatial Entanglement Sudden Death in Spin Chains at All Temperatures
- Entanglement in quantum spin chains is strictly finite at any temperature
- Noise-induced contraction of MPO truncation errors in noisy random circuits and Lindbladian dynamics
- Conditional dependence and Scrooge ensembles in shallow random quantum circuits
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity