Hitting Times of Quantum Random Walks

Random walks have been applied in a many different fields for a long time. More recently, classical random walks are being used in wide variety of computer algorithms used to solve complex computational problems like 2-SAT, 3-SAT and the estimation of the volume of complex bodies. In this thesis we look into the quantum version of the familiar random walk, distinguishing between the discrete- and continuous-time quantum randomwalk. Some general properties of random walks are studied throughout this thesis. First we look at the behaviour of both the classical and the random walk on a simple 1-dimensional lattice. Then, to investigate the speed and efficiency of algorithms that use quantumwalks, we analyse quantumrandom walks in graphs, as graphs do a good job of representing the decision trees of algorithms. The graph we look at specifically is the ndimensional hypercube. The criterion we use to see how fast a quantumwalk can traverse certain types of graph is the hitting time. The hitting time is the expected amount of time a random walk takes to reach a certain vertex in a graph for the first time. Literature has shown that classical random walks have a hitting time that scales exponentially with the dimension n of the hypercube. We find that quantum random walks offer a significant speed-up to its classical counterpart. Generally they have a polynomial hitting time, that depends on the Hamming distance between the start and sink vertex. Furthermore we find that quantum walks can have interesting properties such as a non-unitary hitting probability, meaning the quantum walker will never visit the sink vertex. Finally we see that, in some simple, symmetric cases, the hitting time of the quantum walk even is sub-linear, scaling almost like a square root, rather than a polynomial.Applied Mathematics | Applied Physic