Quantum random walk search optimization using resetting techniques

Abstract

Quantum algorithms have shown much potential in solving complex problems more efficiently than our current classical algorithms, particularly in search problems with a large and complex search space. When leveraging the principles of superposition and interference, quantum walk based algorithms can lead to a faster convergence on a target state. The thesis begins with a theoretical framework for the study of classical and quantum walks on graphs. The usage in search algorithms is discussed together with the effect of a modified Hamiltonian that introduces a bias toward the target state. This is analyzed using perturbation theory showing a decrease of the ground state energy. Ultimately, this thesis focuses on the optimization of quantum random walk search algorithms using resetting techniques. Simulations of quantum random walks on simple graph structures, such as path and cycle graphs are used to provide concrete examples. Results show that resetting not only improves the probability of finding the target state, but also has a faster convergence. Furthermore, decoherence effects are shown to be reduced when using resetting techniques.