Discrete-Time Quantum Walks on Compact Two-Dimensional Surfaces

Random walks are powerful tools that are widely used in algorithmic problems. Similarly, quantum random walks, the quantum mechanical counterpart of the classical random walks, have found applications in several quantum algorithms. The first quantum walk-based algorithm was formulated in 2002 by Childs. In the same year, Shenvi et al. introduced the first algorithm in the discrete-time quantum walk setting. Quantum walks have since been used in various algorithmic problems and have been shown to obtain speed-ups for a number of them compared to their classical analogues. The above establishes the importance of discrete-time quantum walks in the context of algorithms, and motivates their study in general. There are two types of quantum walks: continuous-time quantum walks and discrete-time random walks. Despite various studies into continuous-time walks on compact two-dimensional shapes, few results are available for the discrete-time version. This work therefore focuses on discrete-time quantum walks on finite two-dimensional lattices, and considers the effects of (twisted) periodic and reflective boundary conditions. More specifically, it discusses some of the key properties of quantum walks on the rectangle, torus, Klein bottle, cylinder and Möbius strip. These properties include limiting distributions and marginal distributions.