Quantum walks and spatial search on regular graph

Abstract

Random walks and algorithms based upon them are used widely to explore large state spaces that arise while studying physical systems. In this thesis, we will discuss some quantum generalizations of such algorithms and study their complexity. In the first part of this talk, we will discuss quantum search in the presence of spatial constraints. One of the main results in this thesis is an efficient search algorithm that can find multiple marked elements under spatial constraints imposed by regular graphs. Next, we will focus attention on two-dimensional square lattices. Building on our earlier algorithmic framework, we will show that optimal quantum search is possible on the square lattice by only mildly violating the locality constraints imposed by the graph. This investigation leads to a general prescription for dealing with the graph powering operation in the quantum walk framework. After this, we will move on to discussing mixing times of quantum walks. We will show that a fully decohered quantum walk mixes asymptotically at the same rate as its classical counterpart only if its degree is a constant function of its size. We will also present some numerical evidence showing that faster mixing is possible using a weakly decohered quantum walk, if the decoherence probability is tuned in relation to the spectral gap of the graph. Finally, we will also discuss the implementation of quantum walks and spatial search on IBM's quantum computing platform.