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

  • $\begingroup$ 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 $\endgroup$ Commented Sep 19, 2022 at 16:20
  • $\begingroup$ @Yes. That is correct. We have the standard definition of continuous time quantum walk. $\endgroup$
    – Root
    Commented Sep 19, 2022 at 16:59

1 Answer 1


(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:

SWAP circuits

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$:

Fourth Roots of Rotations

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:


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?

  • $\begingroup$ 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> $\endgroup$
    – Root
    Commented Sep 22, 2022 at 6:27
  • $\begingroup$ @Root have you thought about explicitly working out $U(t)$ for small $n$, such as $n=4$? $\endgroup$ Commented Sep 22, 2022 at 12:33

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.