4 Communication upper bounds from magic depth
4.1 The private simultaneous message passing model and NLQC
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.
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).
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:
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;
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\).
4.2 Transforming \(\mathsf{Q}\| ^{*}\) protocols into \(\mathsf{PSM}^{*}\) protocols
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.
Suppose Alice and Bob have executed their \(\mathsf{Q}\| ^{*}\) actions and hold message systems \(M_A, M_B\). Bob teleports \(M_B\) to Alice (Definition 10) without revealing the Pauli corrections. Alice attempts to execute the referee’s unitary \(U_{M_A M_B E}\) (\(E\) the referee’s advice) on her copy, but only knows Bob’s state up to Pauli corrections; she tracks these through the Clifford\(+T\) decomposition of \(U\).
Clifford layers. The teleportation produces Pauli corrections on the inputs; conjugating through a Clifford layer yields new Pauli corrections that are known to Bob (he knows the circuit).
\(T\) layers. From the relations \(TX = PXT\) and \(TZ = ZT\) (Definition 5), Pauli \(X\) corrections commute through a \(T\) gate at the cost of a conditional phase-gate \(P\) correction. These conditional \(P\) corrections are removed using garden-hose gadgets via Lemma 47: the function deciding whether a \(P\) correction is needed is initially fully known to Bob, hence has garden-hose complexity \(1\); by Lemma 47 the resulting corrections after the first Clifford\(+T\) layer remain of constant garden-hose complexity. For the next layer, the corrections conjugate through the Clifford to corrections whose presence is an XOR of a subset of previous corrections; by Lemma 48 these have garden-hose complexity \(O(m+a)\), and so on, the gadgets growing in cost layer by layer.
Accounting. The total entanglement cost of the gadgets matches the cost of implementing \(U\) as an NLQC, namely \(O((68(m+a))^d)\) by Theorem 45 with \(n = m+a\). After the final Clifford\(+T\) layer Alice applies a last Clifford layer and measures a single qubit, with outcome bit \(s\). Alice sends \(s\) together with all her Bell-basis measurement outcomes to the referee; Bob sends all his Bell-basis measurement outcomes. From the Bell-basis outcomes the referee determines whether there was a Pauli \(X\) correction on the measured qubit and hence learns the corrected outcome, recovering \(f(x,y)\) with error \(\epsilon \). All messages are classical, so this is a \(\mathsf{R}\| ^{*}\) (indeed \(\mathsf{PSM}^{*}\)) protocol of cost \(O((68(m+a))^d)\).
Security (\(\delta = 2\epsilon \)). Let \(\vec r = (r_1,\dots ,r_k)\) be the Bell-basis outcomes (uniformly random in \(\{ 0,1\} ^{|r|}\)) and \(s\) Alice’s single output bit. The message has the form
where \(p(r)\) is a parity deciding the \(X\) correction on the measured qubit and \(\alpha (x,y)\ge 1-\epsilon \). Define the simulator
Then
using unitary invariance of the trace norm and \(\lVert (\alpha -1)\lvert f\rangle \langle f\rvert + (1-\alpha )\lvert f\oplus 1\rangle \langle f\oplus 1\rvert \rVert _{1} = 2|1-\alpha |\). Hence the protocol is \(\delta = 2\epsilon \) secure.
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.
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
4.3 Separating \(\mathsf{R}\| ^{*}\) and \(\mathsf{R}\)
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.
Alice gets \(A,C\in \mathrm{SU}(n)\) and Bob gets \(B,D\in \mathrm{SU}(n)\), and the goal is to output
For \(\alpha = \Theta (1/\log n)\), the Forrelation problem requires \(\mathsf{R}\)-cost \(\tilde\Omega (n^{1/4})\).
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\).
The ABCD problem requires \(\mathsf{R}\)-cost \(\Omega (\sqrt{n})\).
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\).
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.
Take either the ABCD problem or the Forrelation problem (Definitions 53, 52). Each has a \(\mathsf{Q}\| ^{*}\) protocol of cost \(O(\log n)\) whose referee acts in constant \(T\)-depth (Constructions 57 and 55, with \(T\)-depth \(1\) and \(2\) respectively). Applying Theorem 49 with \(m, a = O(\log n)\) and \(d = O(1)\) converts each into an \(\mathsf{R}\| ^{*}\) (in fact \(\mathsf{PSM}^{*}\)) protocol of cost \((O(\log n))^{O(1)} = \mathrm{polylog}(n)\). On the other hand the \(\mathsf{R}\) complexity is \(\Omega (\sqrt n)\) for ABCD (Lemma 56) and \(\tilde\Omega (n^{1/4})\) for Forrelation (Lemma 54), both \(n^{\Omega (1)}\). Hence \(\mathsf{R}\| ^{*}= \mathrm{polylog}(n)\) while \(\mathsf{R}= n^{\Omega (1)}\), an exponential separation.