Bounds on the $\mathrm{QAC}^0$ Complexity of Approximating Parity

$\mathrm{QAC}$ circuits are quantum circuits with one-qubit gates and Toffoli gates of arbitrary arity. $\mathrm{QAC}^0$ circuits are $\mathrm{QAC}$ circuits of constant depth, and are quantum analogues of $\mathrm{AC}^0$ circuits. We prove the following: $\bullet$ For all $d \ge 7$ and $\varepsilon>0$ there is a depth-$d$ $\mathrm{QAC}$ circuit of size $\exp(\mathrm{poly}(n^{1/d}) \log(n/\varepsilon))$ that approximates the $n$-qubit parity function to within error $\varepsilon$ on worst-case quantum inputs. Previously it was unknown whether $\mathrm{QAC}$ circuits of sublogarithmic depth could approximate parity regardless of size. $\bullet$ We introduce a class of"mostly classical"$\mathrm{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 $\mathrm{QAC}$ circuits that approximate this component. $\bullet$ Arbitrary depth-$d$ $\mathrm{QAC}$ circuits require at least $\Omega(n/d)$ multi-qubit gates to achieve a $1/2 + \exp(-o(n/d))$ approximation of parity. When $d = \Theta(\log n)$ this nearly matches an easy $O(n)$ size upper bound for computing parity exactly. $\bullet$ $\mathrm{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.

• For all d ≥ 7 and ε > 0 there is a depth-d QAC circuit of size exp(poly(n 1/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 = Θ(log n) 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.

Background
A central problem in computational complexity theory is to prove lower bounds on the nonuniform circuit size required to compute explicit boolean functions. Since this appears to be out of reach given current techniques, research in circuit complexity has instead focused on proving lower bounds in restricted circuit classes. There are now many known lower bounds in classical circuit complexity, as well as in quantum query complexity, but comparatively few lower bounds are known in quantum circuit complexity, which is the subject of the current paper.
The study of quantum circuit complexity was initiated in large part by Green, Homer, Moore and Pollett [9], who defined quantum analogues of a number of classical circuit classes. One of the seemingly most restrictive quantum circuit classes that they defined is the class of QAC 0 circuits, consisting of constant-depth QAC circuits, where QAC circuits are quantum circuits with arbitrary one-qubit gates and generalized Toffoli gates of arbitrary arity. (More precisely, (n + 1)-ary generalized Toffoli gates are defined by |x, b → |x, b ⊕ n j=1 x j for x = (x 1 , . . . , x n ) ∈ {0, 1} n , b ∈ {0, 1}.) This is analogous to the classical circuit class of AC 0 circuits, consisting of constant-depth AC circuits, where AC circuits are boolean circuits with NOT gates and unbounded-fanin AND and OR gates. Low-depth circuits are a model of fast parallel computation, and this is especially important for quantum circuits, because quantum computations need to be fast relative to the decoherence time of the qubits in order to avoid error.
One difference between AC and QAC circuits is that AC circuits are allowed fanout "for free", i.e. the input bits to the circuit and the outputs of gates may all be used as inputs to arbitrarily many gates. The quantum analogue of this would be to compute the unitary "fanout" transformation U F , defined by U F |b, x 1 , . . . , x n−1 = |b, x 1 ⊕ b, . . . , x n−1 ⊕ b for b, x 1 , . . . , x n−1 ∈ {0, 1}, or at least to compute this in the case that we call "restricted fanout" in which x 1 = · · · = x n−1 = 0. QAC 0 circuits with fanout gates are called QAC 0 f circuits, and can simulate arbitrary AC 0 circuits by using ancillae and restricted fanout to make as many copies as needed of the input bits and of the outputs of gates. In fact, QAC 0 f circuits are strictly more powerful than AC 0 circuits, because QAC 0 f circuits (even without generalized Toffoli gates) of polynomial size can also compute threshold functions [12,15] whereas AC 0 circuits require exponential size to do so [11]. In contrast, little is known about the power of QAC 0 circuits and how it compares with that of AC 0 circuits.
Green et al. [9] observed that fanout can be computed by QAC circuits of logarithmic depth and linear size. This raises the question of whether QAC circuits of sublogarithmic depth can compute fanout, or at least restricted fanout, even if allowed arbitrary size. The same question can be asked about parity, which is a famous example of a function that requires exponential size to compute in AC 0 [11], and which is defined for quantum circuits as the unitary transformation U ⊕ such that U ⊕ |b, x = |b ⊕ n−1 j=1 x j , x for b ∈ {0, 1},  In fact, all of these questions are equivalent: Green et al. [9] proved that parity and fanout are equivalent up to conjugation by Hadamard gates (Fig. 1), and that they reduce to restricted fanout with linear blowups in size and depth (Fig. 2). Recent work [8,10] suggests that QAC 0 f may be a physically realistic model of constant depth computation in certain quantum computing architectures (such as ion traps). As for QAC lower bounds, Fang, Fenner, Green, Homer and Zhang [6] proved that QAC circuits with a ancillae require depth at least Ω(log(n/(a + 1))) to compute the n-qubit parity and fanout functions, which is a nontrivial lower bound when a = o(n). Bera [3] used a different approach to prove something slightly weaker than the a = 0 case of this result. Finally, Padé, Fenner, Grier and Thierauf [14] proved that QAC circuits with two layers of generalized Toffoli gates cannot cleanly 1 compute 4-qubit parity or fanout, regardless of the number of ancillae. A survey of Bera, Green and Homer [4] discusses some of the above QAC lower bounds and QAC f upper bounds in greater detail.

Definitions of Complexity Measures
Call | ψ|ϕ | 2 the fidelity of states |ϕ and |ψ . We define the size of a QAC circuit to be the number of multi-qubit gates in it, and the depth of a QAC circuit to be the number 1 A clean computation is one in which the ancillae end in the all-zeros state.
of layers of multi-qubit gates in it. One motivation for not counting single-qubit gates, besides mathematical convenience, is that size and depth can be interpreted as measures of the reliability and computation time of a quantum circuit respectively, and in practice multi-qubit gates tend to take more time to apply and have lower fidelity as compared to single-qubit gates.

Reductions to and from Constructing Nekomata
Recall that Green et al. [9] proved that parity, fanout, and restricted fanout are all equivalent up to low-complexity QAC reductions. In Section 3 we make the more general observation that clean approximate and non-clean approximate versions of these problems are all equivalent in this sense. For brevity's sake, here in Section 1.2 we will only state immediate corollaries of these reductions insofar as they relate to our other results.
We also introduce another problem equivalent to parity, which all of our results about parity and fanout are proved via reductions to. The state 1 √ 2 1 b=0 |b n is commonly called the cat state on n qubits, and we denote it by | n . More generally, call a state |ν an nnekomata if |ν = 1 √ 2 1 b=0 |b n , ψ b for some states |ψ 0 , |ψ 1 on any number of qubits (the word "nekomata" is also the name of two-tailed cats from Chinese and Japanese folklore), or equivalently if a standard-basis measurement of some n qubits of |ν outputs all-zeros and all-ones each with probability 1/2.
Call a QAC circuit C acting on any number of qubits a solution to the "p-approximate n-nekomata problem" if there exists an n-nekomata |ν such that C|0 . . . 0 and |ν have fidelity at least p. (We remark that there is no need to allow "ancillae" in this problem, because if |ν is an n-nekomata then so is |ν, ψ for any state |ψ .) Note that the identity circuit on n or more qubits trivially solves the 1/2-approximate n-nekomata problem. In informal discussions we will often say that a circuit "constructs an approximate nnekomata" if it solves the p-approximate n-nekomata problem for some fixed p ∈ (1/2, 1), say p = 3/4.
Constructing nekomata reduces to computing restricted fanout because | n = U F (H ⊗ I)|0 n . Our reduction from parity to constructing nekomata is a variant of Green et al.'s [9] reduction from parity to restricted fanout.

Upper Bounds
Theorem 1.1. For all ε > 0 there exists a depth-2 QAC circuit C such that for some n-nekomata |ν , the fidelity of C|0 . . . 0 and |ν is at least 1 − ε. Furthermore, the size of C and the number of qubits acted on by C are both exp(O(n log(n/ε))).
The d = 11 case of Corollary 1.2 follows immediately from Theorem 1.1 and our reduction from parity to constructing nekomata. We decrease the minimum depth from 11 to 7 using an optimization specific to the circuit from our proof of Theorem 1.1. We prove Corollary 1.2 for higher depths using the fact that n-qubit restricted fanout can be computed by a circuit consisting of d layers of n 1/d -qubit restricted fanout gates.
If we were to also count one-qubit gates toward size and depth, then statements similar to Theorem 1.1 and Corollary 1.2 would still hold, because without loss of generality a depth-d QAC circuit acting on m qubits has at most d + 1 layers of one-qubit gates and at most (d + 1)m one-qubit gates.

Tight Lower Bounds for Constructing Approximate Nekomata in "Mostly
Classical" Circuits Call a QAC circuit mostly classical if it can be written as CLM L † such that C consists only of generalized Toffoli gates, L is a layer of one-qubit gates, and M is a layer of generalized Toffoli gates. We remark that the circuit C here is a close analogue of (classical) AC circuits with bounded fanout, since generalized Toffoli gates can simulate classical AND and NOT gates. The following is apparent from our proof of Theorem 1.1: Remark 1.3. Theorem 1.1 remains true even if "QAC circuit" is replaced by "mostly classical QAC circuit".
Motivated by Remark 1.3, we prove the following lower bound for constructing approximate nekomata in mostly classical circuits: Theorem 1.4. Let C be a mostly classical circuit of size s and depth o(log n), acting on any number of qubits. Then for all n-nekomata |ν , the fidelity of C|0 . . . 0 and |ν is at most (See Theorem 4.2 for a more precise tradeoff between depth and fidelity.) In particular, Theorem 1.4 implies that mostly classical circuits of depth o(log n) require size at least exp(n 1−o(1) ) to construct approximate n-nekomata, essentially matching the exp(Õ(n)) size upper bound from Theorem 1.1 and Remark 1.3. This lower bound does not contradict the exp(n o(1) ) size upper bounds of depth ω(1) from Corollary 1.2, because our reductions between parity, fanout, and constructing nekomata do not in general map mostly classical circuits to mostly classical circuits. Since the identity circuit is mostly classical, the upper bound on the fidelity of C|0 . . . 0 and |ν in Theorem 1.4 is tight up to the value being exponentiated. Finally, we remark that if we also allow r-qubit parity and fanout gates in mostly classical circuits-a natural model for small values of r, in light of the upper bounds from Corollary 1.2-then a trivial generalization of our proof of Theorem 1.4 implies that an identical statement holds for circuits of depth o(log max(r,2) n).
Our proof of Theorem 1.4 goes roughly as follows. It suffices to prove that the Hamming weight of a standard-basis measurement of any n qubits of C|0 . . . 0 is concentrated around some value. We use the fact that standard-basis measurements commute with generalized Toffoli gates, and, after some preparation, apply a concentration inequality of Gavinsky, Lovett, Saks and Srinivasan [7].

Lower Bounds for Arbitrary QAC Circuits of Low Size and Depth
Call the first n qubits of an n-nekomata 1 √ 2 1 b=0 |b n , ψ b the targets of that nekomata.
Theorem 1.5. There is a universal constant c > 0 such that the following holds. Let C be a depth-d QAC circuit acting on any number of qubits, and let |ν be an n-nekomata such that at most cn/(d + 1) multi-qubit gates in C act on the targets of |ν . Then the fidelity of C|0 . . . 0 and |ν is at most 1/2 + exp(−Ω(n/(d + 1))).
(We remark that the +1 in exp(−Ω(n/(d + 1))) is necessary when C = H and |ν = |+ := |0 +|1 √ 2 , and that, perhaps surprisingly, a sharp "phase change" near the cn/(d + 1) threshold is in fact inherent to our proof.) For example, Theorem 1.5 implies that a depth-2 QAC circuit constructing an approximate n-nekomata must have at least Ω(n) multi-qubit gates acting on the targets of that nekomata. This Ω(n) lower bound is tight, because Theorem 1.1 says that depth-2 QAC circuits can construct approximate n-nekomata, and a depth-d QAC circuit can have at most nd multi-qubit gates acting on any given set of n qubits. Similarly, Corollary 1.6 implies that depth-7 QAC circuits approximating n-qubit parity, fanout, or restricted fanout require at least Ω(n) multi-qubit gates acting on the n "input" qubits, and this Ω(n) lower bound is tight as well by Corollary 1.2.
Theorem 1.5 also implies that the total number of multi-qubit gates, a.k.a. the size, of a depth-d QAC circuit constructing an approximate n-nekomata must be at least Ω(n/(d + 1)). When d ≤ o(log n), this lower bound is disappointingly far from the upper bounds of Theorem 1.1 and Corollary 1.2. However, Green et al. [9] observed that for some d = Θ(log n), a depth-d QAC circuit of size O(n) can construct an n-nekomata (specifically, the n-qubit cat state), so for this value of d our Ω(n/d) size lower bound is tight to within a logarithmic factor. Similarly, for some d = Θ(log n), the minimum size of a depth-d QAC circuit that approximates n-qubit parity, fanout, or restricted fanout is between Ω(n/ log n) and O(n), by Corollary 1.6 and upper bounds of Green et al.
If a QAC circuit has size s ≤ o( ). It follows from Theorem 1.5 and Corollary 1.6 that QAC circuits of arbitrary depth require size at least Ω( √ n) to construct approximate n-nekomata, or to approximately compute n-qubit parity, fanout, or restricted fanout. 2 Finally, we remark that Theorem 1.5 is actually a special case of a more general result, Theorem 5.3, about states |ψ such that for some orthogonal projections 3 Q 1 , . . . , Q n on arbitrary numbers of qubits, (For example, n-nekomata satisfy this criterion with Q j = |0 0| for all j.) We will comment on this generalization of Theorem 1.5 again in Section 1.2.7.

A Normal Form for Quantum Circuits
Integral to our proof of Theorem 1.5 is a certain normal form for QAC circuits. We believe that this normal form may be of independent interest, since the standard quantum circuit model is that of QAC circuits whose gates have maximum arity 2. Our normal form is described precisely in Section 2; here we will only give the underlying intuition, by way of analogy with well-known facts from classical circuit complexity. If we define AC circuits as consisting only of AND and NOT gates, then it cannot in general be assumed that the NOT 2 More generally, inspection of its proof reveals that Theorem 1.5 also holds if "depth" is replaced by "maximum number of multi-qubit gates acting on any one of the target qubits". This quantity is at most the total number of multi-qubit gates acting on all of the targets, so similar reasoning implies that QAC circuits of arbitrary depth require at least Ω( √ n) multi-qubit gates acting on the targets to construct approximate n-nekomata. It follows from our reductions that QAC circuits require at least Ω( √ n) gates acting on the n "input" qubits to approximately compute n-qubit parity, fanout, or restricted fanout.
gates are all adjacent to the inputs. However, by DeMorgan's laws we may equivalently allow OR gates in AC circuits as well, and then it can be assumed that the NOT gates are all adjacent to the inputs (with only a constant-factor blowup in size, and no blowup in depth). 4 Similarly, we introduce a certain further generalization of generalized Toffoli gates which allows us to assume that the one-qubit gates in a QAC circuit are all adjacent to the input.
Our proof of Theorem 1.7 gives a multiplicative constant of roughly 1/10 60000 implicit in the Ω(·) notation in the above inequalities, which makes them trivial for small values of n. If n is sufficiently large however, then Theorem 1.7 implies that depth-2 QAC circuits cannot approximate n-qubit parity, fanout, or restricted fanout, or approximately construct the n-qubit cat state, even if these approximations are not required to be clean. Still taking n to be sufficiently large, this improves on the previously mentioned result of Padé et al. [14] that depth-2 QAC circuits cannot cleanly compute parity exactly on four or more qubits. Theorem 1.7 and Corollary 1.2 imply that for all sufficiently large n, the minimum depth of a QAC circuit approximating n-qubit parity is between 3 and 7 inclusive, and likewise for fanout, restricted fanout, and constructing the cat state. By Theorem 1.1 there is a depth-2 QAC circuit that constructs an approximate n-nekomata for all n, so any proof of Theorem 1.7 must use some property of | n , ψ that does not hold for an arbitrary n-nekomata. Ours uses a property similar to the fact that if we measure some of the qubits in the "B" register of | n A ⊗ |ψ B in an arbitrary basis, then the resulting state in registers A and B is still an n-nekomata.
Our proof of Theorem 1.7 mostly uses different techniques than those of Padé et al. An exception is the observation, of which we will use a generalization, that if we define a "generalized Z gate" on any number of qubits by Z = I − 2|1 . . . 1 1 . . . 1| then Z|0, φ = |0, φ and Z|1, φ = |1 ⊗ Z|φ for all states |φ . We also incorporate a variant of the proof given by Bene Watts, Kothari, Schaeffer and Tal [2, Theorem 16] that there is no QNC circuit (QAC circuit whose gates have maximum arity 2) of depth o(log n) that maps |0 . . . 0 to | n , 0 . . . 0 : Using a "light cone" argument they prove that out of any n output qubits, there are at least two whose standard-basis measurements would be independent, but the standard-basis measurements of any two qubits in | n are dependent.
Our proof of Theorem 1.7 goes roughly as follows. If there are only o(n) multi-qubit gates acting on the n targets of | n , ψ then the result follows from Theorem 1.5. Otherwise, out of the multi-qubit gates acting on a nonzero number of targets, the average gate acts on O(1) targets, as would be the case in a QNC circuit. Using a variant of a light cone argument, we choose Θ(n) pairwise disjoint sets of qubits on which to define orthogonal projections, and apply the generalization of Theorem 1.5 that was mentioned at the end of Section 1.2.5.

Organization
In Section 1.4 we introduce some miscellaneous notation and definitions. In Section 2 we give multiple equivalent characterizations of QAC circuits, including the previously mentioned normal form, and introduce some related definitions which we will use in more general contexts as well. In Section 3 we give reductions between parity, fanout, restricted fanout, and constructing nekomata; we also use these reductions to prove that the d ≥ 11 case of Corollary 1.2 follows from Theorem 1.1, that Corollary 1.6 follows from Theorem 1.5, and that Theorems 1.7(i) and 1.7(ii) follow from Theorem 1.7(iii). In Section 4 we prove our upper and lower bounds for constructing approximate nekomata in mostly classical circuits, Theorems 1.1 and 1.4. In Section 5 we prove our other main results, Theorems 1.5 and 1.7(iii). In Appendix A we prove the d < 11 case of Corollary 1.2.
Out of Sections 3 to 5, occasionally a later section will reference a self-contained lemma from an earlier section, but otherwise these sections may be read in any order. Appendix A relies on content from Sections 3 and 4.

Preliminaries
We write log and ln to denote the logarithms base 2 and e respectively, and (x j ) j to denote the tuple of all x j for j in some implicit index set. Also let [n] = {1, . . . , n} and ψ = √ ψ * ψ, i.e. · denotes the 2-norm. Anything written as ·| or |· is implicitly unit-length.
Orthogonal projections are linear transformations Q such that Q = Q 2 = Q † . For an orthogonal projection Q and a state |ϕ , we call ϕ|Q|ϕ "the probability that |ϕ measures to Q". If Q = |ψ ψ| then we also call this "the probability that |ϕ measures to |ψ ", and it equals | ψ|ϕ | 2 , a.k.a. the fidelity of |ϕ and |ψ . More generally, if Q is an orthogonal projection on some Hilbert space H then we call ϕ|(Q ⊗ I)|ϕ "the probability that the H qubits of |ϕ measure to Q".
We use standard notation for the Hadamard basis states Figure 3: The multi-qubit gates on the left and right are OR and generalized Toffoli gates respectively, whose target qubits are on the bottom wire.
denote the identity transformation, I H for the identity on the Hilbert space H, and I n for the identity on some n-qubit Hilbert space.
To be thorough, we remind the reader that an n-nekomata is a state with n qubits (called targets) that measure to 0 n and to 1 n each with probability 1/2, or equivalently a state of the form 1 √ 2 1 b=0 |b n , ψ b for some states |ψ 0 , |ψ 1 on any number of qubits. For example, the n-qubit cat state is the state | n = (|0 n + |1 n )/ √ 2.

QAC Circuits
Consider a quantum circuit C, written as C = L d M d · · · L 1 M 1 L 0 such that each L k consists only of one-qubit gates and each M k is a layer (tensor product) of multi-qubit gates. We may assume that each L k is a single layer as well, because the product of one-qubit gates is also a one-qubit gate. Define the size of C to be the number of multi-qubit gates in C, the depth of C to be the number of layers of multi-qubit gates in C (in this case, d), and the topology of C to be the set of pairs (S, k) such that S equals the support of some gate in M k , where the support of a gate is the set of qubits acted on by that gate. Note that the topology of C encodes its depth, size, and more generally the number of multi-qubit gates acting on any given set of qubits.
Recall that QAC circuits are quantum circuits with arbitrary one-qubit gates and generalized Toffoli gates of arbitrary arity, where (n + 1)-ary generalized Toffoli gates are , and call the qubit corresponding to b in these definitions the target qubit of the gate. By the construction of an OR gate from a generalized Toffoli gate and NOT gates in Fig. 3, we may add OR gates to the set of allowed gates when defining QAC circuits, without changing the set of topologies of QAC circuits computing any given unitary transformation.
For a state |θ let R |θ = R θ = I − 2|θ θ| (the R stands for "reflection"). Let a mono-product state be a tensor product of any number of one-qubit states. When |θ is a mono-product state we call R θ an R ⊗ gate. For example, an (n+1)-qubit generalized Toffoli gate equals R |1 n ,− , because it acts on the basis {|0 , |1 } ⊗n ⊗ {|+ , |− } by multiplying |1 n , − by -1 and leaving all other states in this basis unchanged.
Consider an (n + 1)-qubit mono-product state |θ , and let L be a layer of one-qubit gates such that |θ = L|1 n , − . Then, i.e. R θ equals the conjugation of a generalized Toffoli gate by a layer of one-qubit gates. (We remark that Fang et al. [6] observed Eq. (1) in the case where |θ = |1 n+1 and L = I n ⊗ H.) Therefore, similarly to the above, we may add arbitrary R ⊗ gates to the set of allowed gates when defining QAC circuits.
In fact, a stronger statement holds. Let a QAC circuit be in R ⊗ normal form if it can be written as CL such that C consists only of multi-qubit R ⊗ gates and L is a layer of single-qubit gates. We will use the following in Section 5: Proposition 2.1. Every QAC circuit computes the same unitary transformation as a circuit in R ⊗ normal form with the same topology.
Proof. The proof is by induction on the depth d of a QAC circuit C. If d = 0 then C is a layer of one-qubit gates, which is already in R ⊗ normal form. Otherwise write C = LM D such that L is a layer of one-qubit gates, M is a layer of multi-qubit generalized Toffoli gates, and D is a depth-(d − 1) QAC circuit. Since C = LM L † LD, it suffices to prove that LD is equivalent to a circuit in R ⊗ normal form with the same topology as D, and that LM L † is equivalent to a layer of R ⊗ gates that has the same topology as M . The first claim follows from the inductive hypothesis. To prove the second claim, note that where G ranges over all gates in M , and L G is the tensor product of the gates in L that act on the support of G. Then apply Eq. (1).

Reductions to and from Constructing Nekomata
The high-level idea of this section may be obtained relatively quickly by inspecting the beginning of Section 3.2 (in particular, Fig. 5) and perhaps also Lemma 3.9, assuming familiarity with certain content from Section 1. Most of the rest of the current section consists of routine calculations.
We will define "p-approximate" versions of the parity, fanout, restricted fanout, cat, and nekomata problems for all p ∈ [0, 1], and prove the following: there is a QAC circuit of size s, depth d, and number of qubits acted on a that solves the (1 − ε)-approximate n-nekomata problem, then there is a QAC circuit of size O(s + n), depth 4d + 3, and number of ancillae a that solves the (1 − O(ε))-approximate (n + 1)-qubit clean parity problem.
For every non-red 5 arrow from a problem P to a problem Q in Fig. 4, if a QAC circuit C solves p-approximate, n-qubit P then there is a QAC circuit with the same topology as C that solves p-approximate, n-qubit Q. (If Q is the nekomata problem then substitute "n-nekomata" for "n-qubit nekomata" here.) Furthermore, if this arrow is dashed then C itself solves p-approximate, n-qubit Q. In Section 3.1 we define the problems mentioned in Theorem 3.1, and prove all of Theorem 3.1 except for the reduction from clean parity to constructing nekomata. In Section 3.2 we reduce clean parity to constructing nekomata. In Section 3.3 we prove that Theorem 1.1 implies the d ≥ 11 case of Corollary 1.2, i.e. we construct depth-d QAC circuits (of size decaying with d) for approximate parity, fanout, and cat in terms of depth-2 QAC circuits for approximate nekomata. It is easy to prove Corollary 1.6 assuming Theorem 1.5, and to prove Theorems 1.7(i) and 1.7(ii) assuming Theorem 1.7(iii), using reasoning similar to that in Section 3.1.

Problem Definitions and Most Reductions
Recall that we define the phase-dependent fidelity of states |ϕ and |ψ to be 1− |ϕ −|ψ 2 . This quantity is at most the fidelity of |ϕ and |ψ , because The following two definitions are with respect to an arbitrary unitary transformation U on n qubits: Construct a circuit C on at least n qubits such that for all n-qubit states |φ , the phase-dependent fidelity of C|φ, 0 . . . 0 and U |φ ⊗|0 . . . 0 is at least p. Problem 3.3 (p-approximate Dirty U ). Construct a circuit C on at least n qubits such that for all n-qubit states |φ , the first n qubits of C|φ, 0 . . . 0 measure to U |φ with probability at least p.
Any circuit that computes p-approximate clean U also computes p-approximate dirty U , because the probability that the first n qubits of C|φ, 0 . . . 0 measure to U |φ is at least the probability that C|φ, 0 . . . 0 measures to U |φ ⊗ |0 . . . 0 , a.k.a. the fidelity of these two states, which is at least their phase-dependent fidelity.
Given n, recall that the unitary transformations for n-qubit parity and fanout are defined respectively by U ⊕ |b, Define the clean and dirty versions of approximating n-qubit parity and fanout as instances of Problems 3.2 and 3.3 with respect to U ⊕ and U F .
Recall also that H ⊗n U ⊕ H ⊗n = U F (see Fig. 1) [9]. We will henceforth write "(p, n)" as an abbreviation for "p-approximate, n-qubit". If a circuit C ⊕ computes (p, n) clean parity then the circuit Here we made the substitution |ϕ = H ⊗n |φ , and used the facts that H 2 = I and that applying a unitary transformation to a vector does not change the norm of that vector. Similarly, if C ⊕ computes (p, n) dirty parity then the same circuit C F given above computes (p, n) dirty fanout, because Problem 3.4 (p-approximate Clean Restricted Fanout). Construct a circuit C on at least n qubits such that for all one-qubit states |φ , the phase-dependent fidelity of C|φ, 0 n−1 , 0 . . . 0 and U F |φ, 0 n−1 ⊗ |0 . . . 0 is at least p.
Problem 3.5 (p-approximate Dirty Restricted Fanout). Construct a circuit C on at least n qubits such that for all one-qubit states |φ , the first n qubits of C|φ, 0 n−1 , 0 . . . 0 measure to U F |φ, 0 n−1 with probability at least p.
A circuit computing (p, n) clean (resp. dirty) fanout trivially computes (p, n) clean (resp. dirty) restricted fanout, and similarly to the above, a circuit computing (p, n) clean restricted fanout also computes (p, n) dirty restricted fanout. Problem 3.6 (p-approximate Clean | n ). Construct a circuit C on at least n qubits such that the phase-dependent fidelity of C|0 . . . 0 and | n , 0 . . . 0 is at least p.
Problem 3.7 (p-approximate Dirty | n ). Construct a circuit C on at least n qubits such that the first n qubits of C|0 . . . 0 measure to | n with probability at least p.
By making the substitution |φ = |+ in Problems 3.4 and 3.5 and using the fact that | n = U F |+, 0 n−1 , it is easy to see that if a circuit C computes (p, n) clean (resp. dirty) restricted fanout then the circuit C(H ⊗ I) solves the (p, n) clean (resp. dirty) cat problem. Similarly to the above, a circuit solving the (p, n) clean cat problem also solves the (p, n) dirty cat problem. Finally, recall the following: Problem 3.8 (p-approximate n-Nekomata). Construct a circuit C such that for some n-nekomata |ν , the fidelity of C|0 . . . 0 and |ν is at least p.
Any circuit C solving the (p, n) dirty cat problem also solves the p-approximate nnekomata problem, because the probability that the initial qubits of C|0 . . . 0 measure to | n equals the maximum over all states |ψ of the fidelity of C|0 . . . 0 and | n , ψ , and the latter state is an n-nekomata.

Reducing Clean Parity to Constructing Nekomata
First we reduce exact (n + 1)-qubit clean parity to the exact n-nekomata problem. Let C be a circuit on a qubits such that |ν := C|0 a is an n-nekomata. A circuit for exact (n + 1)-qubit clean parity is shown in Fig. 5, where the top n wires acted on by each of the C and C † subcircuits correspond to the targets of |ν . Between times 1 and 2, and also between times 5 and 6, is a layer of n copies of R |11 , the i'th of which acts on the wires corresponding to the i'th input qubit and the i'th target of |ν for i ∈ [n]. The gate R |11 is better known as a controlled Z gate, and acts as |xy → (−1) xy |xy for x, y ∈ {0, 1}. Between times 3 and 4 is an OR gate (recall Fig. 3).
Let |ν ⊥ = ((|0 n 0 n |−|1 n 1 n |)⊗I a−n )|ν and |ψ = C † |ν ⊥ . Then 0 a |ψ = 0 a |C † |ν ⊥ = ν|ν ⊥ = 1/2 − 1/2 = 0, so |ψ is a superposition of standard basis states with Hamming weight at least 1. It follows that if |φ is an n-qubit standard basis state with parity c, and if b is a classical bit, then the table in Fig. 5 indicates the state at each time in the computation. Therefore the circuit in Fig. 5 correctly computes parity on the input |φ, b , so by linearity this circuit correctly computes parity on arbitrary inputs.
Remark. The truncation of the circuit in Fig. 5 at time 4 does not compute dirty parity, because if |φ is a superposition of standard basis states with different parities then at time 4 the ancillae are entangled with the input qubits. Now assume only that there exists an n-nekomata |ν such that | ν|C|0 a | 2 ≥ 1 − ε. Without loss of generality, multiply |ν by a phase factor so that ν|C|0 a is a nonnegative real, i.e. ν|C|0 a ≥ √ 1 − ε ≥ 1 − ε. To prove that the circuit D from Again let |ν ⊥ = ((|0 n 0 n | − |1 n 1 n |) ⊗ I a−n )|ν , and now let |ψ = (I−|0 a 0 a |)C † |ν ⊥ (I−|0 a 0 a |)C † |ν ⊥ . Since ν|ν ⊥ = 0 and 0 a |ψ = 0, there exists an a-qubit unitary transformation U such that U |0 a = |ν and U |ψ = |ν ⊥ . For t ∈ [7] let L t be the subcircuit between times t − 1 and t in Fig. 5, and let M t be the circuit formed by substituting U for C and U † for C † in L t . Fix some b and c, and let |φ = |φ b,c . Then, by the triangle inequality, If c = 1 then and it follows from Eq. (3) that 3.3 Proof of Corollary 1.2 (d ≥ 11) assuming Theorem 1.1 Lemma 3.9. For all m ≥ 2 there is a quantum circuit of depth log m n and size at most n − 1, consisting only of restricted fanout gates of arity at most m, that computes n-qubit restricted fanout exactly using no ancillae.
The m = 2 case of Lemma 3.9 was observed by Green et al. [9]. Proof of Corollary 1.2 (d ≥ 11) assuming Theorem 1.1. Recall that Theorem 1.1 states that for all ε > 0, the (1−ε)-approximate n-nekomata problem is solvable by a depth-2 QAC circuit of size and number of qubits acted on exp(O(n log(n/ε))). It follows from Theorem 3.1 that for all ε > 0, the (1 − ε)-approximate n-qubit clean parity, fanout, and cat problems are solvable by depth-11 QAC circuits of size and number of ancillae exp(O(n log(n/ε))). Now let ε > 0 and N, d ∈ N, and let n = N 1/d . By Lemma 3.9 there exists a depth-d circuit of size at most N − 1, consisting only of (≤ n)-ary restricted fanout gates, that computes N -qubit restricted fanout exactly using no ancillae. Replace each gate in this circuit with the aforementioned depth-11 QAC circuit computing (1 − ε)-approximate clean restricted fanout on the appropriate number of qubits. The result is a depth-11d QAC circuit of size and number of ancillae (N − 1) · exp(O(n log(n/ε))), and by reasoning similar to that in Section 3.2 it computes (1 − O(N 2 ε))-approximate N -qubit clean restricted fanout. It follows from Theorem 3.1 that there exist depth-O(d) QAC circuits of size and number of ancillae O(N ) · exp(O(n log(n/ε))) that compute (1 − O(N 2 ε))-approximate N -qubit clean parity and fanout. Finally, given ε > 0 and a sufficiently large value d , substituting appropriate values ε = Θ(ε /N 2 ) and d = Θ(d ) into the above gives depthd QAC circuits solving the (1 − ε )-approximate N -qubit clean parity, fanout, and cat problems, where the size and number of ancillae are exp(poly(N 1/d ) log(N/ε )) (using the fact that n ≤ N 1/d + 1 = poly(N 1/d )).

Tight Bounds for Constructing Approximate Nekomata in "Mostly Classical" Circuits
Call a QAC circuit purely classical if it consists only of generalized Toffoli gates (perhaps including NOT gates, which are generalized Toffoli gates on one qubit). Call a QAC circuit mostly classical if it can be written as CL such that C is purely classical and L is a layer of R ⊗ gates; by Eq. (1) this is equivalent to the definition from Section 1.2.4. Call a mostly classical QAC circuit nice if it can be written as CL in this way such that every multi-qubit gate R θ in L satisfies | 0 . . . 0|θ | 2 ≤ 1/4. (The niceness condition will allow us to express certain quantities as convex combinations in a convenient way, by ensuring that the coefficients in these convex combinations are between 0 and 1.) We prove the following generalizations of Theorems 1.1 and 1.4 respectively:  (ii) Regardless of whether C is nice, the fidelity of C|0 . . . 0 and |ν is at most Theorems 4.2(i) and 4.1 imply that for d ≥ 2, the minimum size of a nice, mostly classical, depth-d QAC circuit that "constructs an approximate n-nekomata" (i.e. maps |0 . . . 0 to a state that has fidelity at least 3/4 with some n-nekomata) is between exp(Ω(n/2 d )) and exp(Õ(n/2 d )) + O(n). We prove the d > 2 case of Theorem 4.1 solely for the sake of comparison with Theorem 4.2(i), as Theorem 4.1 gives a weaker upper bound than Corollary 1.2 when ω(1) ≤ d ≤ o(log n). Theorem 4.2 makes a stronger statement about nice circuits than about non-nice circuits, since a/ max(log s, √ a) = min(a/ log s, √ a) for all a > 0.
In Section 4.1 we make some general observations about mostly classical circuits and "approximate nekomata", including observations common to the proofs of Theorems 4.1 and 4.2. In Section 4.2 we prove Theorem 4.1, and in Section 4.3 we prove Theorem 4.2(i). We prove Theorem 4.2(ii) in Appendix B, because its proof has a similar high-level idea to that of Theorem 4.2(i) and is much more complicated.

Reduction to a Classical Sampling Problem
Collectively, the following observations reduce proving Theorems 4.1 and 4.2 to proving upper and lower bounds respectively for a certain type of sampling problem. This sampling problem can be succinctly characterized in purely classical and probabilistic terms, with only a transient reference to quantum circuits.
Recall that nekomata can be defined as states for which a standard-basis measurement of the targets is distributed in a certain way. The following two lemmas make similar statements about "approximate nekomata", and are used to prove Theorems 4.1 and 4.2 respectively: Lemma 4.3. Let |ϕ be a state with n "target" qubits that measure to all-zeros with probability exactly 1/2 and all-ones with probability at least 1/2 − ε/1.5. Then there exists an n-nekomata |ν such that | ν|ϕ | 2 ≥ 1 − ε.
Proof. Let Q b = |b n b n |⊗I for b ∈ {0, 1}. By the triangle inequality and Cauchy-Schwartz, Consider a mostly classical circuit, written as CL such that C is purely classical and L is a layer of R ⊗ gates. A standard-basis measurement of designated "target" qubits of CL|0 . . . 0 is distributed identically to an appropriate marginal distribution of a standardbasis measurement of all qubits of CL|0 . . . 0 . It is easy to see that standard-basis measurements commute with generalized Toffoli gates, so we may first measure L|0 . . . 0 in the standard basis and then apply C to the result.
For mostly classical circuits that are nice, the following is a more convenient characterization of this distribution:

Proof of Theorem 4.1
We first prove the depth-2 case of Theorem 4.1, i.e. that there exists a nice, mostly classical, depth-2 QAC circuit C of size and number of qubits acted on exp(O(n log(n/ε))) such that C|0 . . . 0 and some n-nekomata have fidelity at least 1 − ε. We then reduce the general case of Theorem 4.1 to the depth-2 case.
Proof of Theorem 4.1 (d = 2). Let M ∈ N and δ ∈ (0, 1) be parameters to be chosen later. 6 The circuit acts on n(M + 1) qubits, all initialized to |0 , and arranged in a grid of dimensions n × (M + 1) (see Fig. 6). Designate one column as the "target" column, and call the qubits in the M other columns "ancillae". First, to each ancilla column, apply R ( √ δ|0 + √ 1−δ|1 ) ⊗n . Second, to each row, apply an (M + 1)-qubit OR gate whose target qubit is in the target column. (A layer of OR gates is a depth-1 purely classical circuit, by the construction in Fig. 3.) All measurements described below are with respect to the state on the ancillae between the first and second layers of the above circuit. By Lemma 4.3 it suffices to choose M and δ such that if we measure the ancillae in the standard basis, then with probability exactly 1/2 all of the ancillae measure to 0, and with probability at least 1/2 − ε/1.5 at least one ancilla in each row measures to 1. We now choose δ in terms of M such that the ancillae measure to all-zeros with probability 1/2. By Lemma 4.5 and the independence of measurements of different columns, it suffices to ensure that (1 − 2δ n ) 2M = 1/2. Choose δ ∈ (0, (1/2) 1/n ) that satisfies this equation. Below we will choose M such that the probability that there exists an ancilla column measuring to neither all-zeros nor all-ones is at most ε/1.5. It follows that with probability at least 1 − ε/1.5, every ancilla column measures to either all-zeros or all-ones. Since the ancillae measure to all-zeros with probability 1/2, it follows that with probability at least 1/2 − ε/1.5, every ancilla column measures to all-zeros or all-ones and at least one ancilla column measures to all-ones. Therefore the probability is at least 1/2 − ε/1.5 that at least one ancilla in every row measures to 1, as desired.
By Lemma 4.5 and a union bound, the probability that there exists an ancilla column measuring to neither all-zeros nor all-ones is at most To make this bound at most ε/1.5, let M = 0.25 ln(2) · (1.5 ln(2)n/ε) n ≤ exp(O(n log(n/ε))).
Recall that Theorem 4.1 states that for all 2 ≤ d ≤ log n and ε > 0, there exists a nice, mostly classical, depth-d QAC circuit C of size and number of qubits acted on exp(O(n2 −d log(n2 −d /ε))) + O(n) such that C|0 . . . 0 has fidelity at least 1 − ε with some n-nekomata.
Proof of Theorem 4.1 (for arbitrary d). Since a two-qubit generalized Toffoli gate (a.k.a. a C-Not gate) computes two-qubit restricted fanout, 7 it follows from Lemma 3.9 that Nqubit restricted fanout is computable by a purely classical circuit of depth log N , size N − 1, and no ancillae. Use the circuit from the depth-2 case of Theorem 4.1 to construct a state |ϕ that has fidelity at least 1 − ε with some m-nekomata for m = n/2 d−2 , and initialize n − m additional qubits to |0 n−m . Partition the m targets of |ϕ (more precisely, the targets of the m-nekomata approximated by |ϕ ) and the n − m new qubits into m sets, each of size at most n/m ≤ 2 d−2 , and each including one of the targets of |ϕ . To each of these sets of qubits, apply the depth-(≤ d − 2) circuit for restricted fanout described above, where the qubit being "fanned out" is the target of |ϕ in that set.

Proof of Theorem 4.2(i)
We use the following concentration inequality of Gavinsky, Lovett, Saks and Srinivasan [7]: Remark. For example, if r = 1 then Y 1 , . . . , Y n are all independent and so Theorem 4.8 recovers a well-known Chernoff bound for sums of independent Bernoulli random variables. Theorem 4.8 also recovers this Chernoff bound when n = rm and Y j = X j/r for all j [7].
Consider a string x of independent Bernoulli random variables. If G is a generalized Toffoli gate then G|x is a read-2 family, because for all i the i'th bit of x can only influence the i'th and target bits of G|x . More generally, if G is a generalized Toffoli gate and L 1 , L 2 are layers of NOT gates acting on subsets of the support of G, then L 1 GL 2 |x is a read-2 family. Even more generally, it follows by induction that if C is a depth-d purely classical circuit then C|x is a read-2 d family.
Proof. It follows from the above discussion that a standard-basis measurement of any n designated target qubits of C|φ is a read-2 d family. 8 If the expected Hamming weight of a standard-basis measurement of the targets of C|φ is less (resp. greater) than or equal to n/2, then Theorem 4.8 implies that the targets of C|φ measure to all-ones (resp. all-zeros) with probability at most exp(−Ω(n/2 d )), and the result follows from Lemma 4.4.
Recall that Theorem 4.2(i) states that if C is a nice, mostly classical circuit of size s and depth d, then for all n-nekomata |ν , Proof of Theorem 4.2(i). Designate n qubits of C|0 . . . 0 as targets, and assume without loss of generality that s ≥ exp n/2 d . We will prove that for some a ∈ {0, 1}, the targets of C|0 . . . 0 measure to a n with probability at most exp(−Ω(n2 −d / log s)). The result then follows from Lemma 4.4. Write C = D(L ⊗ G∈G G) such that D is purely classical, L is a layer of singlequbit gates, and G is a set of multi-qubit R ⊗ gates that each satisfy the precondition of Corollary 4.6. For all G ∈ G, a standard-basis measurement of G|0 . . . 0 is distributed By a union bound, the probability that there exists G ∈ G such that µ G > 2 ln s and b G = 1 is at most Therefore it suffices to prove that for some a ∈ {0, 1}, the targets of |ϕ := D(L ⊗ G:µ G ≤2 ln s G ⊗ I)|0 . . . 0 measure to a n with probability at most exp(−Ω(n2 −d / log s)). Henceforth we will never refer to any gate G for which µ G > 2 ln s; phrases such as "for all G" and "(· G ) G " will implicitly quantify over only those gates G for which µ G ≤ 2 ln s.
where c > 2 is a universal constant large enough so that e(2e/c) c < 1. A well-known Chernoff bound states that if S is a sum of independent Bernoulli random variables, and µ = E[S], then P (S > t) < (eµ/t) t e −µ for all t > µ. Therefore, by a union bound and the fact that max G µ G ≤ 2 ln s, the probability that x fails to be good is at most  For r 1 , r 2 ∈ R let r 1 ≈ r 2 if |r 1 − r 2 | ≤ 0.1n. Let W (b, z) be the Hamming weight of the output bits as a function of b and z := (x, y), and let z be an independent copy of z. We now argue that where the probability is over (b, z, z ), and the expectations are over independent copies of z and b respectively, substituted for "·" as inputs to W . For any fixed value of b, Theorem 4.8 implies that W (b, z) ≈ E[W (b, ·) | b] except with probability at most exp(−Ω(n2 −d )) over z, and the same statement holds with z in place of z. Similarly, for any fixed value of z = (x , y ) such that x is good, Theorem 4.8 implies that W (b, z ) ≈ E[W (·, z ) | z ] except with probability at most exp(−Ω(n2 −d / log s)) over b. Since x is good except with probability at most exp(−Ω(n2 −d / log s)), Eq. (4) follows from a union bound.
Therefore, by the triangle inequality, where the probability is over (b, z, z ). It follows that there exists a fixed value of z such that the above inequality holds with the probability being over (b, z). For this fixed value of z , if E[W (·, z ) | z ] is at most (resp. at least) n/2, then the output bits are all-ones (resp. all-zeros) with probability at most exp(−Ω(n2 −d / log s)).

Lower Bounds for General QAC Circuits
In Section 5.1 we prove a technical lemma, which in Section 5.2 we use to prove a generalization of Theorem 1.5. Then, using this generalization of Theorem 1.5, in Sections 5.3 and 5.4 we prove Theorem 1.7(iii). Remark. More generally, Lemma 5.1 holds if the |ψ j are unit vectors in a real or complex Euclidean space of arbitrary finite dimension that is not necessarily a power of 2.
Since for all j ∈ [d], it follows that f (|ψ 1 , . . . , |ψ d−1 ) = cos(θ) d as desired. Now we prove that the above construction is optimal. The maximum of f exists because f is continuous and its domain, i.e. (d − 1)-tuples of unit vectors in some finite-dimensional Hilbert space, is compact. Therefore it suffices to start with a point ψ = (|ψ 1 , . . . , |ψ d−1 ) where f achieves its maximum, make finitely many changes to ψ that do not decrease f (ψ), and observe that the result is equivalent to the above construction.
More generally, Proposition 5.2. For all positive integers d, orthogonal projections Q d , and states |φ , where the maximum is taken over all orthogonal projections Q 1 , . . . , Q d−1 .
Proof. The claim is trivial when Q d = 0, so assume Q d = 0. The equality is proved by a reduction to Lemma 5.1. For j ∈ [d − 1] we may assume that Q j is rank-1, because Q j · · · Q 1 |φ = |θ j θ j |Q j−1 · · · Q 1 |φ for |θ j = 5.2 Proof of Theorem 1.5 Theorem 1.5 is the case of the following in which H 1 , . . . , H n are single-qubit Hilbert spaces, |φ is the all-zeros state, Q j = |0 0| for all j, and |ψ is an n-nekomata.
There is a universal constant c > 0 such that the following holds. Let H 1 , . . . , H n be Hilbert spaces, let H T = n j=1 H j (for "targets"), and let H A be a Hilbert space (for "ancillae"). Let |φ = |φ 1 , . . . , φ n , φ A for some states |φ j ∈ H j , j ∈ [n] ∪ {A}. Let Q j be an orthogonal projection on H j for j ∈ [n], and let |ψ be a state in H T ⊗ H A that measures to n j=1 Q j ⊗ I H A and to n j=1 (I − Q j ) ⊗ I H A each with probability 1/2. Let C be a depth-d QAC circuit on H T ⊗ H A with at most cn/(d + 1) multi-qubit gates acting on H T . Then, | ψ|C|φ | 2 ≤ 1/2 + exp(−Ω(n/(d + 1))).
Proof. By Proposition 2.1 we may write C = DL for some layer of single-qubit gates L and QAC circuit D, where D has the same topology as C and consists only of multi-qubit R ⊗ gates. Since L|φ factors as a product state in the same way that |φ does, we may assume without loss of generality that C consists only of multi-qubit R ⊗ gates, by replacing C and |φ with D and L|φ respectively.
Let G be the set of gates in C, ordered such that C = G∈G G (where each gate G is implicitly tensored with the identity). Also let G T ⊆ G be the set of gates in C that act on H T . For G ∈ G T let |θ G be the mono-product state, specified up to a phase factor, such that G = R θ G = I − 2|θ G θ G |. Let F be the set of functions f on G such that if G ∈ G T then f (G) is either I or |θ G θ G |, and if G ∈ G\G T then f (G) = G. Then , so by the triangle inequality, Recall the assumption that |G T | ≤ cn/(d + 1), for a constant c to be specified later. It follows that Consider an arbitrary function f ∈ F . For all G ∈ G we may write f (G) = f T (G) ⊗ f A (G), where f T (G) is a tensor product of one-qubit orthogonal projections on H T , and f A (G) is either an orthogonal projection or a unitary transformation on H A . (This can be seen by considering all three cases: f (G) = I, f (G) = |θ G θ G |, or G / ∈ G T and f (G) = G.) Furthermore, if G / ∈ G T then f T (G) = I. Therefore, letting |φ T = |φ 1 , . . . , φ n , .

Simplifying Depth-2 QAC Circuits by Measuring Ancillae
For a one-qubit state |ψ , let the |ψ basis be an orthonormal basis of C 2 that includes |ψ . (We refer to "the" |ψ basis because, up to a phase factor, there is a unique state orthogonal to |ψ .) Lemma 5.4. Let H 1 be a one-qubit Hilbert space, and let H 2 and H 3 be Hilbert spaces on arbitrary numbers of qubits. Then for all |ψ ∈ H 1 , |θ ∈ H 2 , |φ ∈ H 1 ⊗ H 2 ⊗ H 3 , the following two procedures generate identically distributed random states in H 1 ⊗ H 2 ⊗ H 3 : -measure the H 1 qubit of (R |ψ,θ ⊗ I H 3 )|φ in the |ψ basis; -measure the H 1 qubit of |φ in the |ψ basis, and then, conditioned on the outcome being |ψ , apply R θ on H 2 .
Proof. This follows easily from the fact that R |ψ,θ = (I − |ψ ψ|) ⊗ I + |ψ ψ| ⊗ R θ . Theorem 1.7(iii) is clearly equivalent to the statement that if C is a depth-2 QAC circuit, then any n designated "target" qubits of C|0 . . . 0 measure to | n with probability at most 1/2 + exp(−Ω(n)). The following is the starting point for our proof: Proposition 5.5. Let p and |ψ be such that for some depth-2 QAC circuit C, designated "target" qubits of C|0 . . . 0 measure to |ψ with probability p. Then there exist layers of R ⊗ gates L 2 , L 1 and a mono-product state |φ such that for some partition of the qubits of L 2 L 1 |φ into "targets" and "ancillae", (i) the targets of L 2 L 1 |φ measure to |ψ with probability at least p; (ii) for all k ∈ {1, 2}, every ancilla is acted on by a gate in L k , and every gate in L k acts on at least one target.
Remark. Although not necessary for our purposes, it follows from Proposition 2.1 that the gates in L 2 and L 1 may be assumed to be multi-qubit gates.

Proof of Theorem 1.7(iii)
The δ = 1 case of the following is Markov's inequality: Lemma 5.6. Let 0 < δ ≤ 1, let a > 0, and let X be a nonnegative random variable. Then Remark. The intuition behind our use of Lemma 5.6 is as follows. Theorem 5.3 implies that depth-2 QAC circuits require size at least Ω(n) to approximately construct | n (even using ancillae), and Proposition 5.5 implies that depth-2 QAC circuits that approximately construct | n have size at most 2n without loss of generality, so these bounds are "just a constant factor" away from implying that depth-2 QAC circuits of arbitrary size cannot approximately construct | n . This is analogous to how Markov's inequality is "just a factor of δ" away from the conclusion of Lemma 5.6.
Theorem 5.7 (Turán's theorem 10 ). Let G be a simple undirected graph on n vertices, and let d be the average degree of the vertices in G. Then G contains an independent set of size at least n/(d + 1).
Remark. For the intuition behind our use of Theorem 5.7, recall the discussion of disjoint light cones from Section 1.2.7.
Proof exposited by Alon and Spencer [1]. Identify the vertex set of G with [n]. Let σ be a uniform random permutation of [n], and let I be the set of vertices u such that σ(u) < σ(v) for all edges {u, v}. Then I is an independent set, because for every edge {u, v}, either σ(u) < σ(v) or σ(v) < σ(u). A vertex u with degree d u is in I with probability 1/(d u + 1), because any vertex out of u and its neighbors is equally likely to be assigned the lowest value by σ out of these vertices. By linearity of expectation it follows that E|I| = u∈[n] 1/(d u + 1), and by Jensen's inequality this is at least n/(d + 1).
Recall that |φ , C, |ψ , (Q j ) j are variables from the statement of Theorem 5.3. In upcoming applications of Theorem 5.3 we will refer to |φ as the "input state", C as the "circuit", |ψ as the "desired output state", and (Q j ) j as "projections".
Remark. We will not actually use the full strength of Theorem 5.3, in the sense that we will always upper-bound the number of multi-qubit gates acting on the targets by upperbounding the total number of gates.
Proof of Theorem 1.7(iii). Let L 2 , L 1 be layers of R ⊗ gates and let |φ be a mono-product state, with n qubits designated as targets and all other qubits designated as ancillae. Assume that for all k ∈ {1, 2}, every ancilla is acted on by a gate in L k , and every gate in L k acts on at least one target. By Proposition 5.5 it suffices to prove that the targets of L 2 L 1 |φ measure to | n with probability at most 1/2 + exp(−Ω(n)).
Let c be the constant from Theorem 5.3, and let γ = (c/2)(c/3)/(1 + c/2) and δ = (c/2)γ 2 . Since Theorem 5.3 remains true if c is replaced by any constant between 0 and c, we may take c to be small enough so that γ, δ ≤ 1.
For a circuit C let |C| denote the number of gates in C, and write "G ∈ C" to denote that G is a gate in C. First consider the case where |L 2 | ≤ γn. It suffices to prove that L 2 L 1 |φ and | n , ψ have fidelity at most 1/2 + exp(−Ω(n)) for all states |ψ . If |L 1 | ≤ n(c/3)/(1 + c/2) then |L 1 | + |L 2 | ≤ (c/3)n, and the result follows from applying Theorem 5.3 with input state |φ , circuit L 2 L 1 , desired output state | n , ψ , and n onequbit projections |0 0| acting on the targets. Alternatively, if |L 1 | ≥ n(c/3)/(1 + c/2) then |L 2 | ≤ (c/2)|L 1 |, and the result follows from applying Theorem 5.3 with input state L 1 |φ , circuit L 2 , desired output state | n , ψ , and for every gate G ∈ L 1 the projection |0 0| ⊗ I on the support of G, where |0 0| acts on one of the targets acted on by G. Now consider the case where |L 2 | ≥ γn. This time we will measure some carefully chosen ancillae before applying Theorem 5.3. Let X be the number of targets acted on by a uniform random gate in L 1 . By Lemma 5.6 there exists a real number t ∈ [1, exp(1/δ)] such that P (X ≥ t) ≤ δE[X]/t. Fix such a t. Write L 1 = L B 1 ⊗ L S 1 , for "big" and "small" respectively, where L B 1 (resp. L S 1 ) consists of the gates in L 1 acting on at least (resp. fewer than) t targets. Then, |L B 1 | = |L 1 |P (X ≥ t) ≤ δ|L 1 |E[X]/t ≤ δn/t = (c/2)γ 2 n/t. Let G be the undirected graph whose vertices are the gates in L 2 , and whose edges are the pairs e of distinct vertices such that for some gate G ∈ L S 1 , for both vertices V in e, there exists a target that both G and V act on. Since t ≥ 1, the degree of a vertex is at most t − 1 times the number of targets acted on by that vertex. Therefore the average degree of the vertices in G is at most (t − 1)n/|L 2 |, so by Theorem 5.7 there exists an independent set I in G of size Fix such a set I. It follows that |L B 1 | ≤ (c/2)|I| and also that |I| ≥ γ 2 n/ exp(1/δ) ≥ Ω(n).
For V ∈ I let H V be the Hilbert space consisting of the following two types of qubits: targets acted on by a gate in L S 1 that acts on one of the same targets as V , and qubits acted on by V that are not acted on by L S 1 . (For example, note that the first category includes every target acted on by L S 1 that is also acted on by V .) The H V are Hilbert spaces on pairwise disjoint sets of qubits, because I is an independent set in G and because a qubit cannot be acted on by multiple gates in L 2 .
For all gates G ∈ L 2 , write G = R H |θ H , where H ranges over all one-qubit Hilbert spaces acted on by G, and |θ H is a state in H. This defines |θ H for every ancilla H, because every ancilla is acted on by a gate in L 2 . For all ancillae H acted on by L S 1 , measure the H qubit of L 2 L 1 |φ in the |θ H basis. By Lemma 5.4, the resulting state |ϕ on the qubits that were not measured satisfies |ϕ = L 2 L B 1 |φ , where L 2 and L B 1 are implicitly tensored with the identity, and -|φ is the tensor product of (i) a mono-product state on the qubits that were not acted on by L S 1 , and (ii) the tensor product over G ∈ L S 1 of a state on the targets that were acted on by G. In particular, |φ factors as |φ = V ∈I |φ V ⊗ |φ A , for some states |φ V ∈ H V (none of the qubits in H V were measured) and a state |φ A on all other qubits in |ϕ .
where U G is a Hermitian unitary transformation (specifically, the identity or an R ⊗ gate) on the qubits in |ϕ that were acted on by G.
It suffices to prove that the targets of |ϕ measure to | n with probability at most 1/2+exp(−Ω(n)), or equivalently that | n , ψ|L 2 L B 1 |φ | 2 ≤ 1/2+exp(−Ω(n)) for all states |ψ . For V ∈ I, the transformation U V acts on a subset of the qubits in H V , including at least one target because V acted on at least one target and none of the targets were measured. Therefore we may define an orthogonal projection on H V by Q V = U V (|0 0| ⊗ I)U V ⊗ I, where |0 0| acts on a target. Observe that I − Q V = U V (|1 1| ⊗ I)U V ⊗ I, and that L 2 | n , ψ measures to V ∈I Q V ⊗ I and to V ∈I (I − Q V ) ⊗ I each with probability 1/2. Therefore the result follows from applying Theorem 5.3 with input state |φ , circuit L B 1 , desired output state L 2 | n , ψ , and projections (Q V ) V , recalling that |L B 1 | ≤ (c/2)|I| and that |I| ≥ Ω(n).
A Proof of Corollary 1.2 (d < 11) Let C be the depth-2 QAC circuit from Section 4.2, and let |ν be an n-nekomata such that C|0 . . . 0 and |ν have high fidelity. Let C = (X ⊗n ⊗ I)C and |ν = (X ⊗n ⊗ I)|ν , where X ⊗n acts on the targets of |ν . Note that |ν is an n-nekomata with the same targets as |ν , and that the fidelity of C |0 . . . 0 and |ν equals that of C|0 . . . 0 and |ν .
To approximate parity in depth 7, plug C into the circuit for parity from Fig. 5, and apply the simplification pictured in Fig. 8. The gate on the right denotes R |1000 (there is a natural generalization to arbitrary numbers of qubits), and the equivalence of the circuits in Fig. 8 may be verified by considering their actions when the unset qubits range over all standard basis states.

2(ii)
Let CL be a depth-(d + 1) mostly classical circuit, where C is purely classical and L is a layer of R ⊗ gates. Designate n qubits of CL as targets. Our proof of Theorem 4.2(ii) is similar to that of Theorem 4.2(i), except that here our procedure for simulating a standardbasis measurement of the targets of CL|0 . . . 0 is much more complicated. For brevity's sake we will omit many proof steps with clear analogues in the proof of Theorem 4.2(i), i.e. in Section 4.3.
Consider a gate G in L. Write G = R j |θ j for one-qubit states (|θ j ) j , and let p j = p (G) j = | 1|θ j | 2 . We may assume that p j = 0 for all j, because G|0 . . . 0 = (R j:p j =0 |θ j ⊗ I)|0 . . . 0 . Therefore, as an immediate corollary of Lemma 4.5, a standardbasis measurement of G|0 . . . 0 is distributed identically to (B ∧ X j ) j , where the X j are independent Bernoulli(p (G) j ) random variables conditioned on (X j ) j not being the all-zeros string, and B ∼ Bernoulli 4 j (1 − p j ) − 4 j (1 − p j ) 2 is independent of (X j ) j .
Let (R j ) j be independent random variables such that each R j is 1 with probability 1−p j and uniform random on [0, 1) with probability p j . Then (X j ) j is distributed identically to (1 R j <1 ) j conditioned on min R < 1. Let argmin R be a value of j such that R j = min R, and note that if we condition on min R < 1 then argmin R is unique with probability 1. To sample R conditioned on min R < 1, one may first sample J = argmin R conditioned on min R < 1, next sample µ = min R conditioned on R J = min R < 1, and finally, for all j = J, independently sample R j conditioned on R j > µ.
Rather than sampling (argmin R | min R < 1) (i.e. argmin R conditioned on min R < 1) directly, we may do so as follows. Identifying C with the function from boolean strings to boolean strings that it computes, say that an input bit j "influences" an output bit k if there exist strings x, y differing only in position j such that C|x and C|y differ in position k. Recall that no input bit influences more than 2 d output bits. Let τ (G) be the (non-random) tree constructed in the following two steps: -Start with a rooted binary tree with n 2 d leaves and depth log n 2 d , and identify each leaf with a distinct set of 2 d targets of CL.
-Then, for each qubit v acted on by G, for some set u of 2 d targets including all of the targets influenced by v, add the node v and edge (u, v) to the tree.
For each non-leaf node u in τ (G) such that (argmin R | min R < 1) is descended from u with nonzero probability, independently "highlight" a random edge from u to one of its children, where the probability of highlighting an edge (u, v) equals the probability that (argmin R | min R < 1) is descended from v divided by the probability that (argmin R | min R < 1) is descended from u. Then there is a unique root-to-leaf path consisting only of highlighted edges, and the leaf at the end of this path is distributed identically to (argmin R | min R < 1). Altogether this implies the following procedure for simulating a standard-basis measurement of G|0 . . . 0 . If G acts on a single qubit then simply output Y (G) ∼ Bernoulli(| 1|G|0 | 2 ). Otherwise, first sample the following random variables, all independently: -Highlight random edges in τ (G) , in the manner described above.
-For all j, sample M Then let J (G) be the leaf in the root-to-leaf path consisting of highlighted edges in τ (G) , and output be the set of highlighted edges between nodes at depths k and k + 1 in τ (G) , where we define the root to have depth 0, children of the root to have depth 1, and so on. Note that (E j }| ≤ c log s for all G, where c is an appropriately large universal constant. As in Section 4.3, by a Chernoff bound, the probability that S fails to be good is at most s −Ω (1) . For all G, P R j < 1 | R j > M is not identically false.
Let V = (Y, B, (E k ) k , M, S), and note that the targets of a standard-basis measurement of CL|0 . . . 0 are a read-O(2 d log s) family if V \Y is fixed, or if V \B is fixed and S is good, or if V \M is fixed and S is good, or if V \S is fixed. (We will consider the case where V \E k is fixed and S is good shortly.) Define W = W (V ) in the natural way such that W is distributed identically to the Hamming weight of a standard-basis measurement of the targets of CL|0 . . . 0 . Then, by an argument involving the triangle inequality 11 similar to that in Section 4.3, it suffices to prove the following (specifically, for an appropriate universal constant ε): 11 In slightly greater detail: sample an independent copy V of V , use a hybrid argument to show that |W (V ) − W (V )| is small with high probability, and then fix a value of V such that W (V ) is concentrated around W (V ).