Efficient classical simulation of noisy random quantum circuits in one dimension

Abstract

Understanding the computational power of noisy intermediate-scale quantum (NISQ) devices is of both fundamental and practical importance to quantum information science. Here, we address the question of whether error-uncorrected noisy quantum computers can provide computational advantage over classical computers. Specifically, we study noisy random circuit sampling in one dimension (or 1D noisy RCS) as a simple model for exploring the effects of noise on the computational power of a noisy quantum device. In particular, we simulate the real-time dynamics of 1D noisy random quantum circuits via matrix product operators (MPOs) and characterize the computational power of the 1D noisy quantum system by using a metric we call MPO entanglement entropy. The latter metric is chosen because it determines the cost of classical MPO simulation. We numerically demonstrate that for the two-qubit gate error rates we considered, there exists a characteristic system size above which adding more qubits does not bring about an exponential growth of the cost of classical MPO simulation of 1D noisy systems. Specifically, we show that above the characteristic system size, there is an optimal circuit depth, independent of the system size, where the MPO entanglement entropy is maximized. Most importantly, the maximum achievable MPO entanglement entropy is bounded by a constant that depends only on the gate error rate, not on the system size. We also provide a heuristic analysis to get the scaling of the maximum achievable MPO entanglement entropy as a function of the gate error rate. The obtained scaling suggests that although the cost of MPO simulation does not increase exponentially in the system size above a certain characteristic system size, it does increase exponentially as the gate error rate decreases, possibly making classical simulation practically not feasible even with state-of-the-art supercomputers.

27 pages, 9 figures, accepted for publication in Quantum

References in corpus (83)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Mixed State Entanglement and Quantum Error Correction
• The density-matrix renormalization group in the age of matrix product states
• Surface codes: Towards practical large-scale quantum computation
• Concentrating Partial Entanglement by Local Operations
• Efficient classical simulation of slightly entangled quantum computations
• Average Entropy of a Subsystem
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Improved Simulation of Stabilizer Circuits
• Quantum Computing with Very Noisy Devices
• Characterizing Quantum Supremacy in Near-Term Devices
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• A class of quantum many-body states that can be efficiently simulated
• Boson Sampling on a Photonic Chip
• Matrix product states represent ground states faithfully
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement
• Quantum Zeno Effect and the Many-body Entanglement Transition
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
• Photonic Boson Sampling in a Tunable Circuit
• Measurement-driven entanglement transition in hybrid quantum circuits
• Surface code quantum computing by lattice surgery
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Theory of the phase transition in random unitary circuits with measurements
• Gaussian Boson Sampling
• Measurement-induced criticality in random quantum circuits
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Unitary-projective entanglement dynamics
• Quantum Error Correction in Scrambling Dynamics and Measurement-Induced Phase Transition
• Critical properties of the measurement-induced transition in random quantum circuits
• Magic state distillation with low overhead
• Valence Bond Solids for Quantum Computation
• Scalable probes of measurement-induced criticality
• The computational complexity of PEPS
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Entanglement of Quantum Evolutions
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Entanglement transition from variable-strength weak measurements
• Symmetrised Characterisation of Noisy Quantum Processes
• The entanglement of purification
• Matrix product simulations of non-equilibrium steady states of quantum spin chains
• Exact dynamics in dual-unitary quantum circuits
• Operator space entanglement entropy in transverse Ising chain
• Quantum error correction with only two extra qubits
• Magic State Distillation: Not as Costly as You Think
• Average Entropy of a Subsystem
• What limits the simulation of quantum computers?
• Self-Organized Error Correction in Random Unitary Circuits with Measurement
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Topological and subsystem codes on low-degree graphs with flag qubits
• No imminent quantum supremacy by boson sampling
• How robust is a quantum gate in the presence of noise?
• An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
• Efficient classical simulation of random shallow 2D quantum circuits
• Flag fault-tolerant error correction with arbitrary distance codes
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Fault-tolerant quantum computation with few qubits
• Fault-Tolerant Quantum Computation with Local Gates
• A Quantum to Classical Phase Transition in Noisy Quantum Computers
• Accessing scrambling using matrix product operators
• Simulating boson sampling in lossy architectures
• Triangular color codes on trivalent graphs with flag qubits
• Flag fault-tolerant error correction for any stabilizer code
• Fault-tolerant magic state preparation with flag qubits
• Very low overhead fault-tolerant magic state preparation using redundant ancilla encoding and flag qubits
• Magic State Distillation with Low Space Overhead and Optimal Asymptotic Input Count
• Contracting projected entangled pair states is average-case hard
• Topological code Autotune
• Efficient description of many-body systems with Matrix Product Density Operators
• Beyond single-shot fault-tolerant quantum error correction
• Classical simulability of noisy boson sampling
• Quantum supremacy and random circuits
• Efficient classical simulation of noisy quantum computation
• Growth of genuine multipartite entanglement in random unitary circuits
• Hierarchical decoding to reduce hardware requirements for quantum computing
• A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing
• Fourier analysis of sampling from noisy chaotic quantum circuits
• Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling
• Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?

