A polynomial-time classical algorithm for noisy quantum circuits
<|reference_start|>A polynomial-time classical algorithm for noisy quantum circuits: 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: any quantum circuit for which error mitigation is efficient must be classically simulable.<|reference_end|>
@article{schuster2024a,
    title={A polynomial-time classical algorithm for noisy quantum circuits},
    author={Thomas Schuster, Chao Yin, Xun Gao, Norman Y. Yao},
    journal={arXiv preprint arXiv:2407.12768},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.12768},
    primaryClass={quant-ph cs.CC cs.IT math-ph math.IT math.MP physics.atom-ph}
}