| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 311
E. Novak
Quantum complexity of integration
Abstract
We study the computation of the integral of functions from the classical
Hoelder classes with d variables. The optimal orders for the complexity of
deterministic and (general) randomized methods are known. We obtain the
respective optimal orders for quantum algorithms and also for restricted Monte
Carlo (only coin tossing instead of general random numbers).
To summarize the results one can say that
a) there is a (roughly) quadratic
speed-up of quantum algorithms over randomized classical methods, if the
"smoothness" is low;
b) there is an exponential speed-up of quantum algorithms
over deterministic (classical) algorithms, if the "smoothness" is low.
