Joel Rajakumar

It has been known for almost 30 years that quantum circuits with interspersed depolarizing noise converge to the uniform distribution at 𝜔(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 any quantum circuit and noise of 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 Θ(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 Θ(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.

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, the output distribution can be efficiently sampled by a classical computer after a critical O(1) depth. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit's architecture, on anti-concentration properties, nor do we require Ømega(łog(n)) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought.