It is known that quantum computers yield a speed-up for certain discrete pr
oblems. Here we want to know whether quantum computers are useful for conti
nuous problems. We study the computation of the integral of functions from
the classical Holder classes F-d(k,alpha) on [0, 1](d) and define gamma by
gamma = (k + alpha)/d. The known optimal orders for the complexity of deter
ministic and (general) randomized methods are comp(F-d(k,alpha), epsilon) a
symptotic to epsilon (-1/gamma) and comp(random)(F-d(k,alpha), epsilon) asy
mptotic to epsilon (-2/(1+2 gamma)). For a quantum computer we prove comp(q
uery)(quant) (F-d(k,alpha), epsilon) asymptotic to epsilon (-1/(1+gamma)) a
nd comp(quant)(F-d(k,alpha), epsilon) less than or equal to C epsilon (-1/(
1+gamma))(log epsilon (-1))(1/(1+gamma)). For restricted Monte Carlo (only
coin tossing instead of general random numbers) we prove comp(com)(F-d(k,al
pha), epsilon) less than or equal to C epsilon (-2/(1+2 gamma))(log epsilon
(-1))(1/(1+2 gamma)). To summarize the results one can say that
. there is an exponential speed-up of quantum algorithms over deterministic
(classical) algorithms, if gamma is small;
. there is a (roughly) quadratic speed-up of quantum algorithms over random
ized classical methods, if gamma is small:
. there is a (roughly) quadratic sped-up of quantum algorithms over randomi
zed classical methods, if gamma is small. (C) 2001 Academic Press.