Michael GULLANS
Noise is an unavoidable barrier to achieving quantum advantage in near-term quantum experiments. Without fault-tolerance, noisy quantum circuits under physically relevant noise models are rendered classically simulable at high-enough depth. We study the trade-off between circuit size and noise rates to identify regimes where a quantum advantage might be achieved, using sampling complexity as a proxy. We use a statistical mechanical mapping for random circuits to show that the distribution of noisy random circuits converges to the uniform distribution exponentially fast. Our results put an upper limit to circuit depth for which we might anticipate average-case sampling hardness. We also discuss the relation of these results to entanglement transitions that arise in random quantum circuits interspersed with measurements.