arXiv:2610.02146
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan
Abstract
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.
AI Summary
The paper studies deterministic classical estimation of a specified output probability $P(x)=|\langle x|U|0^n\rangle|^2$ for constant-depth quantum circuits with bounded-arity gates and arbitrary connectivity. For fixed depth $d$ and gate arity $k$, it gives an algorithm with additive error $\varepsilon$ and runtime $\operatorname{poly}_{d,k}(n,L_{\rm in},1/\varepsilon)$, where $L_{\rm in}$ is the circuit-description length. This replaces the previous arbitrary-connectivity bound $n^{O(\log n)}$ for inverse-polynomial error; polynomial-time estimation was already known for two-dimensional geometrically local circuits. The proof constructs a light-cone overlap graph of maximum degree $K\le k^{2d}$. After reducing the target to $0^n$, it separates bits into “good” and “bad” using the threshold $\tau=[e^2(2K+1)]^{-(K+1)}$ on their probability of being one. Either a marginal-probability bound certifies $P(0^n)\le\varepsilon$, or there are only $O_K(\log(1/\varepsilon))$ bad bits. An inclusion–exclusion identity isolates these bits and attached connected sets of good bits. Exponential decay bounds permit truncation at attachment size $O_K(\log(1/\varepsilon))$. Small mixed marginals are evaluated by brute force, while an existing cluster-expansion approximation scheme evaluates the remaining good-bit marginals. The guarantee concerns individual probabilities, not sampling or approximation of the output state; independently computed estimates need not define a normalized distribution. Polynomial-time sampling even under a peakedness assumption remains open. The result also estimates magnitudes of product-operator expectations, but does not recover general signs or phases. Runtime exponents depend strongly on depth and arity, and the analysis assumes exact arithmetic for marginal calculations.
ChatGPT and Claude were also used for looking up references and proofreading the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.