Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings

Abstract

Classical simulations of noisy quantum circuits are instrumental to our understanding of the behavior of real-world quantum systems and the identification of regimes where one expects quantum advantage. In this work, we present a highly parallelizable tensor-network-based classical algorithm -- equipped with rigorous accuracy guarantees -- for simulating $n$-qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample. Each pure state evolved under a single qubit noise process is then represented by the ensemble of states that achieves the minimal average entanglement (the entanglement of formation) between the noisy qubit and the remainder. This approach lets us use a more compact representation of the quantum state for a given accuracy requirement and noise level. For a given maximum bond dimension $\chi$ and circuit, our algorithm comes with an upper bound on the simulation error, runs in $\mathrm{poly}(n,\chi )$-time and improves upon related prior work (1) in scope: by extending analytic methods from the three commonly considered noise models to general single qubit noise (2) in performance: by deriving an exact, closed-form solution to the local entanglement minimization problem -- previously approached via variational heuristics -- thereby guaranteeing local optimality without numerical optimization overhead, and (3) in conceptual contribution: by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing, dephasing and amplitude damping noise acting on a maximally entangled state.

24 pages + 39 page appendix, 15 figures, 4 tables. Small rephrasing. Adding link to code repository. Comments welcome

References in corpus (85)

• Quantum entanglement
• Entanglement of Formation of an Arbitrary State of Two Qubits
• Mixed State Entanglement and Quantum Error Correction
• The density-matrix renormalization group in the age of matrix product states
• Concentrating Partial Entanglement by Local Operations
• Area laws for the entanglement entropy - a review
• Entanglement of a Pair of Quantum Bits
• Efficient classical simulation of slightly entangled quantum computations
• Efficient simulation of one-dimensional quantum many-body systems
• Improved Simulation of Stabilizer Circuits
• The Quantum Jump Approach to Dissipative Dynamics in Quantum Optics
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas
• Quantum trajectories and open many-body quantum systems
• Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
• Matrix product states represent ground states faithfully
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Roads towards fault-tolerant universal quantum computation
• Tensor networks for complex quantum systems
• Theory of the phase transition in random unitary circuits with measurements
• Measurement-induced criticality in random quantum circuits
• Entanglement Measures under Symmetry
• Entropy scaling and simulability by Matrix Product States
• Critical properties of the measurement-induced transition in random quantum circuits
• Matrix product operator representations
• Classical simulation of noninteracting-fermion quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Average-case complexity versus approximate simulation of commuting quantum computations
• Simulation of quantum circuits by low-rank stabilizer decompositions
• The Entanglement of Formation for Isotropic States
• Simulation methods for open quantum many-body systems
• What limits the simulation of quantum computers?
• A positive tensor network approach for simulating open quantum many-body systems
• Variational Characterisations of Separability and Entanglement of Formation
• Computational advantage of quantum random sampling
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Perfect Sampling with Unitary Tensor Networks
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Efficient classical simulation of noisy random quantum circuits in one dimension
• Purifications of multipartite states: limitations and constructive methods
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Matrix product operators and states: NP-hardness and undecidability
• Roofs and Convexity
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Efficient tensor network simulation of IBM's largest quantum processors
• Entanglement of random vectors
• Classical simulatability, entanglement breaking, and quantum computation thresholds
• Unbiased Simulation of Near-Clifford Quantum Circuits
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• From estimation of quantum probabilities to simulation of quantum circuits
• Improved upper bounds on the stabilizer rank of magic states
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Why Two Qubits Are Special
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Quantum advantage of unitary Clifford circuits with magic state inputs
• Entanglement-Optimal Trajectories of Many-Body Quantum Markov Processes
• Fundamental limitations in the purifications of tensor networks
• Efficient description of many-body systems with Matrix Product Density Operators
• Matrix decompositions in Quantum Optics: Takagi/Autonne, Bloch-Messiah/Euler, Iwasawa, and Williamson
• Stabilizer extent is not multiplicative
• Dynamics of many-body localization in the presence of particle loss
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Optimal Decompositions of Barely Separable States
• Classically estimating observables of noiseless quantum circuits
• Classical simulation of non-Gaussian fermionic circuits
• Efficient sampling of noisy shallow circuits via monitored unraveling
• Comparing bipartite entropy growth in open-system matrix-product simulation methods
• Improved lower and upper bounds for entanglement of formation
• Pauli path simulations of noisy quantum circuits beyond average case
• Another convex combination of product states for the separable Werner state
• Improved simulation of quantum circuits dominated by free fermionic operations
• Noise-induced shallow circuits and absence of barren plateaus
• Optimized trajectory unraveling for classical simulation of noisy quantum dynamics
• Optimality of Lindblad unfolding in measurement phase transitions
• Locally purified density operators for noisy quantum circuits
• Entanglement of formation and monogamy of multi-party quantum entanglement
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Quantum complexity phase transitions in monitored random circuits
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Efficient quantum circuit simulation using a multi-qubit Bloch vector representation of density matrices
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Non-unitarity maximizing unraveling of open quantum dynamics
• Large-scale stochastic simulation of open quantum systems