Cited by in corpus (72)

• Random Quantum Circuits
• Operator scaling dimensions and multifractality at measurement-induced transitions
• Universality of entanglement transitions from stroboscopic to continuous measurements
• A general framework for randomized benchmarking
• Cross Entropy Benchmark for Measurement-Induced Phase Transitions
• Entanglement barrier and its symmetry resolution: theory and experiment
• Quantum error mitigation via matrix product operators
• Classical algorithm for simulating experimental Gaussian boson sampling
• Boundaries of quantum supremacy via random circuit sampling
• Classical simulation of lossy boson sampling using matrix product operators
• Characterizing a non-equilibrium phase transition on a quantum computer
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Realization of quantum signal processing on a noisy quantum computer
• Benchmarking Quantum Simulators using Ergodic Quantum Dynamics
• Rise and fall, and slow rise again, of operator entanglement under dephasing
• Quantum Magic and Multi-Partite Entanglement in the Structure of Nuclei
• Many-Body Open Quantum Systems
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Diagrammatic method for many-body non-Markovian dynamics: memory effects and entanglement transitions
• Spoofing cross entropy measure in boson sampling
• Evolution of many-body systems under ancilla quantum measurements
• Simulating lossy Gaussian boson sampling with matrix product operators
• Measurement induced transitions in non-Markovian free fermion ladders
• Entanglement Dynamics of Noisy Random Circuits
• Dequantizing quantum machine learning models using tensor networks
• TenCirChem: An Efficient Quantum Computational Chemistry Package for the NISQ Era
• Tensor networks for quantum computing
• Comparing bipartite entropy growth in open-system matrix-product simulation methods
• Robustness of quantum chaos and anomalous relaxation in open quantum circuits
• Efficient sampling of noisy shallow circuits via monitored unraveling
• From observations to complexity of quantum states via unsupervised learning
• Combining Matrix Product States and Noisy Quantum Computers for Quantum Simulation
• Quantum State Tomography with Locally Purified Density Operators and Local Measurements
• Locally Purified Density Operators for Symmetry-Protected Topological Phases in Mixed States
• Quantum State Tomography for Matrix Product Density Operators
• Decoherence predictions in a superconductive quantum device using the steepest-entropy-ascent quantum thermodynamics framework
• On the sampling complexity of open quantum systems
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Quantum simulation using noisy unitary circuits and measurements
• Optimality of Lindblad unfolding in measurement phase transitions
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits
• More on symmetry resolved operator entanglement
• Optimized trajectory unraveling for classical simulation of noisy quantum dynamics
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage
• Locally purified density operators for noisy quantum circuits
• Emulating Quantum Interference with Generalized Ising Machines
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Random insights into the complexity of two-dimensional tensor network calculations
• Universal Spreading of Conditional Mutual Information in Noisy Random Circuits
• Noisy induced entanglement transition in one-dimensional random quantum circuits
• Error-mitigated deep-circuit quantum simulation of open systems: steady state and relaxation rate problems
• Compressed quantum error mitigation
• Kernel-Function Based Quantum Algorithms for Finite Temperature Quantum Simulation
• On the connection between least squares, regularization, and classical shadows
• Limitations of Noisy Quantum Devices in Computational and Entangling Power
• Efficient approximation of experimental Gaussian boson sampling
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Macroproperties vs. Microstates in the Classical Simulation of Critical Phenomena in Quench Dynamics of 1D Ising Models
• Mixed-state learnability transitions in monitored noisy quantum dynamics
• Integrals of motion as slow modes in dissipative many-body operator dynamics
• Accelerating Quantum Eigensolver Algorithms With Machine Learning
• Robustness of optimized numerical estimation schemes for noisy variational quantum algorithms
• Comment on the Quantum Supremacy Claim by Google
• Efficient tomography of microwave photonic cluster states
• Linear-optical protocols for mitigating and suppressing noise in bosonic systems
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Evolutionary reduction of the laser noise impact on quantum gates
• Learning mixed quantum states in large-scale experiments
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Measurement-induced entanglement in noisy 2D random circuits
• Noisy Monitored Quantum Circuits