Find in Library

We introduce a classical algorithm for sampling the output of shallow, noisy random circuits on two-dimensional qubit arrays. The algorithm builds on the recently proposed “space-evolving block decimation” (SEBD) [Napp et al, Phys. Rev. X 12, 021021 (2022)] and extends it to the case of noisy circuits. SEBD is based on a mapping of two-dimensional unitary circuits to one-dimensional monitored ones, which feature measurements alongside unitary gates; it exploits the presence of a measurement-induced entanglement phase transition to achieve efficient (approximate) sampling below a finite critical depth T_{c}. Our noisy-SEBD algorithm unravels the action of noise into measurements, further lowering entanglement and enabling efficient classical sampling up to larger circuit depths. We analyze a class of physically relevant noise models (unital qubit channels) within a two-replica statistical mechanics treatment, finding weak measurements to be the optimal (i.e., most disentangling) unraveling. We then locate the noisy-SEBD complexity transition as a function of circuit depth and noise strength in realistic circuit models. As an illustrative example, we show that circuits on heavy-hexagon qubit arrays with noise rates of approximately equal to 2% per cnot, based on IBM Quantum processors, can be efficiently sampled up to a depth of five iswap (or ten cnot) gate layers. Our results help sharpen the requirements for practical hardness of simulation of noisy hardware.