Dependencies

Alice and Bob share \(\log n + 1\) EPR pairs. Alice applies \(\bigl(\begin{smallmatrix} A & 0 \\ 0 & C \end{smallmatrix}\bigr)\) to her halves and Bob applies \(\bigl(\begin{smallmatrix} B^\dagger & 0 \\ 0 & D^\dagger \end{smallmatrix}\bigr)\) to his, and they send all qubits to the referee. The referee does a CNOT on the first two qubits, applies a controlled-swap between the last two register sets controlled on the first register, and measures the first qubit in the Hadamard basis. The referee outputs \(1\) with probability \(\ge 0.95\) if \(\operatorname {Tr}(ABCD)\ge 0.9n\) and \(\le 0.55\) if \(\operatorname {Tr}(ABCD)\le 0.1n\), solving the ABCD problem with cost \(O(\log n)\). The referee’s actions have \(T\)-depth \(1\): the first CNOT is Clifford; before each controlled-swap the control qubit is copied onto \(\log n\) ancillas by CNOTs (Clifford) so all CSWAPs run in parallel; each CSWAP is implemented with one Toffoli (Definition 33); and a Toffoli is implementable in \(T\)-depth \(1\).

Define the controlled multiplexer \(\mathrm{cMultiplex}_n = \lvert 0\rangle \langle 0\rvert \otimes I + \lvert 1\rangle \langle 1\rvert \otimes \mathrm{Multiplex}_n\), acting on \(2 + \lceil \log _2 n\rceil + n\) qubits; a controlled multiplexer implements an ordinary one by fixing the control to \(\lvert 1\rangle \). The \(2^{k+1}\)-qubit controlled multiplexer is built from two \(2^{k}\)-qubit controlled multiplexers, with control \(C\), index register \(I_1,\dots ,I_{k+1}\), array \(X_1,\dots ,X_{2^{k+1}}\), target \(T\), and ancillas \(A_1,A_2\):

1. apply \(X\) to \(I_1\); apply a Toffoli controlled on \(C, I_1\) with target \(A_1\); apply \(X\) to \(I_1\);

2. apply a Toffoli controlled on \(C, I_1\) with target \(A_2\);

3. run the \(2^k\)-qubit controlled multiplexer with control \(A_1\), index \(I_2,\dots ,I_{k+1}\), first half \(X_1,\dots ,X_{2^k}\), target \(T\);

4. run the \(2^k\)-qubit controlled multiplexer with control \(A_2\), index \(I_2,\dots ,I_{k+1}\), second half \(X_{2^k+1},\dots ,X_{2^{k+1}}\), target \(T\);

5. uncompute \(A_1, A_2\).

The ancillas \(A_1, A_2\) record whether the active half is the left or right half (determined by the top index bit \(I_1\) and control \(C\)); at most one of the two half-multiplexers fires, cleanly implementing the \(2^{k+1}\)-qubit controlled multiplexer.

There is a \(\mathsf{Q}\| ^{*}\) protocol of cost \(O(\log n)\) for the Forrelation problem in which the referee’s actions can be implemented in \(T\)-depth \(2\).

Setting the target \(b = 0\), \(\mathrm{Multiplex}_n\) swaps \(x_i\) into the target register, so reading the target gives \(\mathrm{Index}_n(i,x) = x_i\). Hence the multiplexer computes the index function with zero magic overhead.

On \(2n+1\) qubits \(A_1,\dots ,A_n, B_1,\dots ,B_n, C\) with input \(\lvert x,y,0\rangle \):

1. for each \(i\), apply CNOT with control \(A_i\), target \(B_i\), giving \(\lvert x_i, x_i\oplus y_i\rangle \), then apply \(X\) to \(B_i\) giving \(\lvert x_i, x_i\oplus y_i\oplus 1\rangle \);

2. apply \(\mathrm{Toffoli}_n\) controlled on \(B_1,\dots ,B_n\) with target \(C\).

The target \(C\) flips iff all \(B_i = 1\), i.e. iff \(x_i = y_i\) for all \(i\); so the circuit computes \(\mathrm{Equal}_n(x,y)\) using one \(\mathrm{Toffoli}_n\) and otherwise only Clifford gates.

Alice gets \(A,C\in \mathrm{SU}(n)\) and Bob gets \(B,D\in \mathrm{SU}(n)\), and the goal is to output

