The circuit class QAC0 was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC0 cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC0 circuits. We conjecture that the Pauli spectrum of QAC0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC0 circuits. If true, this conjecture immediately implies that polynomial-size QAC0 circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC0 circuits with at most nO(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n−1/4))-fraction of inputs. Additionally we show that this class of QAC0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.
The circuit class QAC0 was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity; in particular, showing that polynomial-size QAC0 cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC0 circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC0 circuits. We conjecture that the Pauli spectrum of QAC0 circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC0 circuits. If true, this conjecture immediately implies that polynomial-size QAC0 circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC0 circuits with at most nO(1/d) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2−Ω(n1/d))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n−1/4))-fraction of inputs. Additionally we show that this class of QAC0 circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC0 circuits. More broadly, our results add evidence that “Pauli-analytic” techniques can be a powerful tool in studying quantum circuits.
Parity ∈/ QAC0 ⟺ QAC0 is Fourier-Concentrated
A major open problem in understanding shallow quantum circuits (QAC0) is whether they can compute Parity. We show that this question is solely about the Fourier spectrum of QAC0: any QAC0 circuit with non-negligible high-level Fourier mass suffices to exactly compute PARITY in QAC0. Thus, proving a quantum analog of the seminal LMN theorem for AC0 is necessary to bound the quantum circuit complexity of PARITY.
In the other direction, LMN does not fully capture the limitations of AC0. For example, despite MAJORITY having 99% of its weight on low-degree Fourier coefficients, no AC0 circuit can non-trivially correlate with it. In contrast, we provide a QAC0 circuit that achieves (1−o(1)) correlation with MAJORITY, establishing the first average-case decision separation between AC0 and QAC0. This suggests a uniquely quantum phenomenon: unlike in the classical setting, Fourier concentration may largely characterize the power of QAC0.
PARITY is also known to be equivalent in QAC0 to inherently quantum tasks such as preparing GHZ states to high fidelity. We extend this equivalence to a broad class of state-synthesis tasks. We demonstrate that existing metrics such as trace distance, fidelity, and mutual information are insufficient to capture these states and introduce a new measure, felinity. We prove that preparing any state with non-negligible felinity, or derived states such as poly(n)-weight Dicke states, implies PARITY ∈ QAC0.
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.
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
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.
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.