Simulating quantum circuits with arbitrary local noise using Pauli Propagation
arXiv:2501.13101 · doi:10.1103/fb28-wlv2
Abstract
We present a polynomial-time classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise, including non-unital or dephasing. Although previous research demonstrated that some carefully designed quantum circuits affected by non-unital noise cannot be efficiently simulated, we show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods. Specifically, we prove that, with high probability over the circuit gates choice, Pauli propagation algorithms with tailored truncation strategies achieve an inversely polynomially small simulation error. This result holds for arbitrary circuit topologies and for any local noise, under the assumption that the distribution of each circuit layer is invariant under single-qubit random gates. Under the same minimal assumptions, we also prove that most noisy circuits can be truncated to an effective logarithmic depth for the task of {estimating} expectation values of observables, thus generalizing prior results to a significantly broader class of circuit ensembles. We further numerically validate our algorithm with simulations on a lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an lattice of qubits affected by amplitude damping.
51 pages, 6 figures
References in corpus (36)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Barren plateaus in quantum neural network training landscapes
- Towards Practical Quantum Variational Algorithms
- Demonstration of the trapped-ion quantum-CCD computer architecture
- Decoherence in Solid State Qubits
- Fault-Tolerant Quantum Computation For Local Non-Markovian Noise
- Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
- Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
- Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
- Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
- A polynomial-time classical algorithm for noisy random circuit sampling
- Does provable absence of barren plateaus imply classical simulability?
- Out-of-distribution generalization for learning quantum dynamics
- Quantum Crosstalk Robust Quantum Control
- Simulation of Qubit Quantum Circuits via Pauli Propagation
- Relative Entropy Convergence for Depolarizing Channels
- Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
- Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
- Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
- Markovian Entanglement Dynamics under Locally Scrambled Quantum Evolution
- Classical shadows with Pauli-invariant unitary ensembles
- Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
- Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
- On contraction coefficients, partial orders and approximation of capacities for quantum channels
- Spoofing cross entropy measure in boson sampling
- Effects of noise on the overparametrization of quantum neural networks
- Classically estimating observables of noiseless quantum circuits
- Quantum Convolutional Neural Networks are Effectively Classically Simulable
- Real-time operator evolution in two and three dimensions via sparse Pauli dynamics
- Pauli path simulations of noisy quantum circuits beyond average case
- Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets
- Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
- Scaling and renormalization in fault-tolerant quantum computers