Year: 2005
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 3 : pp. 233–246
Abstract
We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes $W_{\infty}^{\bf r}([0,1]^d)$ and Hölder Nikolskii classes $H_{\infty}^{\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_{\infty}^{\Lambda}(D)$ whose smoothness index is the boundary of some complete set in $\mathbb{Z}_+^d$.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2005-JCM-8812
Journal of Computational Mathematics, Vol. 23 (2005), Iss. 3 : pp. 233–246
Published online: 2005-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 14
Keywords: Quantum computation Integration problem Anisotropic classes Complexity.