An adaptive Clifford\(+\)Magic circuit is composed of Clifford gates, arbitrary magic gates, and mid-circuit computational-basis measurements, where later gate choices may depend arbitrarily on earlier measurement outcomes. Its cost is the total number of magic gates plus measurements in the worst-case run. The cost \(\mathcal{M}^{\mathrm{adaptive}}_{\epsilon ,c_M}(f)\) is the minimal such cost over adaptive circuits using magic gates and measurements each acting on at most \(c_M\) qubits (a single computational-basis measurement of \(c_M\) qubits counts once) that compute \(f\) with probability \(\ge 1-\epsilon \), with an arbitrary advice state.

The binary entropy function is

with the convention \(0\log 0 = 0\). (Recalled only so later magic-count lower bounds can refer to it.)

A unitary \(C\) on \(n\) qubits is a Clifford operator if it normalizes the Pauli group, i.e. \(C\, Q\, C^\dagger \) is a Pauli string (up to global phase) for every Pauli string \(Q\). The Clifford group is generated by the Hadamard gate \(H\), the phase gate \(P\) (Definition 3), and \(\mathrm{CNOT}\). A Clifford circuit is a circuit composed only of Clifford gates.

For a Hermicity-preserving superoperator \(\Phi \) (e.g. a difference of quantum channels), the diamond norm is

the maximum taken over density operators \(\rho \) on the input space tensored with an ancilla of the same dimension. For unitaries \(U,U'\) we write \(\lVert U-U' \rVert _{\diamond }\) for the diamond norm of the difference of the channels \(\rho \mapsto U\rho U^\dagger \) and \(\rho \mapsto U'\rho U'^\dagger \).

The equality function \(\mathrm{Equal}_n : \{ 0,1\} ^n\times \{ 0,1\} ^n\to \{ 0,1\} \) is \(\mathrm{Equal}_n(x,y) = 1\) iff \(x = y\).

For \(x\in \{ -1,1\} ^n\) with \(n\) a power of \(2\), write \(x = (x_1, x_2)\) (first and second halves) and define the forrelation

In the Forrelation communication problem Alice gets \(x\in \{ -1,1\} ^n\), Bob gets \(y\in \{ -1,1\} ^n\), and for a constant \(\alpha {\gt}0\) the goal is to output

where \(x\cdot y\) is the entrywise product.

In the garden-hose model, Alice and Bob share a fence with a number of pipes; Alice holds \(x\in \{ 0,1\} ^n\), Bob holds \(y\in \{ 0,1\} ^n\), Alice has a tap. Each player connects pipe-ends (and Alice connects the tap) by hoses, as a function of their input. Water from the tap flows along the resulting path and spills on one side; the side encodes the value of a Boolean function \(f(x,y)\) (spilling on Alice’s side \(=0\), Bob’s side \(=1\)). The garden-hose complexity \(\mathrm{GH}(f)\) is the minimal number of pipes in a garden-hose protocol computing \(f\). In the quantum picture, pipes are shared EPR pairs and hose connections are Bell-basis measurements, so the path describes concatenated teleportations (Definition 10).

The index function is \(\mathrm{Index}_n(i,x) = x_i\), where \(x\in \{ 0,1\} ^n\) and \(i\in \{ 0,1\} ^{\lceil \log _2 n\rceil }\).

A magic gate (equivalently, non-Clifford gate) is any unitary that is not a Clifford operator. The weight of a gate is the number of qubits on which it acts. The \(T\) gate is \(T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi /4} \end{pmatrix}\), a weight-\(1\) magic gate; the Clifford\(+T\) gate set is \(\{ H,P,\mathrm{CNOT},T\} \). A Clifford\(+\)Magic circuit is a circuit composed of Clifford gates and magic gates. The \(T\) gate satisfies \(T X T^\dagger = e^{-i\pi /4} P X\) and \(TZ = ZT\) (it commutes with Pauli \(Z\)).

Extend \(\mathcal{M}^{\mathrm{unitary}}_\epsilon \) and \(\mathcal{M}^{\mathrm{mixed}}_\epsilon \) to a target unitary \(U\) by requiring the circuit to implement \(U\) to within \(\epsilon \) in diamond norm, \(\lVert U-U' \rVert _{\diamond }\le \epsilon \), where \(U'\) is the implemented unitary. The cost is the minimal magic count of such an approximating circuit.

A mixed Clifford\(+\)Magic circuit is a quantum operation

