Title: Quantum complexity of integration
Authors: Novak, Erich
Issue Date: Aug-2000
Publisher: Department of Computer Science, K.U.Leuven
Series Title: TW Reports vol:TW311
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.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Numerical Analysis and Applied Mathematics Section

Files in This Item:
File Description Status SizeFormat Published 133KbView/Open


All items in Lirias are protected by copyright, with all rights reserved.