Su-un Lee, Soumik Ghosh, Changhun Oh, Kyungjoo Noh, Bill Fefferman, Liang Jiang (Oct 09 2025).
Abstract: 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.
