PaperlayerView exact revision on arXiv

Source-linked AI summary

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)

Daniel Grier, Jackson Morris, Kewen Wu

arXiv:2601.03243v1cs.CCquant-ph

TL;DR

QAC^0 has resisted classical lower-bound techniques, raising the possibility that it is more powerful than previously assumed. The paper proves separations from AC^0[p] and shows that, with polynomially many input copies, QAC^0 can simulate TC^0 computations.

  • Problem

    Lower bounds for QAC^0 have been harder to establish than for AC^0, and classical techniques such as random restrictions and Fourier concentration have failed to port to the quantum setting.

  • Method

    The paper analyzes QAC^0 circuits with polynomially many input copies, using a CopyEX construction and a padding argument to compute threshold functions.

  • Results

    QAC^0 contains a language requiring exponential-size AC^0[p] circuits, and TC^0 is contained in bounded-error QAC^0 with polynomially many input copies.

  • Takeaways & Limitations

    These results indicate that QAC^0 circuits are substantially more powerful than classical AC^0 circuits when supplied with many copies of the input.

  • Takeaways & Limitations

    The separation construction requires multiple disjoint input copies for parallel W tests, and it remains unclear how to produce these copies within QAC^0 itself.

Abstract

from arXiv · show

$\mathsf{QAC}^0$ is the class of constant-depth polynomial-size quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates. It is arguably the smallest natural class of constant-depth quantum computation which has not been shown useful for computing any non-trivial Boolean function. Despite this, many attempts to port classical $\mathsf{AC}^0$ lower bounds to $\mathsf{QAC}^0$ have failed. We give one possible explanation of this: $\mathsf{QAC}^0$ circuits are significantly more powerful than their classical counterparts. We show the unconditional separation $\mathsf{QAC}^0\not\subset\mathsf{AC}^0[p]$ for decision problems, which also resolves for the first time whether $\mathsf{AC}^0$ could be more powerful than $\mathsf{QAC}^0$. Moreover, we prove that $\mathsf{QAC}^0$ circuits can compute a wide range of Boolean functions if given multiple copies of the input: $\mathsf{TC}^0 \subseteq \mathsf{QAC}^0 \circ \mathsf{NC}^0$. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.

1 Introduction

The paper argues that QAC^0 is more powerful for decision problems than classical AC^0-style lower-bound intuition suggests. It proves a separation from AC^0[p], shows that polynomially many input copies enable TC^0 computations, and makes several constant-depth constructions exact.

  • 1 Introduction: QAC^0 decides a language with perfect completeness and soundness 2^-poly(n), whereas AC^0[p] requires size 2^poly(n) for every prime p > 1.This yields BQAC^0 not subset AC^0[p].
  • 1 Introduction: The separation implies the novel unconditional result QAC^0 not subset AC^0, despite AC^0 being strictly contained in AC^0[p].It resolves whether AC^0 could be more powerful than QAC^0 for decision problems.
  • 1 Introduction: With polynomially many input copies, QAC^0 can simulate every TC^0 computation, equivalently TC^0 is contained in BQAC^0 composed with NC^0.This generic power includes n-bit integer multiplication through the known TC^0 construction.
  • 1 Introduction: Exact amplitude amplification enables constant-depth QAC^0 constructions including exact parity, polynomial-size QTC^0 parity, and exact preparation of the W state.The W state is used in the paper’s construction of the W test.
  • 1 Introduction: The main separation construction uses multiple provided input copies because parallel W tests require disjoint copies, leaving exact separation and average-case hardness as future directions.The paper notes that the resulting CopyEX_n/2 function has high correlation with the constant-zero function on random inputs.
  • 1 Introduction: QAC^0 exactly computes every symmetric function in AC^0, while partial constructions use O(n^3/2) input copies for parity and O(n^2) copies for any symmetric function.These results extend the class of Boolean functions shown computable by QAC^0.

2 Preliminaries

