Introduction

Random walks are a commonly used tool in the arsenal of algorithms on Classical Computers to solve a variety of problems which do not have a known easy solution. The power of such methods can be attributed to the fact that while the space of possible solutions is vast, we only need to sample few solutions to come to a close solution. This power has been routinely exploited in the past to sample from Markov Chains using the MCMC algorithm which can be found in any introductory textbook¹ of Markov processes, and they have recently been used in the fields of Financial engineering², fluid mechanics³, fitting black hole images⁴ and most famously in the Los Alamos project⁵.

With the advent of quantum algorithms, quantum walks have arisen as an obvious extension of classical walks in the quantum domain. The applications of quantum walks are just as many: ANN training⁶, Random Number Generation⁷, List coloring (Grover)⁸, collision finding⁹, link prediction¹⁰. There has even been a recent foray into classifying and using a quantum-classical walk to speed up certain classical algorithms, namely the Google PageRank Algorithm¹¹. The increased interest in quantum walks can be attributed to the quadratic speed up which it grants the solution a-la the Grover algorithm, which itself can be considered as a Quantum Walk¹².

In this master thesis, we will first define the classical (Chapter 1) walk, and specifically, the 1D walk. The classical 1D walk has a standard deviation which goes as \(\mathcal{O}(T^{1/2})\), and is recurrent.

Then we define quantum (Chapter 2) walk, particularly the coined walk on a 1D grid. The quantum 1D walk has a standard deviation which goes as \(\mathcal{O}(T)\), and is transient.

We define these walks with a view of using these walks in search algorithms. We formalise the search problem and show how the quantum walk is faster, but its transient nature leads to a non-zero asymptotic failure rate in Chapter 3.

Then, we look at previous attempts at solving this by resetting (Chapter 4). By resetting a Markov chain, we can convert a transient chain to a recurrent one. We explore the effect of resetting in the quantum case, attempting to recreate past work in continuous time quantum walks in the discrete time quantum walks. We also look at possible shortcomings of the solution.

In Chapter 5, we introduce a new mechanism for quantum resetting based on superposition of the evolution and reset operations and show numerically that it does not have a clear advantage in the search problem (Chapter 5). Due to the complexity of the formalism, we approach quantum resetting unitarily.

Finally, we introduce a second protocol for reset quantum walks by quantising the Markov process via Szegedy walks (Chapter 6). We also present a Grover like search algorithm, which is easily analyzable by eigenvalue analysis. The results and discussions of this protocol are presented in Chapter 7. We then conclude and provide future directions of this work in Chapter 8.

Along with the theory, certain aspects of the implementation of the walks computationally are also added as necessary. This is done inline instead of in an appendix, which is the norm, since the author believes that such a presentation solidifies the readers’ understanding of both, the model and the implementation. We use Julia¹³ and its standard libraries, Plots.jl¹⁴, QuantumInformation.jl¹⁵, Luxor.jl¹⁶, Yao.jl and YaoPlots.jl¹⁷.