A mathematical study of quantum walk-based applications

Abstract

Quantum walk is a framework for quantum computing, which has been studied extensively. In this thesis, our first consideration is the quantum walk framework in both discrete and continuous forms, where we explore its capabilities and limitations in solving graph theoretic problems such as vertex partitioning and isomorphism testing. In the first part of the thesis, we develop a vertex-partitioning scheme for graphs, based on the quantum walk-based search. Secondly, we study the capacity of quantum walks as a tool for graph isomorphism testing. In particular, we prove that the continuous time quantum walks cannot be modified with a phase factor equivalent to the phase-modified discrete time quantum walks, so that it would distinguish a pair of strongly regular graphs in polynomial time. Considering the need of applying quantum walks over connected graphs and similar operations, it is worthwhile to adopt the quantum circuit framework as well. Therefore we consider implementing efficient matrix operations through quantum circuits. Accordingly, we develop quantum algorithms for implementing sparse or Fourier-sparse Toeplitz and Hankel matrices, which are exponentially faster than the classical algorithms. Also we develop quantum algorithms for solving vibrating systems with rotational symmetry.