Efficient Quantum Algorithms (In German: Effiziente Quantenalgorithmen)

Ever since the discovery of efficient quantum algorithms for factoring and computing discrete logarithms by Shor in 1994, the interest in quantum algorithms was growing within the theoretical computer science as well as the physics community. Surprisingly, the number of quantum algorithms found so far is quite small, although the number of researchers working on the subject is rapidly increasing. In fact, the task of designing new quantum algorithms has been proven to be extremely difficult. We give an overview of the problems for which an efficient quantum algorithm is known and briefly describe the underlying ideas. One large area of problems where a quantum computer appears to be superior to classical computers are the so-called hidden subgroup problems. We explain the relevance and the motivation behind this abstract class of problems.