Quantum Complexity of the Integration Problem for Anisotropic Classes (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_{∞}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{∞}^{\bf 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 $\mathbb{Z}_+^d$.
Keywords: Quantum computation; Integration problem; Anisotropic classes; Complexity.