A unitary Clifford\(+\)Magic circuit is the special case of a mixed circuit with a single term (\(p_1 = 1\)), and a special case of an adaptive circuit using no measurements; in both cases the magic-gate count is unchanged. Hence any unitary circuit witnessing \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (f)\) is admissible in the mixed and adaptive models, giving \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (f)\ge \mathcal{M}^{\mathrm{mixed}}_\epsilon (f)\) and \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (f)\ge \mathcal{M}^{\mathrm{adaptive}}_\epsilon (f)\). For the simulation claim, an adaptive circuit can prepare \(\lvert +\rangle \) states and measure in the computational basis to generate randomness and then condition subsequent gates on the outcomes, reproducing the random choice \(i\) with distribution \(\{ p_i\} \) of a mixed circuit; but \(\mathcal{M}^{\mathrm{adaptive}}\) additionally charges for these measurements, so the two costs need not be comparable.

Alice sends the single bit \(\sum _{i\in S_A} x_i \bmod 2\) and Bob sends the single bit \(\sum _{i\in S_B} y_i \bmod 2\). The referee XORs the two received bits to obtain \(p(x,y)\). Two bits are communicated.

Conjugation by a Clifford \(C\) maps each Pauli generator \(X_i, Z_i\) to a Pauli string (Definition 4); on exponent vectors over \(\mathbb {F}_2^{2n}\) this action is \(\mathbb {F}_2\)-linear (the symplectic representation of the Clifford group), depending only on \(C\) and ignoring global phases. Hence \(C(X^{\vec a}Z^{\vec b})C^\dagger \) has exponent vector \(L_C(\vec a, \vec b)\) for a fixed linear map \(L_C\) determined by \(C\). If \((\vec a,\vec b)\) are affine functions of \((x,y)\), then so is \(L_C(\vec a,\vec b)\), i.e. every output exponent is a parity function of \((x,y)\) with coefficients fixed by \(C\).

Take a unitary Clifford\(+\)Magic circuit computing \(f\) with probability \(p = 1-\epsilon {\gt} 1/2\), with \(k\) magic gates each of weight \(\le c_M\). Decompose it into layers \(C^0, M_1, C^1, M_2, \dots , M_k, C^k\) where each \(C^j\) is a Clifford circuit and each \(M_j\) is a magic gate. Run on input \(\lvert z\rangle \lvert \psi \rangle \) with \(z\) split into \((x,y)\); view the input as \(X_A^{\vec x}\lvert x\rangle _A X_B^{\vec y}\lvert y\rangle _B\lvert \psi \rangle _E\) obtained from the all-zeros state.

Give a \(\mathsf{D}\| \) protocol. The referee runs the circuit on \(\lvert 0\rangle \lvert 0\rangle \lvert \psi \rangle \). After the first Clifford layer \(C^0\), the conjugated input Paulis become a Pauli correction \(\sigma _{ABE}[x,y]\) on the state, and by Lemma 20 each of its \(X\)- and \(Z\)-exponents is a parity function of \((x,y)\). Before applying \(M_1\) we must undo the Pauli corrections on the (at most \(c_M\)) wires that \(M_1\) acts on; each such wire carries a correction \(X^a Z^b\) with \(a,b\) parity functions of \((x,y)\), i.e. at most \(2c_M\) parity functions. By Lemma 19 each parity costs \(2\) bits of \(\mathsf{D}\| \) communication. Apply \(M_1\), then the next Clifford layer; the remaining corrections conjugate through to new parity-valued corrections (Lemma 20), and we repeat before each \(M_j\). Finally one more parity determines whether there is an \(X\) correction on the output qubit before the measurement (a \(Z\) correction does not affect the computational-basis measurement and may be left uncorrected). Correcting and measuring yields a sample from the circuit’s output distribution.

Repeating with the same parity values, the referee estimates the output distribution; since the circuit is correct with probability \(1-\epsilon {\gt} 1/2\), outputting the majority bit is correct. The total cost is at most \(4c_M\) per magic gate (at most \(2c_M\) parities, \(2\) bits each) plus \(2\) for the final parity, so \(\mathsf{D}\| (f) \le 4c_M\cdot \mathcal{M}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f) + 2\). Rearranging gives the claim.

