Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

arXiv:2610.02146 · quant-ph, cs.CC, cs.DS · Submitted 2026-10-01 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits".

Kai: Given a description of an n-qubit circuit implementing a unitary U, an output string x ∈ 0, 1n, and an error tolerance ε > 0,

Mira: First, who's behind it and why it matters.

Title and authors: Kai: So, we're diving into the paper titled "Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits," which sounds like something that could really help us figure out how to verify quantum computations without needing a full quantum machine.

Mira: I was looking at the title and authors, and it immediately tells me this work is focused on getting a deterministic classical estimate of those output probabilities for constant-depth circuits, which is a specific setting we see often in experimental quantum hardware right now.

Lev: From my perspective in error correction, the fact that they're aiming for an additive error epsilon in polynomial time suggests they are tackling something very practical; it moves the problem away from exponential complexity toward something manageable for real-world constraints.

Kai: Exactly, and I think the authors are pushing this because estimating these probabilities deterministically is so much more useful than just running a quantum circuit many times to get an approximate count.

Mira: They are clearly positioning this as an estimation problem rather than a sampling problem, which opens the door for error mitigation protocols that rely on knowing what the underlying distribution actually looks like before you start measuring it.

Lev: If this algorithm is truly deterministic polynomial time, it means we could potentially design classical checks that provide a rigorous bound on how much our actual experimental results might deviate from what the circuit predicts.

The paper's summary: Kai: So, the paper summarizes their core contribution as providing a deterministic classical algorithm to compute an estimate of P(x) = xU0 n squared to an additive error epsilon, and they claim this runs in poly (n, one/epsilon) time for constant-depth quantum circuits <ref:2610.02146#pg0>.

Mira: What strikes me about the summary is the specific restriction: it applies to constant-depth quantum circuits comprised of gates with bounded fan-in and arbitrary connectivity, which is a crucial constraint because it makes the geometric structure of the circuit exploitable.

Lev: That limitation on circuit depth and gate arity is important for implementation; running this on actual NISQ hardware means we have to keep our circuits shallow, which aligns perfectly with what they've analyzed.

Kai: They mention that this approach improves upon previous algorithms that took n times O((n)) time for the same task, and even better bounds when the circuit is geometrically local.

Mira: The methodology they use involves an inclusion-exclusion decomposition of P(zero n) based on light-cone properties in the circuit, which they then reduce to a subroutine that computes sufficiently peaked marginals of the output distribution through a cluster expansion technique <ref:2610.02146#pg0>.

Lev: That cluster expansion idea sounds like it’s the mathematical engine that allows them to handle those regions of the distribution that are peaked, essentially finding "exactly solvable points" to simplify things for classical computation.

The paper's improvements: Kai: The paper outlines several improvements stemming from their approach; they show that by using this decomposition and the Mann–Waite theorem, they can achieve polynomial-time additive estimation for general circuits without needing a peakedness assumption initially.

Mira: They specifically highlight that Theorem one point one provides polynomial-time probability estimation without any prior peakedness assumption, but they note a limitation: separate estimates of individual probabilities don't necessarily have to form a normalized distribution or guarantee bounded total variation error <ref:2610.02146#pg0>.

Lev: That is a key point for hardware; if the total variation error isn't guaranteed to be bounded across all probabilities, then we need very careful aggregation protocols when we run the estimation process on noisy hardware.

Kai: The paper also discusses how they can extend their work to polynomial-time sampling of arbitrary-connectivity peaked shallow circuits, which is definitely an open question they've pointed out as a natural next step.

Mira: Furthermore, Theorem one point one extends to single-qubit operators A i with norms less than or equal to one, showing they can estimate the magnitude of the product-operator expectation value m to additive error epsilon in poly (n, one/epsilon) time for fixed depth and gate arity <ref:2610.02146#pg0>.

Lev: That extension is interesting because it lets us quantify the performance of local operations on real hardware; if we can reliably estimate those small operator magnitudes, it gives us a way to monitor drift in the control fields themselves.

Conclusion: Kai: So, to wrap up, this paper introduces a deterministic classical algorithm for estimating output probabilities of shallow quantum circuits with additive error epsilon in polynomial time relative to n and one/epsilon <ref:2610.02146#pg0>.

