Why does gate teleportation allow to implement nonlocal operations via local ones?

Question

In (Gottesman and Chuang 1999), when discussing quantum gate teleportation, they mention how it can be used to implement nonlocal gates such as a CNOT, by only using (classically controlled) local operations. Their scheme is shown in Figure 2 in the paper, which I report below:

Now, specifics of this particular circuit aside, I'm trying to get a better hold at the mechanism allowing nonlocal operations to be implemented via local operations and classical communication.

In general terms, I understand gate teleportation as performing state teleportation via the entangled state $(I\otimes U)|\Psi\rangle$ with $|\Psi\rangle\equiv\sum_i|i,i\rangle$ "standard" (symmetric) maximally entangled state. This results in a state $|\psi\rangle$ evolving to $(UU_a^\dagger U^\dagger)U|\psi\rangle$, conditionally to the ancilla being projected onto $|\Psi_a\rangle\equiv(U_a\otimes I)|\Psi\rangle$.

In a setting like the one in the figure above, the initial resource state $|\Psi\rangle$ oughts to become a four-qubit maximally entangled state $|\chi\rangle$. Somehow, performing Bell measurements on both ancillae (separately), and performing local operations on the state conditioned to these, results in a nonlocal operation being implemented. Now, I could obviously just follow the steps in the circuit above and verify that it indeed results in the CNOT being implemented, but my question concerns whether there is a more general/abstract way to understand this procedure. In particular, how is it that performing only local operations on the ancillae results in a nonlocal one on the target qubits?

Answer 1

In the ZX calculus, replacing gates with gate teleportation is as easy as bending the edges.

is a CNOT. You can rearrange things into this without changing the graph:

but the second graph, read left to right, is introducing two bell pairs then applying a CNOT between them then getting the inputs then performing bell basis measurements. Which is gate teleportation. (The Pauli corrections are implied.)

Answer 2

Another possible way to understand this starts from the observation that state teleportation of $|\psi\rangle$ through $|\Psi\rangle$ is a direct consequence of the fact that we can write $$|\psi\rangle\otimes|\Psi\rangle = \sum_a |\Psi_a\rangle\otimes U_a^\dagger|\psi\rangle,$$ where $|\Psi_a\rangle\equiv(U_a\otimes I)|\Psi\rangle$, and $\{U_a\}$ is some (any) set of orthogonal unitary operators. For more details on this see the second approach in this other answer.

Now, for gate teleportation, focusing on the case where we want to teleport a two-qubit gate, the resource state $|\Psi\rangle$ is an entangled state over four qubits, while $|\psi\rangle$ is a bipartite state. Playing the same game as above, if the gate we want to teleport is some two-qubit unitary $U$, then we write $$|\psi\rangle\otimes|\Psi\rangle = \sum_{ab} (U_{ab}\otimes I)|\Psi\rangle\otimes (UU_{ab}^\dagger|\psi\rangle).$$ Here, again, $\{U_{ab}\}_{ab}$ is a set of orthogonal unitary matrices. Interestingly, however, we can use local unitaries for these, because if $\{U_a\}$ is a set of orthogonal (single-qubit) unitaries, then $U_{ab}=U_a\otimes U_b$ is a set of orthogonal two-qubit unitaries.

To now more directly address the original point of the question: this will only work if $(U_{ab}\otimes I)|\Psi\rangle$ is a set of orthogonal maximally entangled states. And for this to be the case, $|\Psi\rangle$ also needs to be suitably chosen. If for example we were to use $|\Psi\rangle=|\Phi^+\rangle^{\otimes 2}$, with $|\Phi^+\rangle$ a two-qubit Bell state, then $$(U_{ab}\otimes I)|\Psi\rangle = U_{ab}|\Phi^+\rangle\otimes |\Phi^+\rangle,$$ which will only contain a maximum of four orthogonal states. This is not sufficient for our purposes, because it means that the set of states $|\Psi_{ab}\rangle$ does not correspond to a projective measurement we can perform to obtain some values of $a,b$. We instead need some $|\Psi\rangle$ which is not separable with respect to the bipartite between first and last two qubits. For example, we could use $$|\Psi\rangle = \frac12\sum_{ij} |ij\rangle\otimes|ij\rangle = \operatorname{SWAP}_{23}|\Phi^+\rangle^{\otimes 2}.$$ This happens to also be the choice used in the $|\chi\rangle$ used in the paper.

In conclusion, while all performed operations are local, it is possible to perform nonlocal operations via this scheme because there is some nonlocality that has been previously created/is assumed to exist in the resource shared state $|\Psi\rangle$.