Classically Estimating Observables of Noiseless Quantum Circuits

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.