Efficient sampling of noisy shallow circuits via monitored unraveling

Abstract

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.

12+7 pages, 4+7 figures; v2: published version

References in corpus (14)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Strong quantum computational advantage using a superconducting quantum processor
• Entropy scaling and simulability by Matrix Product States
• Critical properties of the measurement-induced transition in random quantum circuits
• Matchgates and classical simulation of quantum circuits
• Postselection-free entanglement dynamics via spacetime duality
• Experimental Realization of a Measurement-Induced Entanglement Phase Transition on a Superconducting Quantum Processor
• Measurement-induced phase transitions in $(d+1)$-dimensional stabilizer circuits
• Measurement-Induced Power-Law Negativity in an Open Monitored Quantum Circuit
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Entanglement Dynamics of Noisy Random Circuits

Cited by in corpus (11)

• Universal structure of measurement-induced information in many-body ground states
• Optimized trajectory unraveling for classical simulation of noisy quantum dynamics
• Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
• Large-scale stochastic simulation of open quantum systems
• Purification Dynamics in a Continuous-time Hybrid Quantum Circuit Model
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Quantum Entanglement Phase Transitions and Computational Complexity: Insights from Ising Models
• Revisiting Nishimori multicriticality through the lens of information measures
• Measurement-induced entanglement in noisy 2D random circuits
• Noisy Monitored Quantum Circuits
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings