Efficient Sampling of Noisy Shallow Circuits Via Monitored Unraveling

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 Tc. 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 noisySEBD 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.

Automated summary

In this paper, we present a classical algorithm for sampling the output of shallow, noisy random circuits on two-dimensional qubit arrays. We extend the recently proposed space-evolving block decimation (SEBD) algorithm to handle noisy circuits. By unraveling the action of noise into measurements, our algorithm reduces entanglement and enables efficient classical sampling up to larger circuit depths.