Zur Seitenansicht


The Relationship Between Coined and Szegedy-Type Quantum Walks
VerfasserSandbichler, Michael
Betreuer / BetreuerinBriegel, Hans Jürgen
HochschulschriftInnsbruck, Univ., Masterarb., 2016
Arbeit an der Bibliothek noch nicht eingelangt - Daten nicht geprüft
Datum der AbgabeMärz 2016
Schlagwörter (DE)Quanteninformation
Schlagwörter (EN)Quantum information / Quantum walks / Quantum algorithm / Graph theory / Markov chains
URNurn:nbn:at:at-ubi:1-4152 Persistent Identifier (URN)
 Das Werk ist frei verfügbar
The Relationship Between Coined and Szegedy-Type Quantum Walks [0.5 mb]
Zusammenfassung (Englisch)

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.