Run the simulation of Theorem 21. Just before a post-selection onto a fixed state, send the (at most \(2\) per qubit) parity-valued Pauli corrections acting on the post-selected qubit, exactly as is done before a magic gate; by Lemma 19 this costs \(2\) bits per qubit of post-selection. The referee corrects and then post-selects. Thus \(\mathsf{D}\| (f)\) also lower bounds the magic-gate count plus the number of post-selected qubits.

Take a mixed Clifford\(+\)Magic circuit \(\mathcal{N}(\cdot )=\sum _i p_i U_i(\cdot ) U_i^\dagger \) computing \(f\) with probability \(\ge 1-\epsilon \); let \(P_i(z)\) be the probability that \(U_i\) outputs \(f(z)\) on input \(z\), so the success probability is \(p_{\mathrm{suc}}(z) = \sum _i p_i P_i(z) \ge 1-\epsilon \). The referee, Alice and Bob use public randomness to sample \(i\) with probability \(p_i\). They then run the \(\mathsf{D}\| \) protocol of Theorem 21 for the unitary \(U_i\), but the referee samples the final measurement once and outputs the result rather than taking a majority. The protocol is then correct with probability \(P_i\), and overall with probability \(\sum _i p_i P_i \ge 1-\epsilon \). The communication for the selected \(U_i\) is at most \(4c_M\) times the number of magic gates in \(U_i\) plus \(2\) (Theorem 21, Lemma 19); the worst case over \(i\) is \(4c_M \mathcal{M}^{\mathrm{mixed}}_{\epsilon ,c_M}(f) + 2\). Hence \(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (f) \le 4c_M\mathcal{M}^{\mathrm{mixed}}_{\epsilon }(f)+2\), which rearranges to the claim.

Build a two-way protocol from an adaptive circuit. Decompose the circuit into layers, each an arbitrary Clifford circuit followed by at most one magic gate or one (computational-basis) measurement, occurring first in the layer. Alice prepares the advice state \(\lvert \psi \rangle _E\) and runs on \(\lvert x\rangle _A X_B^{\vec y}\lvert y\rangle _B\lvert \psi \rangle _E\); she applies the first Clifford layer, producing a Pauli correction \(\sigma _{ABE}[y]\) whose exponents are parities of the input (Lemma 20).

If the first non-Clifford operation is a magic gate (weight \(\le c_M\)), Bob computes the identities of the Pauli corrections on the \(\le c_M\) wires it acts on and sends them to Alice: for each wire there may be an \(X\) and a \(Z\) correction, so \(2c_M\) bits. Alice corrects and applies the gate. If instead it is a measurement (of \(\le c_M\) qubits), Bob sends the \(X\) corrections on the measured wires, Alice corrects, measures, and sends the \(\le c_M\) outcome bits back to Bob; total \(2c_M\) bits. In either case both players learn the measurement outcomes and choose the next layer accordingly. Repeating for every layer costs \(2c_M\) per magic gate or measurement. A final Pauli-\(X\) correction before the output measurement contributes \(+1\). The outcome equals \(f(x,y)\) with probability \(1-\epsilon \), so \(\mathsf{R}_\epsilon (f) \le 2c_M \mathcal{M}^{\mathrm{adaptive}}_{\epsilon ,c_M}(f)+1\), giving the claim.

In the proof of Theorem 21 the communication from Alice and Bob consists entirely of values of parity functions of \((x,y)\) (Lemma 20), and these parity functions depend only on the circuit, not on the input. Hence the referee computes the output as a fixed function of at most \(2c_M\) parities per magic gate plus one final parity, i.e. a non-adaptive parity decision tree of depth \(2c_M \mathcal{M}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f) + 1\). Therefore \(\mathsf{PDT}^{\mathrm{na}}(f) \le 2c_M\mathcal{M}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f) + 1\), which rearranges to the claim.

Specialize Proposition 27 to \(T\) gates, where \(c_M = 1\). Since \(T\) commutes with Pauli \(Z\) (Definition 5), the \(Z\) corrections need not be undone before a \(T\) gate, halving the number of required parities to one per \(T\) gate. Hence \(\mathsf{PDT}^{\mathrm{na}}(f) \le \mathcal{T}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f) + 1\).

