How does one create a long range CNOT gate on a square grid of qubits using constant depth circuits?

Question

In this talk, the speaker shows a bunch of data qubits on the top and ancilla qubits at the bottom that need to be linked by CNOT gates. The grid here is $n\times n$.

The procedure is to swap the data qubits as you go down the rows until they hit the ancilla qubits. The claim is that one needs 3 CNOT gates along the paths shown and this can be done "in 3 steps" and that the circuit is constant depth.

How is this done? The naive way is to do swap operations along the path, do the CNOT, and then swap back but this is a circuit of depth $2n$.

Answer 1

Delfosse is presenting the paper: "Bounds on stabilizer measurement circuits and obstructions to local implementations of quantum LDPC codes"

The claim is that one needs 3 CNOT gates along the paths shown and this can be done "in 3 steps" and that the circuit is constant depth.

What is meant here is that one needs 3 CNOT gates between data qubit 1 and ancilla qubit 3, data qubit 4 and ancilla qubit 1, data qubit 6 and ancilla qubit 2. (I'm labelling the qubits according to the tanner graph on the left of your screenshot).

With 3 steps, Delfosse means sequentially applying the three constant depth circuits that each implement one CNOT. The constant depth circuit he is referring to is given in Figure 10:

This circuit uses a bell state to implement the CNOT. Creating the bell state can be done in constant depth, as shown in part a) of Figure 10. Let's understand how to do a CNOT gate using a bell pair (here C refers to control and T refers to target):

To verify that this circuit implements a CNOT(C->T) gate we need to show $$X_C \rightarrow X_C X_T, \quad Z_C \rightarrow Z_C, \quad X_T \rightarrow X_T, \quad Z_T \rightarrow Z_C Z_T$$

I'll show $X_C \rightarrow X_C X_T$ as an example. $$t_0: \langle X_1, X_2 X_3, Z_2 Z_3 \rangle \\ t_1: \langle Z_1 Z_2 Z_3, X_1 X_2, X_2 X_3 X_4 \rangle \\ t_2: \langle (-1)^a Z_1 Z_3, X_1 X_3 X_4 \rangle \\ t_3: \langle (-1)^b X_1 X_4 \rangle \\ t_4: \langle X_1X_4 \rangle$$

One can similarly check that the other 3 pauli's propagate as desired.

---

Side note: Delfosse explains that the circuits implementing the three CNOTs don't need to implemented sequentially, i.e. in "three steps". They can be implemented in parallel! See Algorithm 2 in the paper for how to do this.