Quantum Walk Based Search Algorithms
In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of cla
- PDF / 487,211 Bytes
- 16 Pages / 430 x 660 pts Page_size
- 66 Downloads / 252 Views
1 CNRS–LRI, Universit´e Paris–Sud, 91405 Orsay, France Centre for Quantum Technologies, Nat. Univ. of Singapore, Singapore 117543
Abstract. In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.
1
Introduction
Searching is without any doubt one of the major problems in computer science. The corresponding literature is tremendous, most manuals on algorithms include several chapters that deal with searching procedures [22,14]. The relevance of finite Markov chains (random walks in graphs) to searching was recognized from early on, and it is still a flourishing field. The algorithm of Aleliunas et al. [4] that solves s–t connectivity in undirected graphs in time O(n3 ) and in space O(log n), and Sch¨ oning’s algorithm [33] that provides the basis of the currently fastest solutions for 3-SAT are among the most prominent examples for that. Searching is also a central piece in the emerging field of quantum algorithms. Grover search [16], and in general amplitude amplification [11] are well known quantum procedures which are provably faster than their classical counterpart. Grover’s algorithm was used recursively by Aaronson and Ambainis [2] for searching in grids. Discrete time quantum walks were introduced gradually by Meyer[27,28] in connection with cellular automata, and by Watrous in his works related to space bounded computations [37]. Different parameters related to quantum walks and possible speedups of classical algorithms were investigated by several researchers [30,8,3,29,19,32]. The potential of discrete time quantum walks with respect to searching problems was first pointed out by Shenvi, Kempe, and Whaley [34] who designed a quantum walk based simulation of Grover search. Ambainis, in his seminal paper [7],
Research supported by the European Commission IST Integrated Project Qubit Applications (QAP) 015848, and by the ANR Blanc AlgoQP grant of the French Research Ministry.
M. Agrawal et al. (Eds.): TAMC 2008, LNCS 4978, pp. 31–46, 2008. c Springer-Verlag Berlin Heidelberg 2008
32
M. Santha
used quantum walks on the Johnson graphs to settle the query complexity of the Element Distinctness problems. Inspired by the work of Ambainis, Szegedy [35] designed a general method to quantize classical Markov chains, and developed a theory of quantum walk based search algorithms. A similar approach for the specific case of searching in grids was taken by Ambainis, Kempe and Rivosh [9]. The frameworks of Ambainis and Szegedy were used in various contexts to find algorithms
Data Loading...
