Source-linked AI summary
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
TL;DR
Classically estimating a specified output probability to additive error is weaker than sampling, but it more naturally fits error mitigation and verification. This paper combines cluster expansion for peaked regions with inclusion-exclusion for non-peaked-region correlations, achieving deterministic polynomial-time estimation for arbitrary-connectivity, bounded-fan-in constant-depth circuits.
Problem
The paper studies how to classically estimate a specified output probability to additive error, a task that more naturally lends itself to error mitigation and verification than sampling.
Source: §1 · p. 2Method
The algorithm uses cluster expansion for peaked regions and inclusion-exclusion to bound approximation error from correlations with non-peaked regions.
Source: §1 · p. 2, §1.1 · p. 3Results
The algorithm deterministically estimates output probabilities to additive error ε in poly(n, 1/ε) time for constant-depth, bounded-fan-in circuits with arbitrary connectivity.
Source: §1 · p. 2Takeaways & Limitations
Output-probability estimation is an observable-estimation task that more naturally lends itself to error-mitigation and verification protocols than sampling.
Source: §1 · p. 2The theorem does not provide polynomial-time sampling, and separate additive probability estimates need not form a normalized distribution or guarantee bounded total-variation error.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
The paper gives a deterministic polynomial-time classical algorithm for additive-error estimation of specified output probabilities in constant-depth, bounded-fan-in quantum circuits with arbitrary connectivity. It handles non-peaked regions through inclusion-exclusion, builds on cluster expansion for peaked regions, and also implies estimates of product-operator expectation magnitudes.
1 Introduction
- Specified output probabilities can be estimated on a quantum computer by repeated circuit runs, and the observable-estimation task more naturally fits error-mitigation and verification protocols than sampling.The broader motivation is to clarify which computational advantages require high depth or adaptive operations and which can arise from constant-depth circuits followed by measurement.Source: §1 · pp. 1–2
- The algorithm estimates a specified output probability to additive error ε in poly(n, 1/ε) time for constant-depth, bounded-fan-in circuits with arbitrary connectivity.Earlier work achieved polynomial time for 2D nearest-neighbor circuits, while later extensions removed geometric restrictions at quasipolynomial cost.Source: §1 · p. 2
- The framework also estimates distributions over binary variables with bounded-degree strong dependency graphs, given a subroutine for small-set outcomes.The subroutine may take time exponential in the size of the evaluated set.Source: §1 · p. 2
1.1 Proof Strategy
- Cluster expansion handles peaked regions, while inclusion-exclusion bounds correlations with non-peaked regions by summing terms over small connecting regions.The method expresses the target probability through marginals on good bits and weighted marginals connecting good and bad bits; truncating large terms yields the additive-error estimate.Source: §1 · p. 2, §1.1 · pp. 3–4
1.2 Implications for expectation values
- The probability-estimation result yields polynomial-time additive estimates of product-operator expectation magnitudes by converting their squared magnitudes to output probabilities.For general real or complex expectations, the squared magnitude does not determine the sign or phase, so estimating those values remains open.Source: §1.2 · p. 5
2 Setup and preliminaries
Bit flips reduce estimation for arbitrary computational-basis inputs and outputs to estimating P(0^n). A bounded-degree overlap graph captures dependence between output qubits.
2 Setup and preliminaries
- Bit flips convert estimating |⟨y|U|x⟩|^2 for arbitrary basis strings into estimating P(0^n), with marginals defined for subsets of output qubits.Estimates for different outcomes or subsets need not be marginals of one common distribution.Source: §2 · p. 5
- The light-cone overlap graph connects output qubits with intersecting backward light cones and has maximum degree K ≤ k^2d.For fixed depth and gate arity, the graph can be constructed in polynomial time.Source: §2 · pp. 5–6
- Output vectors on disjoint vertex sets with no graph edge between them are independent because their backpropagated measurement operators act on disjoint input qubits.The input qubits are assumed to be in a product state.Source: §2 · p. 6
3 Isolating the bad bits
The section separates bad-bit and good-bit contributions in an inclusion-exclusion expansion, truncates terms with many attached good bits, and estimates good-bit marginals using cluster expansion.
3 Isolating the bad bits
- Bits with P(1_i) > τ are classified as bad, and all remaining bits form the good set.Source: §3 · p. 6
3.1 Separating the contributions of good and bad bits
- Inclusion-exclusion expresses P(0^n) through outcomes zero on bad bits and one on selected good bits, separating marginals with limited good-bit attachments.The selected set T contains components adjacent to the bad bits; T′ excludes neighborhoods of the bad bits and T.Source: §3.1 · p. 7
3.2 Bounding the bad bits with few good bits connected to them
- Terms involving many good bits in T decay exponentially, motivating truncation of the inclusion-exclusion sum to small T.Source: §3.2 · p. 7, §3.1 · p. 7
3.3 Computing the marginal probability of the good bits using cluster expansion
- For K ≥ 2, cluster expansion estimates good-bit marginals P(0_T′) to multiplicative error ε in poly(|T′|, ε^-1) time; K = 0 and K = 1 are handled trivially.Source: §3.3 · p. 9
4 Algorithm design
For fixed depth and gate arity, the design estimates a requested output probability with additive error ε in polynomial time. It combines inclusion–exclusion with cluster expansion, using exact small marginals and approximate remaining marginals.
4 Algorithm design
- For fixed d and k, a deterministic classical algorithm estimates P(x) within additive error ε using poly_{d,k}(n, Lin, 1/ε) operations.The algorithm returns an estimate in [0, 1].Source: §4 · p. 9, §4.3 · p. 11
4.1 Definitions and subroutines
- Appending bit flips reduces any target string x to 0^n without enlarging the original depth-d backward light cones; Brute computes selected marginals exactly.Good estimates P(0_W) to additive error η using Theorem 3.3 and exact Brute marginals.Source: §4.1 · pp. 9–10
4.2 Algorithm
- The algorithm builds the light-cone overlap graph and branches on its degree and singleton probabilities, using exact, approximate, or inclusion–exclusion computations as appropriate.When K ≤ 1 it multiplies exact component probabilities; otherwise it forms bad and good bit sets using a threshold and enumerates small connected attachments.Source: §4.2 · p. 10
4.3 Correctness
- The zero-return branch is ε-accurate when the singleton-probability sum is large, while the all-good branch uses Good and the all-bad branch is exact.For K ≤ 1, independent components make the product of exact component probabilities exact; projection onto [0, 1] cannot increase error.Source: §4.3 · p. 11
- In the mixed good/bad case, inclusion–exclusion decomposes the target probability into terms for sets T attached to bad bits and independent remainders T′.For each retained T, the algorithm multiplies an exact probability by a Good estimate; the accumulated marginal-estimation error is below ε/2.Source: §4.3 · p. 11
4.4 Time complexity
- The runtime analysis identifies enumeration of connected sets T and their Brute and Good evaluations as the dominant work, with |B| + ℓ = O(log(1/ε)).The theorem supplies the polynomial-time bound for fixed d and k.Source: §4.4 · p. 12
A Fine-grained time complexity
For fixed circuit depth and gate arity, every branch has polynomial runtime in n, the circuit description length, and 1/ε. The analysis bounds the bad-bit set and enumerates only bounded-size connected sets for the remaining computation.
A Fine-grained time complexity
- On the branch that does not return zero, the bad-bit set satisfies |B| < K + 1.In the mixed case, the enumeration size parameter is R = |B| + ℓ, with ℓ = |B| + ⌈log2(2/ε)⌉.Source: A Fine-grained time complexity · p. 15
- Connected sets B ∪ T are enumerated by bounded-length walks in an enlarged graph, but probability calculations continue to use the original graph.The added edges are used only to make the sets enumerable; duplicate sets are removed.Source: A Fine-grained time complexity · pp. 15–16
- For Good, independence removes disconnected cluster terms, so evaluating its truncation requires enumerating connected subsets U only up to the truncation order m.The runtime analysis also accounts for evaluating marginals on subsets of each retained U and constructing formal logarithms through degree m.Source: A Fine-grained time complexity · p. 16
- For fixed d and k, every branch has total cost poly_{d,k}(n, Lin, 1/ε).The light-cone overlap degree K and the enumeration constant are bounded when d and k are fixed.Source: A Fine-grained time complexity · p. 17