# continuous time quantum walk on a cycle - transition matrix

I am trying to find the transition matrix for a quantum walk on a cycle. The vertices are labelled $$\lbrace 0,1,2,\ldots,n-1\rbrace$$, where vertex $$i$$ is a neighbour of vertex $$i \pm 1$$. Lets say we start at vertex 0. Then we are interested in $$\langle i \vert U(t) \vert 0 \rangle$$.

I have calculated the following: The normalized adjacency matrix for A is a circulant matrix, hence (normalized) eigenvectors and eigenvalues are $$v_j= \dfrac{1}{\sqrt{n}}\left( \omega_j^0, \omega_j^1,\ldots,\omega_j^{n-1}\right) \text{ and }\\ \lambda_j= \cos(2 \pi j / n), \hspace{2cm} \text{ respecively.}$$.

Thus, $$U(t)= \exp(iAt)= \sum\limits_{j=1}^n\exp(i t \lambda_j ) v_j v_j^\dagger$$.

This gives,

$$\langle i \vert U(t) \vert 0 \rangle = \langle i \vert \sum\limits_{j=1}^n\exp(i t \lambda_j ) v_j v_j^\dagger \vert 0 \rangle$$ $$= \sum\limits_{j=1}^n \exp(i t \lambda_j ) \langle i \vert v_j v_j^\dagger \vert 0 \rangle$$ $$= \sqrt{\dfrac{1}{n}}\sum\limits_{j=1}^n \exp(i t \lambda_j ) \langle i \vert v_j \rangle$$ $$={\dfrac{1}{n}}\sum\limits_{j=1}^n \exp(i t \lambda_j )\ \ {\omega_j}^{i}$$.

Is this calculation correct? Is there a way to further simplify this?

Is there another way to get compact expression (in terms of t) for the matrix $$U(t)$$?

• To clarify, you don't have a Hadamard coin here, and you are just evolving unitarily according to the Hamiltonian by $e^{-iAt}$, right? Here you are asking for transition probability (transition amplitude) of evolving from node $0$ to node $i$ at time $t$, right? Classically walking on a cycle you get to the uniform distribution in roughly $\mathcal{O}(\sqrt n)$ time Commented Sep 19, 2022 at 16:20
• @Yes. That is correct. We have the standard definition of continuous time quantum walk.
– Root
Commented Sep 19, 2022 at 16:59

(Not much of an answer yet, just some tentative ideas about how to simulate a continuous-time random walk on a cycle for now. I describe how to take a small quantum walk for a short amount of time, but I'm otherwise getting stuck.)

Recall that the cycle graph on $$n$$ vertices is isomorphic to the Cayley graph of the additive group $$\mathbb Z/n\mathbb Z$$ with generators $$\pm 1$$, which is isomorphic to the rotations of the $$n$$-gon with clockwise or right $$R$$ and counterclockwise or left $$L$$ rotations.

We'll start off with $$n=4$$ for simplicity and convenience. We have $$n=4$$ qubits labeled $$\{|0\rangle,|1\rangle,|2\rangle,|3\rangle\}$$, and we can use the following SWAP circuits that perform the rotations:

There's nothing quantum about this circuit yet, but we can use phase estimation to take the roots of each of $$L$$ and $$R$$, as we know that the eigenvalues of $$R$$ and $$L$$ are $$\{\pm 1, \pm i\}$$ because $$L^4=R^4=I$$. These eigenvalues correspond to the $$\lambda_j$$ in the question.

Letting $$|\psi\rangle$$ be the wavefunction for registers $$|0\rangle|1\rangle|2\rangle|3\rangle$$, below are the $$4$$-th root of $$R$$ and $$L$$:

It's the fourth root in particular because of the $$T=\sqrt[4]Z$$ and $$S=\sqrt[2]Z$$ gates in the middle of the circuit - if we want a smaller movement corresponding to a larger root, we'd use other roots of $$Z$$. Let's call this power the Trotter factor. As this factor increases to infinity, I think we're approaching continuous-time evolution.

We can go back and forth between the $$r$$th root of a clockwise right rotation and a counterclockwise left rotation. An iteration would be:

$$\sqrt[4]{R}\sqrt[4]{L}\sqrt[4]{R}\sqrt[4]{L}\sqrt[4]{R}\sqrt[4]{L}\sqrt[4]{R}\sqrt[4]{L}\cdots$$

I'd like to get this to be a continuous-time quantum walk, corresponding to a little walk to the right (clockwise), then a walk to the left (counterclockwise), then... etc. But, this ends up being the identity after only two repetitions, I think. Either I'm doing something wrong (highly likely), or such a walk on the graph cycles quickly back and forth between the identity, perhaps?

• Thanks for your answer but here I am more interested in the transition probabilities rather than the actual circuit or implementation. What I am looking for is the probability that quantum walk is at vertex j at time t. I have included a calculation in the question, I want to know a) if it is correct b) Is there a way to further simplify this>
– Root
Commented Sep 22, 2022 at 6:27
• @Root have you thought about explicitly working out $U(t)$ for small $n$, such as $n=4$? Commented Sep 22, 2022 at 12:33