Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
The paper presents a deterministic classical algorithm to estimate output probabilities of constant-depth quantum circuits with additive error $\epsilon$ in polynomial time, poly(n, 1/\epsilon). This improves upon prior methods by using a cluster expansion technique combined with an inclusion-exclusion argument to handle the small set of non-peaked regions.