Quantum Algorithms for Numerical Problems

It is a challenge to study the potential capabilities of quantum computing, that is, the question whether a (still to be built) quantum computer can solve computational problems (much) more efficiently than a classsical computer. This question has been considered for a number of problems, mostly of discrete nature. In this talk we are concerned with numerical problems of analysis. Answering any question of such type requires complexity theoretic tools, both for the classical and quantum setting. For numerical problems, these have been developed in information-based complexity theory. We give a survey on the development of numerical quantum algorithms, their complexity theory, and compare classical and quantum computation for a number of basic numerical problems. We also include a short introduction into quantum computing in general.