where \(\{ p_i\} \) is a probability distribution and each \(U_i\) is a unitary Clifford\(+\)Magic circuit. Its magic-gate count is the worst-case count among the \(U_i\). It computes \(f\) with correctness \(\epsilon \) if (with an arbitrary advice state) measuring the first qubit yields \(f(x)\) with probability \(\ge 1-\epsilon \). The cost \(\mathcal{M}^{\mathrm{mixed}}_{\epsilon ,c_M}(f)\) is the minimal number of magic gates (of weight \(\le c_M\)) in any such operation computing \(f\).

The \(n\)-qubit quantum multiplexer acts, for \(x\in \{ 0,1\} ^n\), an \(\lceil \log _2 n\rceil \)-bit index \(i\), and \(b\in \{ 0,1\} \), by

i.e. controlled on \(i\) it swaps the \(i\)-th bit of \(x\) with the target \(b\).

In the non-local quantum computation setting there is no referee: Alice and Bob each send a single simultaneous quantum message to the other and then perform local operations. Concretely, to implement a target channel \(\mathcal{N}\) on a bipartite input, Alice and Bob apply local channels \(\mathcal{V}^L,\mathcal{V}^R\) to their inputs together with their halves of shared entanglement, exchange messages, and apply further local channels \(\mathcal{W}^L,\mathcal{W}^R\), so that the overall map equals \(\mathcal{N}\). The cost is the total communication and shared entanglement.

For subsets \(S_A, S_B \subseteq [n]\), the associated parity function on inputs \(x,y \in \{ 0,1\} ^n\) is

More generally a parity function of \((x,y)\) is any \(\mathbb {F}_2\)-affine function of the bits of \((x,y)\).

The single-qubit Pauli operators are

They satisfy \(X^2 = Z^2 = I\) and the anticommutation relation \(ZX = -XZ\). For \(\vec a = (a_1,\dots ,a_n), \vec b \in \{ 0,1\} ^n\) an (\(n\)-qubit) Pauli string is

possibly multiplied by a global phase in \(\{ \pm 1, \pm i\} \). The set of all such operators (with phases) forms the \(n\)-qubit Pauli group. We freely use \(X^{\vec x}\lvert 0\cdots 0\rangle = \lvert \vec x\rangle \) for \(\vec x\in \{ 0,1\} ^n\).

A non-adaptive parity decision tree (\(\mathsf{PDT}^{\mathrm{na}}\)) of depth \(k\) computing \(f:\{ 0,1\} ^n\to \{ 0,1\} \) is a function \(g:\{ 0,1\} ^k\to \{ 0,1\} \) together with parity functions \(p_1,\dots ,p_k\) such that \(f(x) = g(p_1(x),\dots ,p_k(x))\) for all \(x\). The \(\mathsf{PDT}^{\mathrm{na}}(f)\) complexity is the minimal such \(k\).

The phase gate is \(P = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}\). It satisfies the conjugation relation \(P X P^\dagger = i X Z\) (so conjugating a Pauli \(X\) by \(P\) produces a Pauli up to phase) and \(PZP^\dagger = Z\).

A private simultaneous message task is given by a Boolean function \(f:\{ 0,1\} ^n\times \{ 0,1\} ^n\to \{ 0,1\} \) and parameters \(\epsilon ,\delta \in [0,1]\). Alice (input \(x\)) sends a message system \(M_0\) and Bob (input \(y\)) sends \(M_1\) to the referee; from \(M = M_0 M_1\) the referee prepares an output bit \(z\) on a system \(Z\). Writing \(\rho _M(x,y)\) for the density operator on \(M\) produced on inputs \((x,y)\) and \(f_{x,y} = f(x,y)\), the task requires:

• \(\epsilon \)-correctness: there is a decoding map \(\mathbf{V}_{M\to Z\bar M}\) with, for all \((x,y)\) in the support of \(f\),

  \[ \lVert \operatorname {Tr}_{\bar M}\! \big(\mathbf{V}_{M\to Z\bar M}\, \rho _M(x,y)\, \mathbf{V}^\dagger _{M\to Z\bar M}\big) - \lvert f_{x,y}\rangle \langle f_{x,y}\rvert _Z \rVert _{1} \le \epsilon ; \]

• \(\delta \)-security: there is a simulator channel \(\mathcal{S}_{Z\to M}\) with, for all \((x,y)\) on which \(f\) is defined,

  \[ \lVert \rho _M(x,y) - \mathcal{S}_{Z\to M} (\lvert f_{x,y}\rangle \langle f_{x,y}\rvert _Z) \rVert _{1} \le \delta . \]