Mira: Essentially, it provides a robust framework by using light-cone decompositions and cluster expansions to translate the quantum probability estimation into a problem solvable efficiently on classical hardware.

Lev: For running this on real hardware, the main implication is that we can build dynamic error mitigation strategies that refine state estimation iteratively based on these marginals rather than relying solely on post-measurement corrections.

Kai: The broader impact I see is that this gives us a way to rigorously characterize quantum features and kernels in QML models by providing those polynomially bounded confidence intervals for output probabilities, which is a big deal for verification.

Mira: And from a theory standpoint, the complexity class delineation they suggest based on circuit structure could help us formally classify which circuit families are classically simulatable versus those that truly require quantum resources.

Lev: I just want to reiterate that while this is powerful for theoretical characterization and error mitigation, the paper's limitation is that it doesn't guarantee a bounded total variation error across all probabilities, so we still need to be cautious about how we combine those individual estimates.

Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan

University of Maryland · QuEra Computing Inc. · University of California, Los Angeles

quant-ph, cs.CC, cs.DS

Submitted: 2026-10-01

Updated: 2026-10-01

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Given a description of an n-qubit circuit implementing a unitary U, an output string x ∈ 0, 1n, and an error tolerance ε > 0, this work provides a deterministic classical algorithm that estimates

Key concepts

Constant-depth quantum circuits
These are quantum circuits with only a few layers of gates applied in parallel. They are important for studying quantum advantages, especially in experimental settings where coherence times are limited.
Additive error estimation
This is the task of estimating the probability $P(x) = |\langle x|U|0\rangle|^2$ with a guaranteed error bound $\epsilon$. The algorithm achieves this by bounding the error introduced by truncating an inclusion-exclusion decomposition.
Cluster expansion
This is a technique used to estimate probabilities for distributions. In this paper, it is applied to marginal probabilities of 'good' output bits, allowing for efficient estimation when the dependency graph has bounded degree.

Terminology

Summary

Given a description of an n-qubit circuit implementing a unitary U, an output string x ∈ 0, 1n, and an error tolerance ε > 0, this work provides a deterministic classical algorithm that estimates the probability P(x) = ⟨xU0n⟩2 to additive error ε in poly(n, 1/ε) time for constant-depth quantum circuits. This result improves upon prior state-of-the-art algorithms that take n O(log(n)) time for the same task.

The gist

A deterministic classical algorithm computes an estimate of ⟨xU0n⟩2 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.

Problem Setting and Motivation

The task addressed is the estimation of the output probability P(x) = ⟨xU0n⟩2, given the description of an n-qubit circuit U, a bitstring x ∈ 0, 1n, and an error tolerance ε > 0. While a quantum computer can obtain this estimate by running the circuit repeatedly and counting instances of x, it is highly desirable from the perspective of quantum advantage if this task were difficult for classical computers because it is defined as an observable estimation problem rather than a sampling problem, lending itself naturally to error mitigation and verification protocols. The paper focuses on constant-depth quantum circuits, which are experimentally relevant due to short coherence times and theoretically significant for investigating separations between quantum and classical computational complexity.

Core Technical Approach: Inclusion-Exclusion Decomposition

The main technical contribution involves reducing the estimation problem to a subroutine that computes sufficiently peaked marginals of the output distribution via a cluster expansion technique. The core idea is an inclusion-exclusion decomposition of P(0n) based on light-cone properties in the circuit. This decomposition expresses P(0n) in terms of mixed outcomes:

P(0n) = X T ⊆[n]B (−1)T × Pr[all bits in B agree with x, all bits in T disagree with x] (2).

The set T is constructed such that it consists of connected components touching the set B (bad output bits). The algorithm then enumerates and evaluates this expression using only small connecting regions to produce the desired additive error estimate.

Bounding Error via Peakedness and Cluster Expansion

The algorithm relies on exploiting the structure of shallow circuits, where independence between regions of the circuit with disjoint light cones forces many regions to be strongly concentrated on the corresponding target bitstring. The paper introduces a cluster expansion technique to handle regions of the output distribution that are peaked, choosing the peaked computational basis state as an exactly solvable point. This allows direct application of a classical algorithm that computes sufficiently peaked marginals of the output distribution. The error introduced by truncating the inclusion-exclusion expansion is bounded by showing that terms associated with sets T having many good bits have very small contribution.

Algorithm Structure and Complexity

The deterministic classical algorithm combines the inclusion-exclusion decomposition with the Mann–Waite theorem, which provides a fully polynomial-time approximation scheme for estimating probabilities of events in a strong dependency graph. The algorithm involves several subroutines:

  1. Brute(S, zS): Returns P(zS) exactly in time O(d k d S squared k d S + k).

  2. Good(W, η): Estimates P(0W) to multiplicative error η in runtime poly(W, ε−1), where the marginals are computed exactly by Brute.

The total runtime is shown to be polynomial, specifically O poly(d, k d, n, Lin) 2k n O(k d + log(K+2)) × 2ε O(CK(k d + log(K+2)) log(K+2)), where K is the maximum degree of the light-cone overlap graph G.

Implications for Expectation Values

Theorem 1.1 also provides polynomial-time additive estimation of the magnitude of product-operator expectation values, m, for single-qubit operators Ai with Ai ≤ 1. This is achieved by expressing m2 as an output probability of a circuit on at most 2n qubits with depth at most 2d + 1, and then taking the square root of the estimate to obtain m to additive error ε in poly(n, 1/ε) time for fixed depth and gate arity. However, the paper notes that for general signed or complex expectation values, the squared magnitude does not determine its sign or phase.

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits. The core contribution is a deterministic classical algorithm that estimates the output probability of a shallow quantum circuit to an additive error of inverse polynomial time in both the circuit size and the desired precision.

Here are specific improvements to AI systems that can be derived from this research, categorized by application:

)

)

)

)

  1. Improve Robustness and Verification of Quantum Machine Learning (QML):

  2. Enhanced Error Mitigation in Noisy Intermediate-Scale Quantum (NISQ) Devices:

  3. Efficient Analysis of Quantum Sampling Hardness for Classical Simulation:

  4. Improve Robustness and Verification of QML Systems:

The paper provides a polynomial-time method to estimate the probability distribution output by shallow quantum circuits, which is foundational for characterizing quantum features and kernels in QML models.

  • Specific Improvement: Develop classical verification protocols for quantum classifiers or generative models trained on shallow circuits. Instead of relying solely on noisy sampling, use this algorithm to deterministically bound the error in output probabilities for specific test points (e.g., verifying a classification boundary).

  • What the improved system can do: Create guaranteed-error QML models where the classical simulation side can provide a rigorous, polynomially bounded confidence interval on the quantum output probability, ensuring that adversarial perturbations or measurement noise do not violate predefined accuracy thresholds during inference.

  1. Enhanced Error Mitigation in NISQ Devices:

The algorithm is designed to handle constant-depth circuits with bounded fan-in and arbitrary connectivity, which are characteristic of many hardware architectures (like those using limited qubit connectivity). The error bound is additive, meaning the total error accumulates linearly across the estimation process.

  • Specific Improvement: Implement dynamic, adaptive error mitigation strategies during quantum computation on NISQ hardware. Instead of post-processing a single measurement to estimate an expectation value, use this technique to iteratively refine the state estimation by estimating output probabilities for small subsets of qubits (using the light-cone decomposition) and correcting the resulting bias in real-time.

  • What the improved system can do: Significantly reduce the required number of physical measurements needed to achieve a target confidence level in variational quantum algorithms (VQAs), leading to faster convergence and lower noise sensitivity on hardware with limited coherence times.

  1. Efficient Analysis of Quantum Sampling Hardness for Classical Simulation:

The paper addresses the computational difficulty of classically simulating certain quantum distributions, particularly those arising from shallow circuits. It provides a deterministic polynomial-time algorithm that avoids the exponential bottlenecks found in prior state-of-the-art methods.

  • Specific Improvement: Develop new complexity theory tools to formally classify quantum advantage based on circuit structure (depth, connectivity) rather than just circuit size. Specifically, use the established light-cone graph analysis (Lemma 2.1 and Section 5) to create new complexity classes that precisely delineate the boundary between classical simulation feasibility and quantum computational power for specific circuit families.

  • What the improved system can do: Provide a rigorous theoretical framework for designing quantum circuits with provably hard output distributions against classical simulation, guiding the construction of novel quantum algorithms whose theoretical advantage is guaranteed by their structure, rather than being an empirical observation.

Sources

Related papers