Byeong-Yoon Go

Hardness and Complexity Transition of Noisy Random Circuit Sampling

This work establishes an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $\gamma$ for any circuit architecture satisfying the standard average-case #P-hardness conjecture for ideal RCS, and shows that noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance.