full
search.png

Search

close.png

Cancel

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

Xiao-Fei Hu & Pei-Xin Ye

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

Published online: 2005-06

Preview Full PDF 2423 26487

Cited by

google scholar semantic scholar
Export citation
  • 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$.  

  • Keywords

Quantum computation, Integration problem, Anisotropic classes, Complexity.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-23-233, author = {Xiao-Fei Hu and Pei-Xin Ye}, 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ö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 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 -

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$.  

Xiao-Fei Hu and Pei-Xin Ye. (2005). Quantum Complexity of the Integration Problem for Anisotropic Classes. Journal of Computational Mathematics. 23 (3). 233-246. doi:
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard