The computational complexity of $\mathsf{QAC}^0$, which are constant-depth, polynomial-size quantum circuit families consisting of arbitrary single-qubit unitaries and $n$-qubit generalized Toffoli gates, has gained tremendous focus recently.
In this work, we initiate the study of the computational complexity of geometrically local $\mathsf{QAC}^0$ circuits, where all the generalized Toffoli gates act on nearest neighbor qubits. We show that any $\mathsf{QAC}^0$ circuit can be exactly simulated by a two-dimensional geometrically local $\mathsf{QAC}^0$ circuit, i.e., a $\mathsf{2D\text{-}QAC}^{0}$ circuit, with a quadratic size blow-up. This implies that $\mathsf{QAC}^0 = \mathsf{2D\text{-}QAC}^{0}$. We further show that if there existed a $\mathsf{QAC}^0$ circuit that computes Parity with a bounded constant error, then for any $\varepsilon > 0$, there would exist a $\mathsf{2D\text{-}QAC}^{0}$ circuit that exactly computes Parity, with a very "thin" width $n^\varepsilon$.
We further study the computational power of $\mathsf{1D\text{-}QAC}^{0} $ circuits, i.e., one-dimensional $\mathsf{QAC}^0$ circuits, which are the "thinnest" $\mathsf{2D\text{-}QAC}^{0}$ circuits. We prove a nearly logarithmic depth lower bound on $\mathsf{1D\text{-}QAC}^{0} $ circuits to compute the Parity function, even if allowing an unlimited number of ancilla. Furthermore, if the inputs are encoded in contiguous qubits, we prove that it requires a nearly linear depth $\mathsf{1D\text{-}QAC}^{0} $ circuit to compute the Parity function. This lower bound is almost tight. The results are proved via the combination of the restriction argument and the light-cone argument. These results may provide a new angle for studying the computational power of $\mathsf{QAC}^0$ circuits and for resolving the long-standing open problem of whether Parity is in $\mathsf{QAC}^0$.
The computational complexity of QAC0, which are constant-depth, polynomial-size quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, has gained tremendous focus recently.
In this work, we initiate the study of the computational complexity of geometrically local QAC0 circuits, where all the generalized Toffoli gates act on nearest neighbor qubits. We show that any QAC0 circuit can be exactly simulated by a two-dimensional geometrically local QAC0 circuit, i.e., a 2D-QAC0 circuit, with a quadratic size blow-up. This implies that QAC0=2D-QAC0. We further show that if there existed a QAC0 circuit that computes Parity with a bounded constant error, then for any ε>0, there would exist a 2D-QAC0 circuit that exactly computes Parity, with a very "thin" width nε.
We further study the computational power of 1D-QAC0 circuits, i.e., one-dimensional QAC0 circuits, which are the "thinnest" 2D-QAC0 circuits. We prove a nearly logarithmic depth lower bound on 1D-QAC0 circuits to compute the Parity function, even if allowing an unlimited number of ancilla. Furthermore, if the inputs are encoded in contiguous qubits, we prove that it requires a nearly linear depth 1D-QAC0 circuit to compute the Parity function. This lower bound is almost tight. The results are proved via the combination of the restriction argument and the light-cone argument. These results may provide a new angle for studying the computational power of QAC0 circuits and for resolving the long-standing open problem of whether Parity is in QAC0.
Bounds on the QAC0 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0 circuits are QAC circuits of constant depth, and are quantum analogues of AC0 circuits. We prove the following: ∙ For all d≥7 and ε>0 there is a depth-d QAC circuit of size exp(poly(n1/d)log(n/ε)) that approximates the n-qubit parity function to within error ε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size. ∙ We introduce a class of "mostly classical" QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component. ∙ Arbitrary depth-d QAC circuits require at least Ω(n/d) multi-qubit gates to achieve a 1/2+exp(−o(n/d)) approximation of parity. When d=Θ(logn) this nearly matches an easy O(n) size upper bound for computing parity exactly. ∙ QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large n. The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name "nekomata" after an analogous cat yōkai.
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.
Bounds on the QAC0 Complexity of Approximating Parity
QAC circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. QAC0 circuits are QAC circuits of constant depth, and are quantum analogues of AC0 circuits. We prove the following:
∙ For all d≥7 and ε>0 there is a depth-dQAC circuit of size exp(poly(n1/d)log(n/ε)) that approximates the n-qubit parity function to within error ε on worst-case quantum inputs. Previously it was unknown whether QAC circuits of sublogarithmic depth could approximate parity regardless of size.
∙ We introduce a class of QAC circuits, including a major component of our circuit from the above upper bound, and prove a tight lower bound on the size of low-depth, mostly classical QAC circuits that approximate this component.
∙ Arbitrary depth-dQAC circuits require at least Ω(n/d) multi-qubit gates to achieve a 1/2+exp(−o(n/d)) approximation of parity. When d=Θ(logn) this nearly matches an easy O(n) size upper bound for computing parity exactly.
∙QAC circuits with at most two layers of multi-qubit gates cannot achieve a 1/2+exp(−o(n)) approximation of parity, even non-cleanly. Previously it was known only that such circuits could not cleanly compute parity exactly for sufficiently large n.
The proofs use a new normal form for quantum circuits which may be of independent interest, and are based on reductions to the problem of constructing certain generalizations of the cat state which we name nekomata after an analogous cat y\=okai.
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.
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
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.