This book addresses an interesting area of quantum computation called
quantum walks, which play an important role in building quantum
algorithms, in particular search algorithms. Quantum walks are the
quantum analogue of classical random walks.
It is known that quantum computers have great power for searching
unsorted databases. This power extends to many kinds of searches,
particularly to the problem of finding a specific location in a spatial
layout, which can be modeled by a graph. The goal is to find a specific
node knowing that the particle uses the edges to jump from one node to
the next.
This book is self-contained with main topics that include:
- Grover's algorithm, describing its geometrical interpretation and
evolution by means of the spectral decomposition of the evolution
operator
- Analytical solutions of quantum walks on important graphs like line,
cycles, two-dimensional lattices, and hypercubes using Fourier
transforms
- Quantum walks on generic graphs, describing methods to calculate the
limiting distribution and mixing time
- Spatial search algorithms, with emphasis on the abstract search
algorithm (the two-dimensional lattice is used as an example)
- Szedgedy's quantum-walk model and a natural definition of quantum
hitting time (the complete graph is used as an example)
The reader will benefit from the pedagogical aspects of the book,
learning faster and with more ease than would be possible from the
primary research literature. Exercises and references further deepen the
reader's understanding, and guidelines for the use of computer programs
to simulate the evolution of quantum walks are also provided.
