Classical simulation of noisy random circuits from exponential decay of correlation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911197100507136 |
|---|---|
| author | Lee, Su-un Ghosh, Soumik Oh, Changhun Noh, Kyungjoo Fefferman, Bill Jiang, Liang |
| author_facet | Lee, Su-un Ghosh, Soumik Oh, Changhun Noh, Kyungjoo Fefferman, Bill Jiang, Liang |
| contents | We study the classical simulability of noisy random quantum circuits under general noise models. While various classical algorithms for simulating noisy random circuits have been proposed, many of them rely on the anticoncentration property, which can fail when the circuit depth is small or under realistic noise models. We propose a new approach based on the exponential decay of conditional mutual information (CMI), a measure of tripartite correlations. We prove that exponential CMI decay enables a classical algorithm to sample from noisy random circuits -- in polynomial time for one dimension and quasi-polynomial time for higher dimensions -- even when anticoncentration breaks down. To this end, we show that exponential CMI decay makes the circuit depth effectively shallow, and it enables efficient classical simulation for sampling. We further provide extensive numerical evidence that exponential CMI decay is a universal feature of noisy random circuits across a wide range of noise models. Our results establish CMI decay, rather than anticoncentration, as the fundamental criterion for classical simulability, and delineate the boundary of quantum advantage in noisy devices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06328 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Classical simulation of noisy random circuits from exponential decay of correlation Lee, Su-un Ghosh, Soumik Oh, Changhun Noh, Kyungjoo Fefferman, Bill Jiang, Liang Quantum Physics We study the classical simulability of noisy random quantum circuits under general noise models. While various classical algorithms for simulating noisy random circuits have been proposed, many of them rely on the anticoncentration property, which can fail when the circuit depth is small or under realistic noise models. We propose a new approach based on the exponential decay of conditional mutual information (CMI), a measure of tripartite correlations. We prove that exponential CMI decay enables a classical algorithm to sample from noisy random circuits -- in polynomial time for one dimension and quasi-polynomial time for higher dimensions -- even when anticoncentration breaks down. To this end, we show that exponential CMI decay makes the circuit depth effectively shallow, and it enables efficient classical simulation for sampling. We further provide extensive numerical evidence that exponential CMI decay is a universal feature of noisy random circuits across a wide range of noise models. Our results establish CMI decay, rather than anticoncentration, as the fundamental criterion for classical simulability, and delineate the boundary of quantum advantage in noisy devices. |
| title | Classical simulation of noisy random circuits from exponential decay of correlation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.06328 |