IQIM Postdoctoral and Graduate Student Seminar
Note: this is a special IQIM seminar, scheduled for Thursday, January 8 beginning at 2:30 pm
Abstract: It has been known for almost 30 years that quantum circuits with interspersed depolarizing noise converge to the uniform distribution at $\omega(\log n)$ depth, where $n$ is the number of qubits, making them classically simulable. We show that under the realistic constraint of geometric locality, this bound is loose: these circuits become classically simulable at even shallower depths. While prior work in this regime considered quantum circuits with random gates/inputs or circuits with high levels of noise, we consider sampling from \textit{any} quantum circuit and noise of \textit{any} constant strength. First, we prove that the output distributions of noisy geometrically local quantum circuits can be approximately sampled from in quasipolynomial time, when their depth exceeds a fixed $\Theta(\log n)$ critical threshold which depends on the noise strength. This scaling in $n$ matches classical simulability results that were previously only known for noisy random quantum circuits (Aharonov et al., STOC 2023). We further conjecture that our bound is still loose and that a $\Theta(1)$-depth threshold suffices for simulability due to a percolation effect. To support this, we provide analytical evidence together with a candidate efficient algorithm. Our results rely on new information-theoretic properties of the output states of noisy shallow quantum circuits, which may be of broad interest. On a fundamental level, we demonstrate that unitary quantum processes in constant dimensions are more fragile to noise than previously understood.