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:

Circuit in Childs et al.

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.

  • 1
    $\begingroup$ 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}$ $\endgroup$ May 15, 2023 at 7:40

1 Answer 1


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$.)

  • $\begingroup$ Awesome! Do you know why the circuit shows that the $|10\rangle$ output controls the CCNOT parity count of the bottom ancilla? $\endgroup$ May 15, 2023 at 12:27
  • 1
    $\begingroup$ $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. $\endgroup$
    – DaftWullie
    May 15, 2023 at 12:36
  • $\begingroup$ 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! $\endgroup$ May 17, 2023 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.