PaperlayerView exact revision on arXiv

Source-linked AI summary

The Robustness of QAC0

Daniel Grier, Jackson Morris, Kewen Wu

arXiv:2610.02154v1quant-phcs.CC

TL;DR

The paper asks whether QAC0’s power depends on allowing error and arbitrary single-qubit gates, questions made delicate by constant-depth constraints. It develops exactification and gate-set restriction techniques, showing exact TC0 simulation and efficient approximate implementation with a restricted gate set. These results also preserve a separation from AC0[p] for every fixed prime p.

  • Problem

    The paper asks whether QAC0’s computational power requires nonzero error or arbitrary single-qubit gates, questions complicated because standard error reduction and gate synthesis may increase circuit depth.

    Source: §1 · p. 2

  • Method

    The paper applies exact amplitude amplification in a many-copies protocol oblivious to input Hamming weight and constructs efficient approximations using generalized Toffoli, Hadamard, and S gates.

    Source: §1 · p. 3, §4.2 · p. 16

  • Results

    Every TC0 language is exactly computable by constant-depth, polynomial-size QAC circuits with polynomially many input copies, and EQAC0 is not contained in AC0[p] for any fixed prime p.

    Source: §1 · p. 3

  • Takeaways & Limitations

    QAC0 retains these exact-computation results while also permitting efficient approximate implementation with generalized Toffoli, Hadamard, and S gates.

    Source: §1 · p. 3

    Whether BQAC0 equals EQAC0 remains open, and the paper notes that a generic exactification procedure is unclear.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

In this work we study the robustness of $\mathsf{QAC}^0$ with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for $\mathsf{QAC}^0$ circuits computing Boolean functions is truly necessary. We show that the error inherent in the parallel $W$-test of \cite{grier_morris_wu} can be eliminated entirely via a novel application of exact amplitude amplification in the many-copies context. Consequently, we find that $\mathsf{QAC}^0$ can \textit{exactly} simulate $\mathsf{TC}^0$ with polynomially many copies of the classical input and that for every fixed prime $p$ exact $\mathsf{QAC}^0$, $\mathsf{EQAC}^0$, can compute total Boolean functions outside of $\mathsf{AC}^0[p]$. Second, we ask to what extent the computational power of $\mathsf{QAC}^0$ follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that $\mathsf{QAC}^0$ is in fact robust to restrictions on which single-qubit gates are permitted: every $\mathsf{QAC}^0$ circuit can be approximately implemented by a $\mathsf{QAC}^0$ circuit consisting of just generalized Toffoli, $S$, and Hadamard gates. Moreover, this approximating circuit can be constructed efficiently from a classical description of the original circuit.

1 Introduction

The paper addresses whether QAC0 needs bounded error or arbitrary single-qubit gates to retain its computational power. It gives exactification and gate-set results, develops two additional primitives, and identifies open questions about the scope of these results.

1 Introduction

  • Any QAC circuit can be approximated within operator-norm error ϵ using only generalized Toffoli, Hadamard, and S gates, with an efficient construction.The resulting circuit has depth O(d), size O(s log^2 s/ϵ), and uses O(n+s log^2 s/ϵ) qubits for an original depth-d, size-s circuit on n qubits.Source: §1 · pp. 2–3
  • Every language in TC0 has an exact constant-depth, polynomial-size QAC simulation using polynomially many input copies, and EQAC0 contains total Boolean functions outside AC0[p] for each fixed prime p.These results answer whether zero error removes the stated advantage against AC0[p].Source: §1 · p. 3
  • A QAC random selector returns a uniformly random 1-position with high probability, in either binary or unary encoding.For nonzero x, the success probability is at least 1 − 2^-polylog(n).Source: §1 · p. 3
  • A constant-depth, polynomial-size QAC circuit estimates Hamming weight with relative error at most 1/polylog(n), with probability at least 1 − 2^-polylog(n).Source: §1 · p. 3

