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.
AI Summary
The paper studies whether the power of $\mathsf{QAC}^0$—constant-depth, polynomial-size circuits with generalized Toffoli and arbitrary single-qubit gates—depends on continuous gate parameters or nonzero computational error.
It gives an efficient compilation into generalized Toffoli, Hadamard, and $S$ gates. A depth-$d$, size-$s$ circuit can be approximated with depth $O(d)$ and size $O(s\log^2(s/\epsilon))$, using $O(s\log^2(s/\epsilon))$ additional ancillas. The approximation controls state-vector error uniformly over inputs with zero-initialized ancillas, including their return to zero. The construction uses constant-depth coherent Bernoulli samplers built from disjoint clauses, linear combinations of Pauli operators, and one round of oblivious amplitude amplification.
For exact computation, the paper removes the soundness error of the previously introduced many-copy $W$-test. It obtains exact middle-Hamming-weight testing using $O(n^2)$ classical input copies, and consequently $\mathsf{TC}^0\subseteq\mathsf{EQAC}^0\circ\mathsf{NC}^0$. Consistency-checked copy lifts yield total Boolean functions in $\mathsf{EQAC}^0$ outside $\mathsf{AC}^0[p]$ for every fixed prime $p$. Exactification runs promise tests for each alternative Hamming weight in parallel, tuning their known rejection probabilities so one amplification round suffices; distance-dependent repetition counts keep the total at $O(n^2)$ copies.
Additional constructions give uniformly random supported-coordinate selectors and Hamming-weight estimates with inverse-polylogarithmic relative error and failure probability $2^{-\mathrm{polylog}(n)}$. The exact simulations require supplied classical copies, not unrestricted quantum fanout. Whether $S$ can be omitted and whether $\mathsf{BQAC}^0=\mathsf{EQAC}^0$ remain open.
Little sign of AI-generated textAI use disclosedOverclaims
GPT 5.6 Sol and GPT 6 were used to draft the paper, which was fully rewritten by the authors.
Error found: The introductory discrete-basis theorem claims full operator-norm approximation to I_m ⊗ Q, but the proof establishes approximation only when the added ancillas start in |0^m⟩.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
In this work we study the robustness of QAC0 with respect to error tolerance and modifications to its gate-set. First, we investigate whether the non-zero error typically allowed for QAC0 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 QAC0 can \textit{exactly} simulate TC0 with polynomially many copies of the classical input and that for every fixed prime p exact QAC0, EQAC0, can compute total Boolean functions outside of AC0[p].
Second, we ask to what extent the computational power of QAC0 follows from the fact that arbitrary single-qubit gates may be used at any point in the circuit. We find that QAC0 is in fact robust to restrictions on which single-qubit gates are permitted: every QAC0 circuit can be approximately implemented by a QAC0 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.
The paper studies whether the power of QAC0—constant-depth, polynomial-size circuits with generalized Toffoli and arbitrary single-qubit gates—depends on continuous gate parameters or nonzero computational error.
It gives an efficient compilation into generalized Toffoli, Hadamard, and S gates. A depth-d, size-s circuit can be approximated with depth O(d) and size O(slog2(s/ϵ)), using O(slog2(s/ϵ)) additional ancillas. The approximation controls state-vector error uniformly over inputs with zero-initialized ancillas, including their return to zero. The construction uses constant-depth coherent Bernoulli samplers built from disjoint clauses, linear combinations of Pauli operators, and one round of oblivious amplitude amplification.
For exact computation, the paper removes the soundness error of the previously introduced many-copy W-test. It obtains exact middle-Hamming-weight testing using O(n2) classical input copies, and consequently TC0⊆EQAC0∘NC0. Consistency-checked copy lifts yield total Boolean functions in EQAC0 outside AC0[p] for every fixed prime p. Exactification runs promise tests for each alternative Hamming weight in parallel, tuning their known rejection probabilities so one amplification round suffices; distance-dependent repetition counts keep the total at O(n2) copies.
Additional constructions give uniformly random supported-coordinate selectors and Hamming-weight estimates with inverse-polylogarithmic relative error and failure probability 2−polylog(n). The exact simulations require supplied classical copies, not unrestricted quantum fanout. Whether S can be omitted and whether BQAC0=EQAC0 remain open.
QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore [arXiv: 9903046] as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits can not compute PARITY. In this work we make progress on this longstanding conjecture: we show that any depth-dQAC0 circuit requires n1+3−d ancillae to compute a function with approximate degree Θ(n), which includes PARITY, MAJORITY and MODk. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first superlinear lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to n1+exp(−o(d)) would imply that PARITY ∈ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-dQAC0 circuit with a ancillae, when applied to low-degree operators, has a degree (n+a)1−3−d polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has approximate degree o(n). This is a quantum generalization of the result that LC0 circuits have approximate degree o(n) by Bun, Robin, and Thaler [SODA 2019]. Our result also implies that QLC0=NC1.
QAC0 Contains TC0 (with Many Copies of the Input)
QAC0 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 AC0 lower bounds to QAC0 have failed.
We give one possible explanation of this: QAC0 circuits are significantly more powerful than their classical counterparts. We show the unconditional separation QAC0⊂AC0[p] for decision problems, which also resolves for the first time whether AC0 could be more powerful than QAC0. Moreover, we prove that QAC0 circuits can compute a wide range of Boolean functions if given multiple copies of the input: TC0⊆QAC0∘NC0. Along the way, we introduce an amplitude amplification technique that makes several approximate constant-depth constructions exact.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard, X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∈/QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard, X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Low-degree approximation of QAC0 circuits
QAC0 is the class of constant-depth quantum circuits with polynomially many ancillary qubits, where Toffoli gates on arbitrarily many qubits are allowed. In this work, we show that the parity function cannot be computed in QAC0, resolving a long-standing open problem in quantum circuit complexity more than twenty years old. As a result, this proves QAC0⫋QACwf0. We also show that any QAC circuit of depth d that approximately computes parity on n bits requires 2Ω(n1/d) ancillary qubits, which is close to tight. This implies a similar lower bound on approximately preparing cat states using QAC circuits. Finally, we prove a quantum analog of the Linial-Mansour-Nisan theorem for QAC0. This implies that, for any QAC0 circuit U with a=poly(n) ancillary qubits, and for any x∈{0,1}n, the correlation between Q(x) and the parity function is bounded by 1/2+2−Ω(n1/d), where Q(x) denotes the output of measuring the output qubit of U∣x,0a⟩. All the above consequences rely on the following technical result. If U is a QAC0 circuit with a=poly(n) ancillary qubits, then there is a distribution D of bounded polynomials of degree polylog(n) such that with high probability, a random polynomial from D approximates the function ⟨x,0a∣U†Zn+1U∣x,0a⟩ for a large fraction of x∈{0,1}n. This result is analogous to the Razborov-Smolensky result on the approximation of AC0 circuits by random low-degree polynomials.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems