arXiv · Oct 1, 2026
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
By Matthew Coudron, Michael J. Gullans, Jon Nelson et al.
We give a deterministic classical algorithm that estimates |langle x|U|0ⁿrangle|² to additive error ε in poly(n, 1/ε) time, where U is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and x is an arbitrary n-bit output string. This improves over prior state-of-the-art algorithms that takes n^(O(log(n))) time for the same task, n^(O(log(log(n))) when U is geometrically local, and n^(O(1)) for 2D geometrically-local circuits.