We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This result is incomparable with other recent lower bounds on constant-depth QAC-circuits by Rosenthal [ICTS~2021,arXiv:2008.07470] and uses different techniques which may be of independent interest: 1. We show that all members of a certain class of multivariate polynomials are irreducible. The proof applies a technique of Shpilka & Volkovich [STOC 2008]. 2. We give a tight-in-some-sense characterization of when a multiqubit CZ gate creates or removes entanglement from the state it is applied to. The current paper strengthens an earlier version of the paper [arXiv:2005.12169].
We show that the parity of more than three non-target input bits cannot be computed by QAC-circuits of depth-2, not even uncleanly, regardless of the number of ancilla qubits. This result is incomparable with other recent lower bounds on constant-depth QAC-circuits by Rosenthal [ICTS~2021,arXiv:2008.07470] and uses different techniques which may be of independent interest: 1. We show that all members of a certain class of multivariate polynomials are irreducible. The proof applies a technique of Shpilka & Volkovich [STOC 2008]. 2. We give a tight-in-some-sense characterization of when a multiqubit CZ gate creates or removes entanglement from the state it is applied to. The current paper strengthens an earlier version of the paper [arXiv:2005.12169].
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
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.
The computational power of QAC, which are constant-depth 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 QAC circuits, where the qubits are arranged in a high-dimensional grid, and all the generalized Toffoli gates act on contiguous qubits along one direction. We prove that 2D-QAC circuits are universal: any QAC circuit can be exactly simulated by a two-dimensional geometrically local QAC circuit. Therefore, we focus on the computational power of 2D-QAC circuits with grid width w. We prove that PARITY computation has a tight width--depth tradeoff of w=nΘ(1/d) in the constant-depth regime if the circuit allows arbitrary ancilla. Moreover, for polynomial-size circuits, a width lower bound of nω(1/d) for PARITY would imply PARITY∈/QAC0. We also establish Fourier tail and sensitivity bounds, together with tight width lower bounds and tight depth lower bounds in 1D-QAC circuits for MAJORITY and MOD computation.
Our main tool is \emph{local measurement variance}, the maximum variance of normalized sums of observables on separated regions. We use a hybrid argument to show that each layer of a 2D-QAC0 circuit increases this variance by at most a factor depending only on its width, yielding a variance bound for every 2D-QAC0 state. The high local measurement variance of cat and Dicke states then gives the width lower bounds.
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.
It is well-known that every n-qubit unitary can be implemented by a 2O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth poly(n) with 2O(n) ancilla qubits. In other words, every n-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in n, which is the best possible, and an exponential improvement on the previous best bound of 2n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
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.