Theory of Noise Induced Phase Transition in Random Circuit Sampling and Implications for Near-Term Quantum Algorithms

Digital quantum processors have recently outperformed classical supercomputers on Random Circuit Sampling (RCS) tasks, even in the presence of noise. Noise suppresses quantum correlations and may limit their extent across the system. It raises the question: under what conditions all of the Hilbert of a noisy quantum processor is available for computation? In this presentation, we demonstrate that the statistics of the output of noisy random quantum circuits exhibits a phase transition, separating weak and strong noise regimes. We introduce a model where this phase transition is identified analytically, providing insights into the behavior of quantum correlations under varying noise levels. This phase transition separates the parameter regimes where cross entropy benchmark (XEB), a figure of merit in RCS experiments, is a reliable estimator of fidelity. Moreover, it also separates the regimes where classical spoofing algorithms may be successful/unsuccessful. These algorithms aim to generate samples with the same XEB value as those produced by a noisy quantum processor, using only polynomial computational resources. We demonstrate the signatures of this transition in numerics and experiments on a digital quantum processor.