Classical messages give \(\mathsf{PSM}\); quantum messages give \(\mathsf{PSQM}\); shared entanglement adds the superscript \(*\) giving \(\mathsf{PSM}^{*}, \mathsf{PSQM}^{*}\). The cost is the total number of bits (resp. qubits) sent; \(\mathsf{PSM}_{\epsilon ,\delta }(f)\) etc. denote the minimal cost over \(\epsilon \)-correct, \(\delta \)-secure protocols (with \(\epsilon =1/3\) when omitted).

A randomized non-adaptive parity decision tree (\(\mathsf{RPDT}^{\mathrm{na}}\)) of depth \(k\) computing \(f\) with error \(\epsilon \) is a probability distribution over \(\mathsf{PDT}^{\mathrm{na}}\)’s each of depth \(\le k\) such that, for every input \(x\), the sampled tree outputs \(f(x)\) with probability \(\ge 1-\epsilon \). \(\mathsf{RPDT}^{\mathrm{na}}_\epsilon (f)\) is the minimal such \(k\).

Let \(f : \{ 0,1\} ^n \times \{ 0,1\} ^n \to \{ 0,1\} \) be a (partial or total) Boolean function and \(\epsilon \in [0,1]\). A simultaneous message passing protocol \(P\) for \(f\) has three parties: Alice (input \(x\)), Bob (input \(y\)), and a referee. Alice and Bob send the referee message systems \(M_A, M_B\) respectively, the referee outputs a bit \(c = P(x,y)\), and the parties do not otherwise communicate. The protocol is \(\epsilon \)-correct if \(\Pr [P(x,y)=f(x,y)] \ge 1-\epsilon \) for all \((x,y)\) in the support of \(f\). The cost \(\mathrm{cost}(P)\) is the total number of bits (classical) or qubits (quantum) sent by Alice and Bob; the complexity of \(f\) is the minimum cost over \(\epsilon \)-correct protocols. The variants are:

• messages classical = \(\mathsf{R}\| \), quantum = \(\mathsf{Q}\| \);

• \(\mathsf{D}\| \) = classical, deterministic, \(\epsilon = 0\);

• shared public randomness \(r\) available to all three parties: superscript \(\mathsf{pub}\), giving \(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon , \mathsf{Q}\| ^{\mathsf{pub}}_\epsilon \);

• Alice and Bob share entanglement: superscript \(*\), giving \(\mathsf{R}\| ^{*}, \mathsf{Q}\| ^{*}\).

When the subscript \(\epsilon \) is dropped, \(\epsilon = 1/3\). The complexities are \(\mathsf{D}\| (f), \mathsf{R}\| _\epsilon (f), \mathsf{Q}\| _\epsilon (f), \mathsf{R}\| ^{\mathsf{pub}}_\epsilon (f), \mathsf{Q}\| ^{\mathsf{pub}}_\epsilon (f), \mathsf{R}\| ^{*}(f), \mathsf{Q}\| ^{*}(f)\).

Write a Clifford\(+T\) circuit as a sequence of layers, where each layer is either a Clifford circuit or a layer of (parallel) \(T\) gates. The \(T\)-depth of the circuit is the number of \(T\)-layers in such a decomposition; the \(T\)-depth of a unitary \(U\) is the minimum \(T\)-depth over Clifford\(+T\) circuits implementing \(U\). The magic-depth is defined analogously with general magic-gate layers in place of \(T\)-layers.

An EPR pair is the two-qubit state \(\tfrac {1}{\sqrt2}(\lvert 00\rangle +\lvert 11\rangle )\). A Bell-basis measurement on two qubits projects onto the four maximally entangled states \((X^a Z^b \otimes I)\tfrac {1}{\sqrt2}(\lvert 00\rangle +\lvert 11\rangle )\), \(a,b\in \{ 0,1\} \), returning the outcome \((a,b)\). Teleportation: if Alice holds a state \(\lvert \phi \rangle \) and one half of an EPR pair whose other half is held by Bob, then a Bell-basis measurement by Alice on \(\lvert \phi \rangle \) and her EPR half, with outcome \((a,b)\), leaves Bob’s half in the state \(X^a Z^b \lvert \phi \rangle \). The outcome \((a,b)\) is uniformly random and independent of \(\lvert \phi \rangle \).

The \(n\)-qubit generalized Toffoli gate acts by

i.e. it XORs the AND of the first \(n\) bits into the target qubit.