1.1 Technical overview

  • For gate synthesis, coherent sampling encodes target-gate parameters in a circuit whose size grows with precision while its depth remains constant.The construction approximates real single-qubit gates with Hadamard and generalized Toffoli, then extends to complex gates using S.Source: §1.1 · p. 4
  • Exactification over many input copies uses exact amplitude amplification on weight-specific promise tests, avoiding dependence on an unknown initial success probability.The W-test has error that parallel repetition can reduce, but its success probability depends on the input weight; the promise tests allow constant-depth exact distinction.Source: §1 · p. 3, §1.1 · p. 5

1.2 Future directions

  • Whether S is necessary for QAC0 and whether BQAC0 equals EQAC0 remain open.The paper notes that known Boolean-function constructions do not use S, and that every Boolean function known to lie in BQAC0 is computable in EQAC0.Source: §1.2 · p. 5

2 Preliminaries

This section sets notation for circuit classes, QAC0 computation, and unitary approximation, and records prior constructions used later.

Uniformity

  • The circuit upper bounds are uniform and efficiently extractable, while the lower bounds allow non-uniform circuits.Uniformity is not the paper's focus.Source: §2 · p. 6

Classical circuit complexity

  • For each fixed prime p, AC0 is strictly contained in AC0[p], which is strictly contained in TC0.ACC0 is also contained in TC0, though strictness of that inclusion is unproven.Source: §2 · p. 6

QAC and QAC0

  • QAC0 comprises constant-depth polynomial-size circuits with single-qubit and generalized Toffoli gates, with exact and bounded-error variants EQAC0 and BQAC0.The standard gate set permits arbitrary single-qubit gates.Source: §2 · p. 7

Classical copies and composition

  • The class EQAC0 ◦ NC0 includes functions computed after an NC0 copying map supplies polynomially many identical classical input copies.The m-copy lift is total and rejects inconsistent copies.Source: §2 · pp. 7–8

Unitary approximation and block encodings

  • The paper's approximation definition controls both the input-register error and the error from uncomputing ancillas.A block encoding's all-zero ancilla block gives the encoded operator; encoding U/2 succeeds with probability 1/4 and does not alone implement U with clean ancillas.Source: §2 · p. 8

Prior constructions

  • Prior QAC0 constructions include clean-ancilla W-state preparation, exact fanout for polylogarithmic fanout, and exact threshold and exact-weight tests for k ≤ polylog(n).These results are attributed to [GMW26].Source: §2 · p. 8

3 A discrete basis for QAC0

The section constructs constant-depth approximations to arbitrary single-qubit gates using a discrete gate set. Its synthesis combines coherent coefficient preparation, LCU, and amplitude amplification, yielding Hadamard, S, and generalized Toffoli gates as a universal set for QAC0.

Coherent Bernoulli sampler

  • For every p in [0,1] and 0 < δ < 1/2, the coherent Bernoulli sampler Wp uses only Hadamard and generalized Toffoli gates, has O(log^2(1/δ)) gates, and depth independent of p and δ.Source: §3 · p. 10

Direct synthesis of Uθ

  • For every θ and ε, a constant-depth Hadamard–Toffoli circuit approximates Uθ using O(log^2(1/ε)) qubits.The circuit is built from coherent coefficient preparation and an LCU construction for (1/2)Uθ, followed by one round of amplitude amplification to approximate Uθ.Source: §3 · pp. 10–12

Theorem 9

  • Hadamard, S, and generalized Toffoli are universal for QAC0, and arbitrary one-qubit gates can be approximately implemented with this gate set.The construction can be extended from real to complex single-qubit gates by adding S gates.Source: §3 · pp. 9, 14
  • Each determinant-one single-qubit gate can be approximated using three Uθ gates and six S gates.The Euler decomposition supplies the reduction to these rotations and S gates.Source: §3 · p. 14
  • Approximating a circuit with k single-qubit gates to error ε requires O(k log^2(k/ε)) additional ancillas in the described construction.The synthesis uses at most 3k + 1 Uθ gates, each approximated with error ε/(3k + 1).Source: §3 · p. 15

4 Exact simulation of TC0 in QAC0

