(untitled) (Journal of Computational Mathematics, 2005)
We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes W_∞^r([0,1]^d) and Hölder Nikolskii classes H_∞^r([0,1]^d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n^-1 and over randomized classical methods due to factor n^-1/2. Moreover, we give an estimation for optimal query complexity in the class H_∞^Λ(D) whose smoothness index is the boundary of some complete set in Z_+^d.