Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach

Abstract

Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve practical quantum advantages. However, the presence of quantum noise might suppress and undermine these advantages, which blurs the boundaries of classical simulability. To gain further clarity on this matter, we present a novel polynomial-scale method based on the path integral of observable's back-propagation on Pauli paths (OBPPP). This method efficiently approximates expectation values of operators in variational quantum algorithms with bounded truncation error in the presence of single-qubit Pauli noise. Theoretically, we rigorously prove: 1) For a constant minimal non-zero noise rate $\gamma$, OBPPP's time and space complexity exhibit a polynomial relationship with the number of qubits $n$, the circuit depth $L$. 2) For variable $\gamma$, in scenarios where more than two non-zero noise factors exist, the complexity remains $\mathrm{Poly}\left(n,L\right)$ if $\gamma$ exceeds $1/\log L$, but grows exponential with $L$ when $\gamma$ falls below $1/L$. Numerically, we conduct classical simulations of IBM's zero-noise extrapolated experimental results on the 127-qubit Eagle processor [Nature \textbf{618}, 500 (2023)]. Our method attains higher accuracy and faster runtime compared to the quantum device. Furthermore, our approach allows us to simulate noisy outcomes, enabling accurate reproduction of IBM's unmitigated results that directly correspond to raw experimental observations. Our research reveals the vital role of noise in classical simulations and the derived method is general in computing the expected value for a broad class of quantum circuits and can be applied in the verification of quantum computers.

References in corpus (32)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• The theory of variational hybrid quantum-classical algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Circuit Learning
• Characterizing Quantum Supremacy in Near-Term Devices
• The Variational Quantum Eigensolver: a review of methods and best practices
• Efficient Learning for Deep Quantum Neural Networks
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum-assisted quantum compiling
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Experimental Quantum Generative Adversarial Networks for Image Generation
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• What limits the simulation of quantum computers?
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Quantifying the magic of quantum channels
• Efficient classical simulation of noisy random quantum circuits in one dimension
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Toward Practical Quantum Embedding Simulation of Realistic Chemical Systems on Near-term Quantum Computers
• Classical algorithms for quantum mean values
• Characterizing local noise in QAOA circuits
• Tight bounds on the convergence of noisy random circuits to the uniform distribution
• Simulating Noisy Quantum Circuits with Matrix Product Density Operators
• Variational circuit compiler for quantum error correction

Cited by in corpus (24)

• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Does provable absence of barren plateaus imply classical simulability?
• Classically estimating observables of noiseless quantum circuits
• Lie-algebraic classical simulations for quantum computing
• Real-time operator evolution in two and three dimensions via sparse Pauli dynamics
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Pauli path simulations of noisy quantum circuits beyond average case
• Simulating quantum dynamics in two-dimensional lattices with tensor network influence functional belief propagation
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
• Coherence Fraction in Grover Search Algorithm
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Tensor-Programmable Quantum Circuits for Solving Differential Equations
• Hardware-efficient quantum phase estimation via local control
• The Dual Role of Low-Weight Pauli Propagation: A Flawed Simulator but a Powerful Initializer for Variational Quantum Algorithms
• Short-time simulation of quantum dynamics by Pauli measurements
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Dynamical complexity of non-Gaussian many-body systems with dissipation
• Limits of Clifford Disentangling in Tensor Network States
• Noisy Monitored Quantum Circuits
• Majorana string simulation of nonequilibrium dynamics in two-dimensional lattice fermion systems
• Quantum Phase Recognition via Quantum Attention Mechanism