Quantum complexity of integration

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.