Defining a discrete quantum walk on a 3D hypercube

Question

I am trying to implement at a discrete-time quantum walk on a 3D hypercube using cirq.

I have three qubits for the position register: the $|x\rangle$ qubit, $|y\rangle$ qubit and $|z\rangle$ qubit, and the hamming distance between two adjacent vertices is always one. I am not sure how to implement the coin 'qubit': at each step there are three vertices the walker can walk to (where each possibility has 1 qubit flipped from the original qubit), so I would need a 3D coin. I can't use one qubit for my coin, as that would only give me $2$ directions to walk into, and I can't use two qubits for the coin, as that would leave me with one direction too many. So, I thought I could implement it using a qutrit, so that if the coin state is $|1\rangle$ I flip the $|x\rangle$ qubit, if the coin state is $|2\rangle$ I flip the $|y\rangle$ qubit and if the coin state is $|3\rangle$ I flip the $|z\rangle$ qubit. This would correspond to walking to an adjacent vertex (since the hamming distance is one).

So now I have 2 questions:

1. [general question] Is using a qutrit the best way to implement my coin? Is this experimentally feasible now? Can I just combine qubits and qutrits? Or more generally, what are the implications of using qutrits?
2. [cirq specific question] How would I now define controlled NOT gates where my control is a qutrit?

Thanks!

Answer 1

I can't answer your cirq-specific question, but your general approach is on the right path. For example, beginning on the first column of page 7 of Kempe's article on quantum walks, to walk along a $d$-dimensional hypercube $|\psi\rangle=|xyz\rangle$ with $\{x,y,z\}\in\{0,1\}^3$, we can use a $d$-dimensional coin or dice, controlling the transitions based on the value of the coin in the way you propose.

Letting $\omega=(-1+i\sqrt 3)/2$ be the principle cube root of unity, you can use a three-dimensional Fourier transform acting on your qutrit coin $|C_3\rangle$:

$$H_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1&1&1\\ 1&\omega&\omega^2\\ 1&\omega^2&\omega \end{pmatrix}.$$

You can control off the value of your qutrit coin $|C_3\rangle$, iterating between $H_3$ and controlled-NOT's along your cube $|\psi\rangle=|xyz\rangle$. For example, if $|C_3\rangle=|2\rangle$ then we can map $|\psi\rangle$ from $|xyz\rangle$ to $|x\bar y z\rangle$, etc.

Indeed, even though you are correct that two qubits may be overkill, you can still use two qubits instead of one qutrit, by never have your four-dimensional coin transition to, say, $|11\rangle$:

$$H_3' = \frac{1}{\sqrt{3}} \begin{pmatrix} 1&1&1&0\\ 1&\omega&\omega^2&0\\ 1&\omega^2&\omega&0\\ 0&0&0&\sqrt 3 \end{pmatrix}.$$

The fourth row (and fourth column) never come in to play if you initialize your two control qubits as $|C_4\rangle=|00\rangle$. Instead of three CNOT's with a qutrit control you could use three CCNOT's with two qubit controls.

Certainly if you are walking on a four-dimensional cube (a tesseract), you could use a four-dimensional qudit controlling the transition, or it would be easier to just walk with two qubits. Also, your other related question about whether qutrits are experimentally feasible now has was previoulsy discussed here.