{"id":"arxiv/2610.02146","url":"https://arxiv.org/abs/2610.02146","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits","domain":"quant-ph","source":"arxiv","authors":["Matthew Coudron","Michael J. Gullans","Jon Nelson","Joel Rajakumar","Shi Jie Samuel Tan"],"reviews":0,"subject":"quant-ph","summary":"We give a deterministic classical algorithm that estimates $|\\langle x|U|0^n\\rangle|^2$ to additive error $\\varepsilon$ in $\\mathrm{poly}(n, 1/\\varepsilon)$ 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.","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}