|Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW)|
Quantum complexity of integration
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.