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) and extends it to
the case of noisy circuits. SEBD is based on a mapping of 2D unitary circuits
to 1D {\it 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 $\approx 2\%$ per CNOT, based on IBM Quantum processors, can be
efficiently sampled up to a depth of 5 iSWAP (or 10 CNOT) gate layers. Our
results help sharpen the requirements for practical hardness of simulation of
noisy hardware.
Zihan Cheng Matteo Ippoliti