Pauli Propagation for the Classical Simulation of Quantum Circuits

Classically simulating quantum circuits is in general a hard task. However, certain families of quantum circuits may be practically or even provably efficiently simulated by use of specialized classical algorithms. In this talk, we will cover a new simulation method called "Pauli propagation", which is based on the Heisenberg propagation of observables through a quantum circuit. We will discuss recent polynomial-time simulation guarantees for estimating expectation values of noisy quantum circuits, as well as a wide range of noise-free quantum circuits that were previously believed to be out of range of classical techniques. We support our theoretical results with large-scale numerical simulations of quantum computations above 100 qubits and beyond 1D. Our results highlight that Pauli propagation is a complementary simulation approach to the popular tensor networks in that it is not natively hindered by the amount of entanglement a quantum circuit introduces or the entangling topology. Finally, we provide a high-performance open-source library for Pauli propagation that can be used to simulate modern quantum computing experiments and support quantum algorithm development.