Quantum circuit for Szegedy quantum walk on a cyclic graph

Question

I'm trying to implement an efficient circuit for the Szegedy quantum walk on a cyclic graph with number of nodes N = 8. I found the circuit in this thesis (page 39), the two images below show graph and circuit. I've already wrote the code using Qiskit.

The problem I am facing is how to perform a step, so how to pass as input the superposition of qubits that represents my current position and how to retrieve the next possible positions.

As suggested in the reference for the current position I'm using as state vector|$\phi_{0}\rangle = [0,\frac{1}{\sqrt{2}},0,...,0,\frac{1}{\sqrt{2}}]^{T}$ that is the column in the transition matrix P that represents node 0 then considering a state |x,y$\rangle$ as a state for the Szegedy QW I place the vector $|\phi_{0}\rangle$ in position x expecting the output in y.

To construct the vector |$\phi_{0}\rangle$ I am using an Hadamard gate and some C-NOT gates in sequence This simulation in Quirk explains better what I said before showing what I am trying to do. I don't know if I am making any serious theoretical mistakes but the results doesn't make so much sense.

Answer 1

It's been a long while since I've looked at my thesis, so a lot of my knowledge is pretty rusty, but here goes.

If you're looking for the circuit representation of $C_8$, here's the Quirk simulation for it. The first two columns prepare the state $|\phi_0\rangle = \frac{1}{\sqrt{2}}(|001\rangle+|111\rangle)$ in big-endian order (the dominant convention years back), which in Quirk is $\frac{1}{\sqrt{2}}(|100\rangle+|111\rangle)$ because it uses little-endian order.

One important difference from your Quirk simulation is that only 6 qubits are needed, 3 for each register. The circuit shown in the figure was meant to display the generic circuit for any $N=2^n$ (it looks like it was missing a few vertical dots to between the second and third qubits of each register to denote the generalisation), not $N=2^3=8$ specifically. Note also how the L (left-rotation) and R (right-rotation) operators are defined.

To make sense of the results, the qualitative way of looking at this is that the initial state $|\psi_0\rangle=|0\rangle|\otimes|\phi_0\rangle$ means that we start at the vertex 0 on the graph $C_8$, with a half-half mixture of the edge states on said vertex. So when we propagate the edge states, we'd expect the amplitudes to shift to the adjacent vertices $|100\rangle$ and $|111\rangle$ (in little-endian) after one time-step. Measuring the probability of being on a particular vertex is done by measuring the probability distribution over the first register of qubits (the first 3 in this instance). From the output of the Quirk circuit, we see a 50% probability on the adjacent vertices, which matches the expectation.

We can also inspect this analytically. The Szegedy operator is defined as $U_{walk}=S(I-2\Pi)$, where the swap operator $S$ acts as $S|i,j\rangle=|j,i\rangle$, and $\Pi=\sum_{i=0}^{N-1}|\psi_i\rangle\langle\psi_i|=\sum_{i=0}^{N-1}(|i\rangle\otimes|\phi_i\rangle)(\langle i|\otimes\langle\phi_i|)$. With the initial state $|\psi_0\rangle=|0\rangle|\otimes|\phi_0\rangle$, and given that $\langle\psi_i|\psi_j\rangle=\delta_{i,j}$, it can be easily shown that $U_{walk}|\psi_0\rangle=-|\phi_0\rangle\otimes|0\rangle$, which matches the qualitative expectation, and the Quirk circuit output.

I hope that helps! :)

-Thomas