A polynomial-time classical algorithm for noisy quantum circuits
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914971167752192 |
|---|---|
| author | Schuster, Thomas Yin, Chao Gao, Xun Yao, Norman Y. |
| author_facet | Schuster, Thomas Yin, Chao Gao, Xun Yao, Norman Y. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12768 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A polynomial-time classical algorithm for noisy quantum circuits Schuster, Thomas Yin, Chao Gao, Xun Yao, Norman Y. Quantum Physics Computational Complexity Information Theory Mathematical Physics Atomic Physics 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. |
| title | A polynomial-time classical algorithm for noisy quantum circuits |
| topic | Quantum Physics Computational Complexity Information Theory Mathematical Physics Atomic Physics |
| url | https://arxiv.org/abs/2407.12768 |