Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

quant-phcs.CCcs.DSSubmitted Oct 1, 2026• Announced Oct 2, 2026• 1 citation
arXivHTMLPDF

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.

No sign of AI-generated textAI use disclosed
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.

Related papers

Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.

Nolan J. Coble, Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit $C$, and any bit string $x \in \{0,1\}^n$, can compute the quantity $| |^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$ additive error [Mov20]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.

•Dec 10, 2020•2 citations

Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits

Nolan J. Coble, Matthew Coudron

We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit$C$, and any bit string$x\in\{0,1\}^{n}$, can compute the quantity$\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}$to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is$\# P$-hard to compute this same quantity to within$2^{-n^{2}}$additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used$O(2^{n^{1/3}}\text{poly}(1/\epsilon))$time to compute probabilities to within additive error$\epsilon$[4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.

arXiv:2012.05460•Annual Symposium on Foundations of Computer Science•Feb 1, 2022•6 citations

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.

arXiv:2309.08405•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•16 citations

On estimating the entropy of shallow circuit outputs

Alexandru Gheorghiu, Matty J. Hoban

Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, we show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.

arXiv:2002.12814•Feb 27, 2020•32 citations

Verifiable quantum advantage in extremely low depth

Alexandru Gheorghiu

We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., $\mathsf{QNC}^0[\log\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.

quant-pharXiv:2609.01448•Sep 2, 2026•3 citations

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

Robert Koenig, Marco Tomamichel

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error $δ$, with parallel runtime $2^{O(d)}\log\log(n/δ)$ and $n 2^{O(d)}$ elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime $O(\log n)$. For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized $\mathsf{AC}^0$-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized $\mathsf{AC}^0$-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth $Ω(\log n/\log\log n)$. Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.

quant-pharXiv:2609.39448•Oct 1, 2026•0 citations
We give a deterministic classical algorithm that estimates ∣⟨x∣U∣0n⟩∣2|\langle x|U|0^n\rangle|^2∣⟨x∣U∣0n⟩∣2 to additive error ε\varepsilonε in poly(n,1/ε)\mathrm{poly}(n, 1/\varepsilon)poly(n,1/ε) time, where UUU is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and xxx is an arbitrary nnn-bit output string. This improves over prior state-of-the-art algorithms that takes nO(log(n))n^{O(log(n))}nO(log(n)) time for the same task, nO(log(log(n))n^{O(log(log(n))}nO(log(log(n)) when UUU is geometrically local, and nO(1)n^{O(1)}nO(1) for 2D geometrically-local circuits.
The paper studies deterministic classical estimation of a specified output probability P(x)=∣⟨x∣U∣0n⟩∣2P(x)=|\langle x|U|0^n\rangle|^2P(x)=∣⟨x∣U∣0n⟩∣2 for constant-depth quantum circuits with bounded-arity gates and arbitrary connectivity. For fixed depth ddd and gate arity kkk, it gives an algorithm with additive error ε\varepsilonε and runtime poly⁡d,k(n,Lin,1/ε)\operatorname{poly}_{d,k}(n,L_{\rm in},1/\varepsilon)polyd,k​(n,Lin​,1/ε), where LinL_{\rm in}Lin​ is the circuit-description length. This replaces the previous arbitrary-connectivity bound nO(log⁡n)n^{O(\log n)}nO(logn) 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≤k2dK\le k^{2d}K≤k2d. After reducing the target to 0n0^n0n, it separates bits into “good” and “bad” using the threshold τ=[e2(2K+1)]−(K+1)\tau=[e^2(2K+1)]^{-(K+1)}τ=[e2(2K+1)]−(K+1) on their probability of being one. Either a marginal-probability bound certifies P(0n)≤εP(0^n)\le\varepsilonP(0n)≤ε, or there are only OK(log⁡(1/ε))O_K(\log(1/\varepsilon))OK​(log(1/ε)) bad bits. An inclusion–exclusion identity isolates these bits and attached connected sets of good bits. Exponential decay bounds permit truncation at attachment size OK(log⁡(1/ε))O_K(\log(1/\varepsilon))OK​(log(1/ε)). 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.
We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit CCC, and any bit string x∈{0,1}nx \in \{0,1\}^nx∈{0,1}n, can compute the quantity ∣∣2| |^2∣∣2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is #P\#P#P-hard to compute this same quantity to within 2−n22^{-n^2}2−n2 additive error [Mov20]. The previous best known algorithm for this problem used O(2n1/3poly(1/ϵ))O(2^{n^{1/3}}\text{poly}(1/\epsilon))O(2n1/3poly(1/ϵ)) time to compute probabilities to within additive error ϵ\epsilonϵ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.
We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuitCCC, and any bit stringx∈{0,1}nx\in\{0,1\}^{n}x∈{0,1}n, can compute the quantity∣⟨x∣C∣0⊗n⟩∣2\vert \langle x\vert C\vert 0^{\otimes n}\rangle\vert ^{2}∣⟨x∣C∣0⊗n⟩∣2to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is#P\# P#P-hard to compute this same quantity to within2−n22^{-n^{2}}2−n2additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem usedO(2n1/3poly(1/ϵ))O(2^{n^{1/3}}\text{poly}(1/\epsilon))O(2n1/3poly(1/ϵ))time to compute probabilities to within additive errorϵ\epsilonϵ[4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.
An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.
Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. Here, we examine the hardness of this task for the case of probability distributions or quantum states produced by shallow circuits. Specifically, we show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors (LWE) problem, and thus believed to be intractable even for efficient quantum computation. This illustrates that quantum circuits do not need to be complex to render the computation of entropy a difficult task. We also give complexity-theoretic evidence that this problem for log-depth circuits is not as hard as its counterpart with general polynomial-size circuits, seemingly occupying an intermediate hardness regime. Finally, we discuss potential future applications of our work for quantum gravity research by relating our results to the complexity of the bulk-to-boundary dictionary of AdS/CFT.
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., QNC0[log⁡log⁡]\mathsf{QNC}^0[\log\log]QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0\mathsf{QAC}^0QAC0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
We consider quantum circuits consisting of ddd layers of nearest-neighbor two-qubit gates acting on nnn qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δδδ, with parallel runtime 2O(d)log⁡log⁡(n/δ)2^{O(d)}\log\log(n/δ)2O(d)loglog(n/δ) and n2O(d)n 2^{O(d)}n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(log⁡n)O(\log n)O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0\mathsf{AC}^0AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0\mathsf{AC}^0AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.