caa a22 4500 467914095 CHVBK 20180406152857.0 cr unu---uuuuu 170328e20061001xx s 000 0 eng 10.1007/s00450-006-0008-7 doi (NATIONALLICENCE)springer-10.1007/s00450-006-0008-7 Rötteler Martin Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Quantum algorithms: Asurvey of some recent results [Elektronische Daten] [Martin Rötteler] Quantum algorithms are afield of growing interest within the theoretical computer science as well as the physics community. Surprisingly, although the number of researchers working on the subject is ever-increasing, the number of quantum algorithms found so far is quite small. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. In this paper we give an overview of the known quantum algorithms and briefly describe the underlying ideas. Roughly, the algorithms presented are divided into hidden subgroup type algorithms and in amplitude amplification type algorithms. While the former deal with problems of group-theoretical nature and have the promise to yield strong separations of classical and quantum algorithms, the latter have been proved to be aprolific source of algorithms in which apolynomial speed-up as compared to classical algorithms can be achieved. We also discuss quantum algorithms which do not fall under these two categories and give asurvey of techniques of general interest in quantum computing such as adiabatic computing, lower bounds for quantum algorithms, and quantum interactive proofs. Springer-Verlag, 2006 Informatik - Forschung und Entwicklung Springer-Verlag 21/1-2(2006-10-01), 3-20 0178-3564 21:1-2<3 2006 21 450 https://doi.org/10.1007/s00450-006-0008-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00450-006-0008-7 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Rötteler Martin Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 773 0- Informatik - Forschung und Entwicklung Springer-Verlag 21/1-2(2006-10-01), 3-20 0178-3564 21:1-2<3 2006 21 450 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer