acta physica slovaca |
|
|
Acta Physica Slovaca 61, No.6, 603-725 (2011) (123 pages)
QUANTUM WALKS Daniel Reitzner1, Daniel Nagaj2, and Vladimír Bužek2 1 Department of Mathematics, Technische Universitat Munchen, 85748 Garching, Germany 2 Research Center for Quantum Information, Institute of Physics, Slovak Academy of Sciences, Dúbravská cesta 9, 845 11 Bratislava Full text: ::pdf :: (Received 16 July 2012, accepted 20 July 2012) Abstract: This tutorial article showcases the many varieties and uses of quantum walks. Discrete time quantum walks are introduced as counterparts of classical random walks. The emphasis is on the connections and differences between the two types of processes (with rather different underlying dynamics) for producing random distributions. We discuss algorithmic applications for graph-searching and compare the two approaches. Next, we look at quantization of Markov chains and show how it can lead to speedups for sampling schemes. Finally, we turn to continuous time quantum walks and their applications, which provide interesting (even exponential) speedups over classical approaches. DOI: 10.2478/v10155-011-0006-6 PACS: 03.67.-a, 03.65.-w, 05.40.Fb Keywords: Quantum Walks, Random Walks, Quantum Algorithms, Markov Chains |
ISSN 1336-040X (online) ISSN 0323-0465 (printed) For authors: ActaStyle.cls |
| © published by Institute of Physics, Slovak Academy of Sciences. All rights reserved. | |