The paper defines the quantum and classical circuit models used throughout, including QAC circuits with single-qubit and generalized Toffoli gates and the associated exact and bounded-error classes.

  • Classical NC0, AC0, AC0[m], ACC0, and TC0 are distinguished by depth, size, fan-in, and their allowed gate sets.
  • The paper emphasizes the strict classical hierarchy NC0 ⊊ AC0 ⊊ AC0[p] ⊊ TC0 for every constant prime p.
  • Quantum fanout and Boolean-function unitaries are defined explicitly, with generalized Toffoli gates implementing the AND unitary and quantum OR available in QAC.
  • QAC circuits use single-qubit and generalized Toffoli gates, while QAC0 restricts them to constant depth and polynomial size.
  • EQAC0 allows exact decision, whereas BQAC0 allows error at most 1/3 for constant-depth polynomial-size QAC circuits.
  • Parity and fanout are equivalent to preparing nekomata states, linking state preparation to constant-depth quantum computation.

3 Exact Amplitude Amplification

Exact amplitude amplification adapts Grover-style amplification to constant-depth QAC circuits, removing approximation error and enabling exact nekomata, fanout, and small-threshold constructions.

  • Exact amplitude amplification removes approximation error from prior constant-depth fanout and nekomata constructions.
  • A depth-d, size-s QAC circuit with the required initial amplitude can be transformed into an exact circuit of depth O(dk) and size O(sk).
  • The method yields an exact nekomata using constant depth and O(2^n) size, and an exact nekomata with a constant-depth polynomial-size QTC circuit.
  • QAC0 can exactly compute fanout on log^d(n) qubits for every constant d.
  • These fanout constructions support exact computation of threshold functions with k ≤ polylog(n), and consequently symmetric AC0 functions lie in EQAC0.

4 State-Unitary Duality in QAC0

The paper uses a W-state and Hamming-weight testing duality to build weak exact-weight computations, then lifts them with repeated input copies to obtain QAC0 separations and TC0 simulations.

  • 4.1 The |W⟩ State and Hamming Weight Tests: A constant-depth polynomial-size QAC circuit exactly prepares the |W⟩ state, which enables weak computation of exact Hamming-weight functions.
  • 4.1 The |W⟩ State and Hamming Weight Tests: The weak EX_k test always accepts when |x|=k and rejects with probability at least 1/n^2 when |x|≠k.
  • 4.2 Separating QAC0 from Classical Classes: One-sided error permits amplification with AND, avoiding reliance on majority, whose membership in QAC0 is unknown.
  • 4.2 Separating QAC0 from Classical Classes: With polynomially many identical input copies, QAC0 computes every constant-depth polynomial-size circuit of symmetric gates with error 2^-poly(n), including TC0 functions.
  • 4.2 Separating QAC0 from Classical Classes: The lifted blocky construction yields a decision problem in BQAC0 that is not in AC0[p].
  • 4.2 Separating QAC0 from Classical Classes: Equality checking ensures that lifted inputs consist of identical copies before applying the QAC computation, preserving the original error bound.

A Missing Proofs From Section 3

The missing proofs establish exact computation of small symmetric functions by phase-based Hamming-weight tests and generalized Toffoli aggregation within constant depth and polynomial size.

  • The required phase separation follows by choosing a modulus that assigns distinct residues to the relevant indices, using a least-common-multiple bound.
  • For m ≤ polylog(n), every symmetric Boolean function can be computed exactly by a constant-depth polynomial-size QAC circuit.
  • The construction creates phase states from copies of x, transforms them with XH, and applies a generalized Toffoli AND to detect the target Hamming weight.
  • When the input has the target weight, all transformed states are |1⟩; otherwise one phase component becomes |0⟩, forcing the final AND output to 0.
  • Workspace uncomputation restores all ancillary registers while retaining the exact EX_k or symmetric-function output.

B Indexing Requires Large Classical Fanout

