Hardness and Complexity Transition of Noisy Random Circuit Sampling

As quantum processors scale, demonstrating a clear quantum advantage via Random Circuit Sampling (RCS) becomes increasingly difficult due to unavoidable environmental noise. This paper addresses the critical question of identifying the noise-strength threshold at which noisy RCS transitions from being computationally hard for classical computers to being efficiently simulable.

The authors establish an architecture-general hardness bound for noisy RCS under local depolarizing noise. Their proof relies on two primary technical components:

1. A low-degree polynomial extrapolation that allows the recovery of ideal output probabilities from noisy evaluations.
2. A monotonicity reduction, which demonstrates that if a classical computer can efficiently simulate a circuit at a specific depolarizing noise strength, it can also efficiently simulate the circuit at any higher noise strength.

By combining these, the researchers show that the hardness of ideal RCS can be directly transferred to noisy RCS without requiring additional architectural assumptions or complex error-correction constructions. This approach bypasses the need for an intermediate global white-noise approximation, which was a limitation in previous studies.

The study identifies that for an n-qubit circuit of depth d, noisy RCS remains classically hard to simulate within any inverse-polynomial total variation distance as long as the depolarizing noise strength gamma satisfies gamma = O(log n / (nd)). When combined with existing results on convergence-to-uniformity, this establishes gamma = Theta(log n / (nd)) as the asymptotic complexity-transition scale for layered, regularly connected architectures. This means that within this regime, the hardness of the sampling problem is robust to noise, but beyond this threshold, the system becomes susceptible to efficient classical simulation.