Abstract: | It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes Fk, αd on 0, 1]d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(Fk, αd, ε)≍ε−1/γ and comprandom(Fk, αd, ε)≍ε−2/(1+2γ). For a quantum computer we prove compquantquery(Fk, αd, ε)≍ε−1/(1+γ) and compquant(Fk, αd, ε)⩽Cε−1/(1+γ)(log ε−1)1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove compcoin(Fk, αd, ε)⩽Cε−2/(1+2γ)(log ε−1)1/(1+2γ). To summarize the results one can say that • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small; • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small. |