Sampling Complexity of Noisy and Monitored Random Circuits

Noise is an unavoidable barrier to achieving quantum advantage in near-term quantum experiments. Without fault-tolerance, any noisy quantum circuit is 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 uniform distribution exponentially fast. We do this by proving upper and lower bounds on the expected total variation distance with respect to the uniform distribution, which take the form $\exp[-\tilde{\Theta}(d)]$. In addition, we show that noisy circuits anti-concentrate as fast as noiseless circuits, whereas both of them fail to anti-concentrate at sub-logarithmic depth. Our results put an upper limit to circuit depth for which we might anticipate average-case sampling hardness. We further consider sampling complexity of monitored random circuits where a certain fraction, $p$ of qubits are measured at each time. Using results from percolation theory, we find evidence of worst-case sampling hardness below $p=0.5$, coinciding with an entanglement phase transition in the Hartley entropy.