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.

arXiv comment12+7 pages, 4+7 figures; v2: published version

References in corpus (57)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Area laws for the entanglement entropy - a review
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Strong quantum computational advantage using a superconducting quantum processor
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Quantum Entanglement Growth Under Random Unitary Dynamics
• Measurement-driven entanglement transition in hybrid quantum circuits
• Theory of the phase transition in random unitary circuits with measurements
• Measurement-induced criticality in random quantum circuits
• Unitary-projective entanglement dynamics
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
• Entropy scaling and simulability by Matrix Product States
• Dynamical purification phase transitions induced by quantum measurements
• Critical properties of the measurement-induced transition in random quantum circuits
• Entanglement transition in a monitored free fermion chain -- from extended criticality to area law
• Classical simulation of noninteracting-fermion quantum circuits
• Entanglement in a fermion chain under continuous monitoring
• Scalable probes of measurement-induced criticality
• Information Scrambling in Computationally Complex Quantum Circuits
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Entanglement transition from variable-strength weak measurements
• Observation of measurement-induced quantum phases in a trapped-ion quantum computer
• Entanglement phase transitions in measurement-only dynamics
• Measurement-induced topological entanglement transitions in symmetric random quantum circuits
• Measurement Protected Quantum Phases
• Measurement and entanglement phase transitions in all-to-all quantum circuits, on quantum trees, and in Landau-Ginsburg theory
• Efficient learning of quantum noise
• Matchgates and classical simulation of quantum circuits
• Postselection-free entanglement dynamics via spacetime duality
• What limits the simulation of quantum computers?
• Self-Organized Error Correction in Random Unitary Circuits with Measurement
• Measurement-induced criticality in (2+1)-d hybrid quantum circuits
• Experimental Realization of a Measurement-Induced Entanglement Phase Transition on a Superconducting Quantum Processor
• Conformal invariance and quantum non-locality in critical hybrid circuits
• Efficient classical simulation of random shallow 2D quantum circuits
• Operator scaling dimensions and multifractality at measurement-induced transitions
• Solving the sampling problem of the Sycamore quantum circuits
• Symmetry enriched phases of quantum circuits
• Fractal, logarithmic and volume-law entangled non-thermal steady states via spacetime duality
• Topological order and criticality in (2+1)D monitored random quantum circuits
• Spacetime duality between localization transitions and measurement-induced transitions
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Measurement-induced phase transitions in $(d+1)$-dimensional stabilizer circuits
• Measurement-Induced Power-Law Negativity in an Open Monitored Quantum Circuit
• Entanglement Domain Walls in Monitored Quantum Circuits and the Directed Polymer in a Random Environment
• 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
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Entanglement-Optimal Trajectories of Many-Body Quantum Markov Processes
• Entanglement Dynamics of Noisy Random Circuits
• Optimality of Lindblad unfolding in measurement phase transitions

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