A density operator \(\rho \) is a positive semidefinite operator with \(\operatorname {Tr}\rho = 1\). The trace norm of an operator \(A\) is \(\lVert A \rVert _{1} = \operatorname {Tr}\! \sqrt{A^\dagger A}\), and the trace distance between density operators \(\rho ,\sigma \) is \(\tfrac 12\lVert \rho -\sigma \rVert _{1}\).

Let \(f : \{ 0,1\} ^n \times \{ 0,1\} ^n \to \{ 0,1\} \) and \(\epsilon \in [0,1]\). A two-way classical communication protocol involves Alice (input \(x\)) and Bob (input \(y\)), who may share a random string \(r\). They exchange a sequence of messages (each computed from the local input, \(r\), and previously received messages), and Alice finally outputs a bit \(z\). The protocol is \(\epsilon \)-correct if \(\Pr [f(x,y)=z]\ge 1-\epsilon \) for all \((x,y)\) on which \(f\) is defined. The cost is the number of bits exchanged, maximized over inputs; the two-way complexity \(\mathsf{R}_\epsilon (f)\) is the minimum cost over \(\epsilon \)-correct protocols.

A unitary Clifford\(+\)Magic circuit is a circuit of Clifford gates and magic gates. We say it computes \(f:\{ 0,1\} ^n\to \{ 0,1\} \) with correctness \(\epsilon \) if there is an advice state \(\lvert \psi \rangle \) (independent of the input) such that running the circuit on \(\lvert x\rangle \lvert \psi \rangle \) and measuring the first qubit returns \(f(x)\) with probability \(\ge 1-\epsilon \) for all \(x\) in the support of \(f\). The cost \(\mathcal{M}^{\mathrm{unitary}}_{\epsilon ,c_M}(f)\) is the minimal number of magic gates, each of weight at most \(c_M\), in any such circuit. Access to an arbitrary (arbitrarily large) advice state is allowed.

The ABCD problem requires \(\mathsf{R}\)-cost \(\Omega (\sqrt{n})\).

\(\mathsf{D}\| (\mathrm{Equal}_n) = \Omega (n)\).

\(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Equal}_n) = \Omega (\min \{ \log (1/\epsilon ), n\} )\).

For \(\alpha = \Theta (1/\log n)\), the Forrelation problem requires \(\mathsf{R}\)-cost \(\tilde\Omega (n^{1/4})\).

Let \(f\) have garden-hose complexity \(\mathrm{GH}(f)\), and suppose Alice initially holds \(P^{f(x,y)}\lvert \psi \rangle \) with \(x\) known to Alice and \(y\) known to Bob. Then:

1. there is an instantaneous protocol (no communication) using \(2\mathrm{GH}(f)\) EPR pairs, after which Alice holds \(X^{g(\hat x)} Y^{h(\hat x)}\lvert \psi \rangle \), where \(\hat x\) consists of \(x\) together with the \(2\mathrm{GH}(f)\) bits describing Alice’s and Bob’s measurement outcomes;

2. the garden-hose complexities of \(g\) and \(h\) are at most linear in \(\mathrm{GH}(f)\):

   \[ \mathrm{GH}(g) \le 4\mathrm{GH}(f) + 1, \qquad \mathrm{GH}(h) \le 11\mathrm{GH}(f) + 2. \]

Let \(f_1,\dots ,f_m\) be Boolean functions and \(c\in \{ 0,1\} \). Then for \(f = f_1\oplus \dots \oplus f_m\oplus c\) we have \(\mathrm{GH}(f) \le 4\sum _{i=1}^m \mathrm{GH}(f_i) + 1\).

\(\mathsf{R}\| ^{\mathsf{pub}}_\epsilon (\mathrm{Index}_n) \ge (1-h(\epsilon ))\, n\).

For every Boolean function \(f\), \(\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)\). Moreover the adaptive model can simulate the mixed model (by preparing \(\lvert +\rangle \) states and measuring), though the costs may be incomparable because \(\mathcal{M}^{\mathrm{adaptive}}\) also counts measurements.

We have

and the upper bound \(\mathcal{M}^{\mathrm{unitary}}_{\epsilon =0}(\mathrm{Multiplex}_n) = O(n)\).

For any parity function \(p(x,y) = \sum _{i\in S_A} x_i + \sum _{i\in S_B} y_i \pmod2\), the referee can compute \(p(x,y)\) in the \(\mathsf{D}\| \) model with communication cost \(2\).

