One-dimensional Hadamard Quantum Walk on a Cycle with Rotational Implementation

Abstract

Quantum walks have been extensively studied recently, mainly due to their vast difference in behavior to classical random walks. This paper is concerned with discrete time and space quantum walks of particles that propagate through a one-dimensional line. This line can be either a lattice or a graph or any other form of mathematical structure that can be viewed as a one-dimensional line. First is defined a concrete way to describe the unitary evolution of a quantum walk through a balanced coin operator and a shift operator. Then follows the implementation of the quantum walk on an $8$-cycle, i.e a cycle graph with $8$ nodes, which is then run locally as a simulation and on IBM's quantum computer. The paper explores two implementations of the quantum walk as a quantum circuit: the first one consists of generalised controlled inversions, as introduced in \cite{EffWalk}, whereas the second one tries to replace them with rotation operators around the basis states. The main aim is to find a way around the caveat resulting from the large amount of ancilla qubits required to carry out the computation in the case where only generalised inverters are used. Next, another three experiments are computed, involving cycles with a larger state space, more specifically $16$, $32$ and $64$ possible positions. In order to measure the magnitude of the error of the circuit we use the cross entropy benchmarking method, calculated through the Hellinger distance. Finally, a derivation of the variance of the quantum walk is provided along with a calculation of the variance for our experiment.