Pauli path simulations of noisy quantum circuits beyond average case

Abstract

For random quantum circuits on $n$ qubits of depth $\Theta (\log n)$ with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method [Aharonov et al. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023] . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates $\unicode{x2013}$ going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.

36 pages, 4 figures

References in corpus (36)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Quantum Simulation
• Improved Simulation of Stabilizer Circuits
• Strong quantum computational advantage using a superconducting quantum processor
• Suppressing quantum errors by scaling a surface code logical qubit
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Operator Spreading in Random Unitary Circuits
• Operator hydrodynamics, OTOCs, and entanglement growth in systems without conservation laws
• A Theory of Trotter Error
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• High-threshold and low-overhead fault-tolerant quantum memory
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Low Depth Quantum Simulation of Electronic Structure
• Reachability Deficits in Quantum Approximate Optimization
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Integrable Trotterization: Local Conservation Laws and Boundary Driving
• Parallel Quantum Simulation of Large Systems on Small Quantum Computers
• Expressibility of the alternating layered ansatz for quantum computation
• A polynomial-time classical algorithm for noisy random circuit sampling
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Error propagation in NISQ devices for solving classical optimization problems
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Operator backflow and the classical simulation of quantum transport
• Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Fourier expansion in variational quantum algorithms
• Conserved charges in the quantum simulation of integrable spin chains
• Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Cited by in corpus (13)

• Artificial Intelligence for Quantum Computing
• Classically estimating observables of noiseless quantum circuits
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Emergent unitary designs for encoded qubits from coherent errors and syndrome measurements
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• Subexponential decay of local correlations from diffusion-limited dephasing
• The Dual Role of Low-Weight Pauli Propagation: A Flawed Simulator but a Powerful Initializer for Variational Quantum Algorithms
• Dynamical complexity of non-Gaussian many-body systems with dissipation
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Noisy Monitored Quantum Circuits