Let \(C\) be a Clifford circuit on \(n\) qubits and let \(X^{\vec a}Z^{\vec b}\) be a Pauli string whose exponents \(\vec a,\vec b\) are \(\mathbb {F}_2\)-affine functions (parity functions) of an input \((x,y)\). Then \(C\, (X^{\vec a}Z^{\vec b})\, C^\dagger \) is a Pauli string (up to phase) each of whose \(X\)- and \(Z\)-exponents is again a parity function of \((x,y)\), with the parities determined by \(C\) and not by the input.

We have \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (\mathrm{Toffoli}_n) = \Omega (\min \{ \log (1/\epsilon ), n\} )\) and, for all \(\epsilon {\lt}\tfrac 12\), \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (\mathrm{Toffoli}_n) = \Omega (n)\).

If a circuit using a unitary \(U\) computes \(f\) with probability \(1\) and no extra magic gates, then \(\mathcal{M}^{\mathrm{unitary}}_\epsilon (U) \ge \mathcal{M}^{\mathrm{unitary}}_\epsilon (f)\) and \(\mathcal{M}^{\mathrm{mixed}}_\epsilon (U) \ge \mathcal{M}^{\mathrm{mixed}}_\epsilon (f)\).

\(\ \mathsf{PDT}^{\mathrm{na}}(f) - 1 \le \mathcal{T}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f)\), where \(\mathcal{T}^{\mathrm{unitary}}\) counts \(T\) gates.

For all \(c_M\), \(\ \dfrac {1}{2c_M}\big(\mathsf{PDT}^{\mathrm{na}}(f) - 1\big) \le \mathcal{M}^{\mathrm{unitary}}_{\epsilon {\lt}1/2}(f)\).

\(\mathsf{D}\| (f)\) also lower bounds the number of magic gates plus the number of post-selected qubits in any Clifford\(+\)Magic\(+\)post-selection circuit computing \(f\): precisely, the simulation of Theorem 21 extends so that each qubit of post-selection adds \(2\) bits of \(\mathsf{D}\| \) communication.

The simulation of \(\mathsf{Q}\| ^{*}\) by \(\mathsf{R}\| ^{*}\) in Theorem 49 also applies to relational problems, dropping the privacy condition: the only change is that Alice sends the referee the measurement outcomes of a subset of qubits rather than a single qubit.

For all \(c_M\), \(\ \dfrac {1}{2c_M}\big(\mathsf{RPDT}^{\mathrm{na}}_\epsilon (f) - 1\big) \le \mathcal{M}^{\mathrm{mixed}}_\epsilon (f)\).

\(\ \mathsf{RPDT}^{\mathrm{na}}_\epsilon (f) - 1 \le \mathcal{T}^{\mathrm{mixed}}_\epsilon (f)\).

Let \(\Lambda _f\) denote the measurement applied by the referee in a \(\mathsf{Q}\| ^{*}\) protocol for \(f\). Then Theorem 49 yields the \(T\)-depth lower bound

Let \(f\) be a Boolean function. For all \(\epsilon {\lt} \tfrac 12\) and all \(c_M\),

where the magic gates have weight at most \(c_M\).

Consider an \(\epsilon \)-correct \(\mathsf{Q}\| ^{*}\) protocol for \(f\) using \(m\) qubits of message, in which the referee applies a \(T\)-depth-\(d\) unitary to the received messages together with at most \(a\) qubits of ancilla and then measures the first qubit. Then there is a \(\mathsf{PSM}^{*}_{\epsilon ,\delta =2\epsilon }\) protocol for \(f\) using \(O((68(m+a))^d)\) qubits of communication and entanglement.

Let \(f\) be a Boolean function. For all \(\epsilon \) and \(c_M\),

Let \(f\) be a Boolean function. For all \(\epsilon \) and \(c_M\),

There exist \(n\)-bit partial Boolean functions whose \(\mathsf{R}\| ^{*}\) complexity is \(\mathrm{polylog}(n)\) while their \(\mathsf{R}\) (two-way randomized) complexity is \(n^{\Omega (1)}\); in particular \(\mathsf{R}\| ^{*}\) and \(\mathsf{R}\) are exponentially separated.

Let \(U_{AB}\) be a Clifford\(+T\) unitary of \(T\)-depth at most \(d\) acting on \(n\) qubits. Then \(U_{AB}\) can be implemented as an NLQC using at most \(O((68n)^d)\) bits of communication and at most \(O((68n)^d)\) shared EPR pairs.