{"id":"arxiv/2607.20804","url":"https://arxiv.org/abs/2607.20804","tags":["quant-ph"],"score":0,"title":"Hardness and Complexity Transition of Noisy Random Circuit Sampling","domain":"quant-ph","source":"arxiv","authors":["Byeongseon Go","Changhun Oh","Hyunseok Jeong"],"reviews":0,"subject":"quant-ph","summary":"Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $γ$. Assuming the standard average-case #P-hardness conjecture for ideal…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-23","reactions":{}}