# What are the entries in the 2x2 $W$ gate used for walking along the welded-trees graph of Childs et al.?

As an extension of a famous description of non-local Hamiltonian simulation in section 4.7.3 of Nielsen and Chuang, the welded-trees paper of Childs, et al. provides the following circuit for use in the quantum walk along their graph:

Here, $$a$$ and $$b$$ are two different $$2n$$-bit labels for the nodes of the graph, while $$W$$ appears somehow related to a SWAP gate used in the traversal of the graph.

In particular, the eigenvalues of SWAP are $$\pm 1$$ because SWAP$$\ne$$SWAP$$^2=\mathbb 1$$, while the unique eigenvector of the SWAP gate having eigenvalue $$-1$$ is $$\frac{1}{\sqrt 2}(|01\rangle-|10\rangle)$$.

Childs et al. define $$W$$ as:

$$\begin{eqnarray} W|00\rangle=|00\rangle\\ W\frac{1}{\sqrt 2}(|01\rangle+|10\rangle)=|01\rangle\\ W\frac{1}{\sqrt 2}(|01\rangle-|10\rangle)=|10\rangle\\ W|11\rangle=|11\rangle \end{eqnarray}$$

But what, then, are the entries of this gate $$W$$?

Are they something like: $$\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & e^{i\pi q/2}\cos\frac{\pi q}{2} & -ie^{i\pi q/2}\sin\frac{\pi q}{2} & \: 0 \ \\ 0 & -ie^{i\pi q/2}\sin\frac{\pi q}{2} & e^{i\pi q/2}\cos \frac{\pi q}{2} & 0 \\ 0 & 0 & 0 & 1 \end{array}\right)$$

for some $$q$$?

I'm really just trying to understand that paper in general, and this circuit in particular, in more detail. Childs et al. trotterizes this circuit over all the different edge-colorings of the graph to do the Hamiltonian simulation thereof; after about a linear amount of time there's a decent odds that the particle, which was initially at node $$|\psi\rangle=$$ ENTRY, has found the EXIT.

• You can get $W|01\rangle$ by summing the second and third equation and dividing by $\sqrt{2}$ and $W|10\rangle$ by taking the difference between the second equation and the third one and then once again dividing by $\sqrt{2}$ May 15, 2023 at 7:40

According to the definition you gave, $$W=\left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1/\sqrt{2} & 1/\sqrt{2} & 0 \\ 0 & 1/\sqrt{2} & -1/\sqrt{2} & 0 \\ 0 & 0 & 0 & 1 \end{array}\right).$$ (Just think of the central $$2\times 2$$ block like a Hadamard, which would convert $$|+\rangle$$ to $$|0\rangle$$ and $$|-\rangle$$ to $$|1\rangle$$ except that, in this case, the basis elements are $$|01\rangle$$ and $$|10\rangle$$ instead of $$|0\rangle$$ and $$|1\rangle$$.)
• Awesome! Do you know why the circuit shows that the $|10\rangle$ output controls the CCNOT parity count of the bottom ancilla? May 15, 2023 at 12:27
• $T$ is basically the SWAP operator in parallel. Note that $S=I-2|\psi\rangle\langle\psi|$ where $|\psi\rangle=(|01\rangle-|10\rangle)/\sqrt{2}=W^\dagger|10\rangle$. This means that $e^{iSt}=e^{iSt}$ effectively adds a relative phase to the component in $|\psi\rangle$ compared to everything else. So, the idea is that $W$ converts the singlet state into $|10\rangle$. Then controlled off those qubits being $|10\rangle$, it adds a phase. May 15, 2023 at 12:36
• Oh I see! That's awesome! The H'nian in § 4.7.3 of Mike and Ike is a tensor product of $Z$ gates, where the unique eigenvector having an eigenvalue of $-1$ is $|1\rangle$ - this is why their circuit uses CNOT gates with a filled-in bubble to count the parity. But, the H'nian in Childs et al. is a tensor product of a bunch of SWAP gates, and the singlet state is the one having an eigenvalue of $-1$ - this maps to $|10\rangle$. Hence the circuit in Childs et al. has a CCNOT with a filled-in bubble for the first qubit and an open bubble for the second. How neat is that! May 17, 2023 at 20:21