Volume 23, Issue 3
Quantum Complexity of the Integration Problem for Anisotropic Classes
DOI:

J. Comp. Math., 23 (2005), pp. 233-246

Published online: 2005-06

Preview Full PDF 0 639
Export citation

Cited by

• 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$\rm{\ddot{o}}$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$.

• Keywords

Quantum computation Integration problem Anisotropic classes Complexity

@Article{JCM-23-233, author = {}, title = {Quantum Complexity of the Integration Problem for Anisotropic Classes}, journal = {Journal of Computational Mathematics}, year = {2005}, volume = {23}, number = {3}, pages = {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$\rm{\ddot{o}}$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$. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/8812.html} }
TY - JOUR T1 - Quantum Complexity of the Integration Problem for Anisotropic Classes JO - Journal of Computational Mathematics VL - 3 SP - 233 EP - 246 PY - 2005 DA - 2005/06 SN - 23 DO - http://dor.org/ UR - https://global-sci.org/intro/jcm/8812.html KW - Quantum computation KW - Integration problem KW - Anisotropic classes KW - Complexity AB - 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$\rm{\ddot{o}}$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$.