Discrete quantum walks are quantum analogues of classical random walks. They are an important tool in quantum computing and a number of algorithms can be viewed as discrete quantum walks, in particular Grover's search algorithm. These walks are constructed on an underlying graph, and so there is a relation between properties of walks and properties of the graph. This book studies the mathematical problems that arise from this connection, and the different classes of walks that arise. Written at a level suitable for graduate students in mathematics, the only prerequisites are linear algebra and basic graph theory; no prior knowledge of physics is required. The text serves as an introduction to this important and rapidly developing area for mathematicians and as a detailed reference for computer scientists and physicists working on quantum information theory.
In the past few decades, quantum algorithms have become a popular research
area of both mathematicians and engineers. In 2003, Childs et al. found a graph
in which the continuous-time quantum walk spreads exponentially faster than any
classical algorithm for a certain black-box problem. Since then, there are
extensive explorations on quantum walks on graphs. Among them, uniform mixing
provides a uniform probability distribution of information over time which
attracts a special attention. However, there are only a few known examples of
graphs which admit uniform mixing. In this paper, we give a characterization of
abelian Cayley graphs having uniform mixing. Some concrete constructions of
such graphs are provided. Particularly, for cubelike graphs, it is shown that
the Cayley graph
Cay(F22k;S) having uniform mixing if and
only if
f is a bent function, where
f is the characteristic function of
S.
Quantum walks (QWs) are the quantum analogue to classical random walks. We explore various implementations of QWs and create visualizations for each, with the goal of increasing educational accessibility. A new QW, called sticky walk, is introduced, where the walker sticks to targets once found. Corresponding pseudocode and Qiskit implementations are provided. Sticky walk helps bridge the gap between non-searching QWs and Quantum Walk Search (which may be an unintuitive search algorithm for those new to QWs).