A challenging question in the overlap of computer science, mathematics, and physics is the exploration of potential capabilities of - up to now still hypothetical - quantum computers. Milestones were the algorithm of Shor (1994), who showed that quantum computers could factor large integers efficiently (which is widely believed to be infeasible on classical computers) and the quantum search algorithm of Grover (1996), which provides a quadratic speedup over deterministic and randomized classical algorithms of searching a database.
So far research was mainly concentrated on discrete problems like the above and many others one encounters in computer science. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical setting. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (that is, on a quantum computer) and how the outcome compares to the efficiency of deterministic or Monte Carlo algorithms on a classical (i.e. non-quantum) computer.
In the talk we first give an introduction into the basic ideas of quantum computation. Then we discuss recent results on quantum algorithms for approximating the mean of p -summable sequences and the integral of functions from Lp and Sobolev spaces. We also include complexity results and comparisons to the classical settings.