The section shows that some logarithmic-size juntas and the indexing function require polynomial fanout in constant-depth classical threshold circuits. A counting argument establishes this lower bound by comparing circuit descriptions with the number of Boolean functions.

  • B Indexing Requires Large Classical Fanout: The section frames large-fanout lower bounds for juntas and indexing as a simple counting-based result supplied for completeness.The construction enumerates Boolean functions on log(n) bits, including the hard function from Theorem 25.
  • B Indexing Requires Large Classical Fanout: Some Boolean function on log(n) bits requires fanout n^Ω(1) in every constant-depth circuit of negations and threshold gates.The result follows for any fixed constant depth.
  • B Indexing Requires Large Classical Fanout: The counting proof bounds the number of depth-d, fanout-r circuits by (r^d + log(n))^O(r^d), while there are 2^n functions on log(n) bits.Therefore r must be n^Ω(1) when d=O(1).
  • B Indexing Requires Large Classical Fanout: The indexing function Ind(x,i)=x_i also requires fanout n^Ω(1) for constant-depth threshold circuits.Fixing x turns indexing into a logarithmic-input function, allowing the junta lower bound to apply.

C Towards Better Copy Complexity

This section introduces techniques aimed at reducing the number of input copies required by constructions for symmetric functions.

  • C Towards Better Copy Complexity: The paper develops additional techniques to improve the copy complexity of various symmetric functions.

C.1 Truncated Parallel Repetition

Truncated parallel repetition improves QAC circuit performance for exact Hamming-weight testing by repeating tests across copies and combining them with an AND. The resulting circuits achieve high completeness and inverse-polynomial soundness, while the copy complexity remains a central limitation.

  • C.1 Truncated Parallel Repetition: The approach is constrained because c parallel W-test runs require c disjoint input copies, and QAC^0 is known to provide only polylog(n) copies.This yields only polylog(n)/n^2 success for the available parallel repetition.
  • C.1 Truncated Parallel Repetition: Completeness is at least 1 − 2^-polylog(n), while soundness is at most 1 − polylog(n)/n for EX_n/2 using truncated parallel repetition.The circuit outputs 1 with high probability on weight n/2 and outputs 0 with probability at least polylog(n)/n otherwise.
  • C.1 Truncated Parallel Repetition: The construction repeats W tests in parallel and applies an AND, yielding deterministic acceptance for EX_n/2(x)=1 and rejection probability 1 − (1 − 1/n^2)^m otherwise.The final AND is applied after preparing and processing repeated test states.
  • C.1 Truncated Parallel Repetition: The repeated-test construction uses a state approximation whose ℓ2 distance from the ideal repeated W state is 2^-polylog(n).The bound follows from a union bound and concentration for the relevant binomial distribution.
  • C.1 Truncated Parallel Repetition: For every exact weight k, m = n/polylog(n) input copies suffice for completeness 1 − 2^-polylog(n) and soundness 2^-polylog(n).The result extends the construction from EX_n/2 to all EX_k functions.
  • C.1 Truncated Parallel Repetition: The copy complexity of every n-bit symmetric function is at most n^2/polylog(n), while improving soundness to a constant would require roughly n^2 parallel runs.The paper notes that such an improvement would imply Parity ∈ QAC^0.

C.2 Probabilistic Computation

The section uses probabilistic computation to reduce the number of input copies needed for exact high-probability parity computation in constant-depth QAC circuits. An ensemble with m = n^1.5/polylog(n) copies succeeds simultaneously on every input tuple with error 2^-polylog(n).

  • The m-copy parity function outputs Parity(y1) when all input copies are identical and outputs 0 otherwise.
  • The construction obtains a square-root saving over the n^2/polylog(n) copies used by the preceding deterministic construction.
  • With m = n^1.5/polylog(n) copies, an ensemble of constant-depth polynomial-size QAC circuits computes the m-copy parity function with probability at least 1 - 2^-polylog(n) for every input tuple.
  • For each even string r, the circuit computes f(y ⊕ r) on copied inputs, while parity remains unchanged under the shift y ⊕ r.
  • The two possible failure events each occur with probability 2^-polylog(n), and a union bound completes the proof.
  • The probabilistic computation idea can also be generalized to other symmetric functions.
Loading 2601.03243v1…