For each \(U_i\) in the mixed circuit, the \(\mathsf{D}\| \) protocol of Theorem 21 defines a (deterministic) non-adaptive parity decision tree as in Proposition 27, except that the leaf now samples the output from the final measurement distribution rather than taking a majority; this is a \(\mathsf{RPDT}^{\mathrm{na}}\) that outputs \(f(x)\) with the same probability as running \(U_i\). Adding the public random choice of \(i\) (with probability \(p_i\)) gives a single \(\mathsf{RPDT}^{\mathrm{na}}\) outputting \(f(x)\) with the same probability as \(\sum _i p_i U_i(\cdot )U_i^\dagger \). The number of parities needed for the worst-case \(U_i\) is \(2c_M\mathcal{M}^{\mathrm{mixed}}_\epsilon (f) + 1\), so \(\mathsf{RPDT}^{\mathrm{na}}_\epsilon (f) \le 2c_M\mathcal{M}^{\mathrm{mixed}}_\epsilon (f) + 1\).

Specialize Proposition 29 to \(T\) gates (\(c_M=1\)) and use, as in Proposition 28, that \(T\) commutes with \(Z\) so only one parity per \(T\) gate is needed. This gives \(\mathsf{RPDT}^{\mathrm{na}}_\epsilon (f) \le \mathcal{T}^{\mathrm{mixed}}_\epsilon (f) + 1\).

Suppose \(U'\) approximates \(U\) with \(\lVert U-U' \rVert _{\diamond }\le \epsilon \). Replacing \(U\) by \(U'\) in the circuit that computes \(f\) exactly yields a circuit computing \(f\) with probability \(\ge 1-\epsilon \) (the diamond-norm bound limits the change in any measurement outcome by \(\epsilon \)). Since the surrounding gates add no magic, any circuit implementing \(U\) to error \(\epsilon \) gives a circuit computing \(f\) to error \(\epsilon \) with the same magic count, so the magic count of \(U\) is at least that of \(f\) in both the unitary and mixed models.

By Construction 35, \(\mathrm{Toffoli}_n\) computes \(\mathrm{Equal}_n\) with no magic overhead, so by Lemma 32 \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Toffoli}_n) \ge \mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Equal}_n)\) and \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (\mathrm{Toffoli}_n)\ge \mathcal{M}^{\mathrm{unitary}}_\epsilon (\mathrm{Equal}_n)\). By Theorem 23, \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Equal}_n) \ge \tfrac {1}{4c_M}(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Equal}_n)-1)\), and \(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Equal}_n) = \Omega (\min \{ \log (1/\epsilon ),n\} )\) (Lemma 37) with \(c_M = O(1)\), giving the mixed bound. By Theorem 21, \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (\mathrm{Equal}_n) \ge \tfrac {1}{4c_M}(\mathsf{D}\| (\mathrm{Equal}_n)-2)\), and \(\mathsf{D}\| (\mathrm{Equal}_n) = \Omega (n)\) (Lemma 36), giving the unitary bound \(\Omega (n)\).

Lower bound. By Construction 41, \(\mathrm{Multiplex}_n\) computes \(\mathrm{Index}_n\) with no magic overhead, so by Lemma 32, \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Multiplex}_n) \ge \mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Index}_n)\). By Theorem 23, \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Index}_n) \ge \tfrac {1}{4c_M}(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Index}_n) - 1)\), and by Lemma 42 \(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Index}_n) \ge (1-h(\epsilon ))n\), giving the stated bound.

Upper bound. Use Construction 43. Let \(g(k)\) be the magic count (Toffoli gates of weight \(3\)) of the \(2^k\)-qubit controlled multiplexer. The recursion uses two copies of the \(2^k\)-qubit controlled multiplexer plus a constant number of Toffolis (steps 1, 2 and the uncomputation in step 5), so \(g(k+1) \le 2g(k) + 4\), with base case \(g(1) = O(1)\). Unrolling, \(g(k) \le 2^k g_0 + 4(2^k - 1) = O(2^k)\). Since the \(n\)-array multiplexer corresponds to \(k = \log _2 n\), the magic count is \(O(2^{\log _2 n}) = O(n)\), and an ordinary multiplexer is a controlled one with control fixed to \(\lvert 1\rangle \). Hence \(\mathcal{M}^{\mathrm{unitary}}_{\epsilon =0}(\mathrm{Multiplex}_n) = O(n)\).