Foundations of Quantum Programming

5.1.3 An Example

We now give an example to show how Proposition 5.1.2 can be applied to quantum walks in order to compute their average running time. We consider a quantum walk on an n-circle. It can be seen as a variant of a one-dimensional quantum walk, and it is also a special case of quantum walk on a graph defined in Subsection 2.3.4.

Let ${\mathcal{H}}_d$ be the direction space, which is a 2-dimensional Hilbert space with orthonormal basis state |L〉 and |R〉, indicating directions Left and Right, respectively. Assume that the n different positions on the n-circle are labelled by numbers 0,1,…,n − 1. Let ${\mathcal{H}}_p$ be an n-dimensional Hilbert space with orthonormal ...