Classically estimating observables of noiseless quantum circuits
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that, for any architecture where each circuit layer is randomly sampled from a distribution invariant under single-qubit rotations, our algorithm achieves a small error ϵ on all circuits except for a small fraction δ. The computational time is polynomial in qubit count and circuit depth for any small constant ϵ, δ and quasipolynomial for inverse-polynomially small ϵ, δ. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.