TY - JOUR
T1 - Quantum Complexity of the Integration Problem for Anisotropic Classes
AU - Xiao-Fei Hu & Pei-Xin Ye
JO - Journal of Computational Mathematics
VL - 3
SP - 233
EP - 246
PY - 2005
DA - 2005/06
SN - 23
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jcm/8812.html
KW - Quantum computation, Integration problem, Anisotropic classes, Complexity.
AB - <p style="text-align: justify;">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$. &nbsp;</p>