The section eliminates the W-test’s soundness error through exact amplitude amplification, enabling exact QAC0 simulation of TC0 with polynomially many classical input copies.

4.1 Standard error reduction via parallel repetition

  • Parallel W-tests accept with certainty at weight n/2 and reduce the acceptance probability for other weights to at most e^(-m/n^2) after m repetitions.A single test rejects non-middle weights with probability at least 1/n^2.Source: §4.1 · p. 16

4.2 Hamming weight oblivious exact amplitude amplification

  • The amplification challenge is that the precise overlap needed for exact amplification depends on the unknown Hamming weight being tested.The construction therefore seeks amplification that is oblivious to |x|.Source: §4.2 · p. 16
  • For weight k versus n/2, amplification distinguishes the two promised cases with zero error, while leaving the state unchanged at weight n/2.The construction uses O(n^2) classical copies for the exact middle-slice test.Source: §4.2 · pp. 16, 19
  • Padding gives exact tests for every Hamming weight, and combining them computes any symmetric function, including every threshold function, with polynomially many copies.The padded test distinguishes weight j from weight k by extending each input copy with a fixed string.Source: §4.2 · p. 19
  • TC0 is contained in exact QAC0 with polynomially many classical input copies.The section also concludes that, for every prime p, exact QAC0 contains total Boolean functions outside AC0[p].Source: §4 · p. 15, §4.2 · p. 19
  • For every fixed prime p, exact QAC0 is not contained in AC0[p].The passage also states noncontainment in ACC0 under the assumption ACC0 ⊂ TC0.Source: §4.2 · p. 19

C eC

A circuit computing EX↑nk can be used to construct a circuit for EXn/2 by copying the input and feeding it into that circuit.

C eC

  • A circuit computing EX↑nk can be used to construct a circuit for EXn/2 by copying the input and feeding it into that circuit.The provided passage describes this construction by copying the input before evaluating C.Source: C eC · p. 20

5 AI disclosure

The authors describe GPT 5.6 Sol and GPT 6 as tools used in the research and drafting process, while retaining responsibility for the paper’s mathematical claims and exposition.

5 AI disclosure

  • The authors report that GPT 5.6 Sol confirmed heuristics with rigorous proofs during the research process.The authors supplied the intuitive justification and intended proof approach.Source: §5 · p. 20
  • GPT 5.6 Sol and GPT 6 were used to draft the paper, which the authors then fully rewrote.Source: §5 · p. 20
  • The authors state that mathematical claims and exposition remain their responsibility.Source: §5 · p. 20

A Random selectors in QAC0

QAC0 constructs unary and binary selectors that choose a uniformly random 1-location with high probability, while outputting zero on zero input. The constructions bypass the natural need for indexing, which is not known to be in QAC0.

Selector scope

  • The selectors bypass the natural need for indexing, which is not known to be in QAC0.The binary encoding map from an indicator to bin(i) is in QAC0, but the text does not establish a map to i itself.Source: A Random selectors in QAC0 · pp. 22, 24

Unary selector

  • The unary selector outputs 0^n surely when x=0^n, and otherwise outputs a uniformly random e_i from the support with probability at least 1−δ.The guarantee holds when log(1/δ) is polylog(n).Source: A Random selectors in QAC0 · p. 22
  • The unary construction uses polylogarithmically many random masking trials at geometrically decreasing inclusion rates, then phase kickback writes the selected indicator without large fanout.The trials mask the input and flag masks containing exactly one surviving 1.Source: A Random selectors in QAC0 · pp. 22–23

Binary selector

  • The circuit’s L-qubit output register Y measures to 0^L with probability one on x=0^n; for nonzero x, it yields 0^L or bin(i), with the latter occurring with probability at least 1−δ and i uniformly random in S(x).Source: A Random selectors in QAC0 · pp. 23–24

B Approximate counting in QAC0

QAC0 implements approximate Hamming-weight counting in constant depth and polynomial size, with exact zero detection and a multiplicative-error guarantee for positive weights.

Approximate counting

Loading 2610.02154v1…