Since their inception at the end of the 1990s, quantum walks have proven to be a valuable concept for constructing quantum algorithms that surpass their classical counterparts in terms of runtime complexity. Quantum walks can be thought of as the 'quantum analogue' of random walks, and hence several different ways of constructing them have been devised.
The goal of this thesis is a self-contained introduction to the theory of quantum walks, their applications and interrelations. We will first review the necessary mathematics and physics and introduce what we mean by a quantum walk. Then we establish two seemingly very different methodologies for performing quantum walks in discrete time, namely coin- and Szegedy walks, and apply them to graph traversing and searching problems. In both cases, a speedup over classical algorithms is achieved.
In the final part of the thesis, we will examine the connection of the two different quantum walks by finding conditions, when they directly correspond to each other. We furthermore use this connection in order to numerically investigate the stability of the quantum speedup for hypercube traversing.