Quantum algorithms: A?survey of some recent results |
| |
Authors: | Martin R?tteler |
| |
Institution: | (2) Institute for Quantum Computing and Dept. of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada;(3) St. Jerome's University, Waterloo, Canada;(4) Perimeter Institute for Theoretical Physics, Waterloo, Canada;; |
| |
Abstract: | Quantum algorithms are a field 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 a prolific source of algorithms
in which a polynomial 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 a survey of techniques of
general interest in quantum computing such as adiabatic computing, lower bounds for quantum algorithms,
and quantum interactive proofs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|