Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916995915579392 |
|---|---|
| author | Zhang, Yifan F. Lee, Su-un Jiang, Liang Gopalakrishnan, Sarang |
| author_facet | Zhang, Yifan F. Lee, Su-un Jiang, Liang Gopalakrishnan, Sarang |
| contents | While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a classical algorithm that runs in $n^{\rm{polylog}(n)}$ time for simulating quantum circuits under local depolarizing noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markovianity to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markovianity in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits without anticoncentration, where prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06324 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity Zhang, Yifan F. Lee, Su-un Jiang, Liang Gopalakrishnan, Sarang Quantum Physics Statistical Mechanics Computational Complexity While quantum computing can accomplish tasks that are classically intractable, the presence of noise may destroy this advantage in the absence of fault tolerance. In this work, we present a classical algorithm that runs in $n^{\rm{polylog}(n)}$ time for simulating quantum circuits under local depolarizing noise, thereby ruling out their quantum advantage in these settings. Our algorithm leverages a property called approximate Markovianity to sequentially sample from the measurement outcome distribution of noisy circuits. We establish approximate Markovianity in a broad range of circuits: (1) we prove that it holds for any circuit when the noise rate exceeds a constant threshold, and (2) we provide strong analytical and numerical evidence that it holds for random quantum circuits subject to any constant noise rate. These regimes include previously known classically simulable cases as well as new ones, such as shallow random circuits without anticoncentration, where prior algorithms fail. Taken together, our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability, thereby highlighting the limitation of noisy quantum circuits in demonstrating quantum advantage. |
| title | Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity |
| topic | Quantum Physics Statistical Mechanics Computational Complexity |
| url | https://arxiv.org/abs/2510.06324 |