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.
