QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(Wpr([0, 1]d)) AND Β(Hpr([0, 1]d))

doi:10.1016/S0252-9602(10)60174-9

Acta mathematica scientia,Series B ›› 2010, Vol. 30 ›› Issue (5): 1808-1818.doi: 10.1016/S0252-9602(10)60174-9

• Articles • Previous Articles Next Articles

QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(W_p^r([0, 1]^d)) AND Β(H_p^r([0, 1]^d))

YE Pei-Xin, HU Xiao-Fei

School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China; College of Mathematical, Syracuse University, |NY 13210, USA

Received:2006-03-03 Revised:2008-10-10 Online:2010-09-20 Published:2010-09-20
Supported by:
Supported by the Natural Science Foundation of China (10501026, 60675010,10971251).

Abstract

Abstract:

We study the approximation of functions from anisotropic Sobolev classes B(W_p^r}([0, 1]^d)) and H\"{o}lder-Nikolskii classes B(H_p^r}([0, 1]^d)) in the L_q([0, 1]^d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.

Key words: quantum approximation, anisotropic classes, minimal query error

CLC Number:

41A55

YE Pei-Xin, HU Xiao-Fei. QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(W_p^r([0, 1]^d)) AND Β(H_p^r([0, 1]^d))[J].Acta mathematica scientia,Series B, 2010, 30(5): 1808-1818.

Trendmd

References

[1] Dahmen W, DeVore R, Scherer K. Multi-dimensional Spline approximation. SIAM J Numer Anal, 1980, 17: 380--402

[2] Fang Gensun, Hickernell F J, Li Huan. Approximation on anisotropic Besov classes with mixed norm by standarded information. J Complexity, 2005, 21: 294--313

[3] Fang Gensun, Ye Peixin. Computational complexity in worst, stochastic and average case setting on functional approximation problem of multivariate. Acta Mathematica Scientia, 2005, 25B(3): 439--448

[4] Grover L. A framework for fast quantum mechanical algorithms//Proceedings of the 30th Annual ACM Symposium on the Theory of
Computing. New York: ACM Press, 1998: 53--62

[5] Heinrich S. Quantum summation with an application to integration. J Complexity, 2002, 18: 1--50

[6] Heinrich S. Quantum integration in Sobolev classes. J Complexity, 2003, 19: 19--42

[7] Heinrich S. Novak E. On a problem in quantum summation. J Complexity, 2003, 18: 1--18

[8] Heinrich S. Quantum approximation I. Imbeddings of finite-dimensional L_p spaces. J Complexity, 2004, 20: 5--26

[9] Heinrich S. Quantum approximation II. Sobolev imbeddings. J Complexity, 2004, 20: 27--45

[10] Hu Xiaofei, Ye Peixin. Quantum complexity of the integration problem for anisotropic classes. J Comput Math, 2005, 23 (3): 233--246

[11] Luo Junbo, Sun Yongsheng. Optimal recovery and widths of anisotropic Sobolev class of multivariate functions. Adva Math, 1998, 27: 69--77 (in Chinese)

[12] Nikolskii S M. Approximation of Functions of Several Variables and Imbedding Theorems. Berlin: Springer-Verlag, 1975

[13] Novak E. Quantum complexity of integration. J Complexity, 2001, 17: 2--16

[14] Shor P W. Introduction to Quantum Computing Algorithms. Boston: Birkhauser, 1999

[15] Temlyakov V N. Approximation of Periodic Functions. New York: Nova Science, 1993

QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(W_p^r([0, 1]^d)) AND Β(H_p^r([0, 1]^d))

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 10

[1]	Fang Gensun; Long Jingfan. TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS [J]. Acta mathematica scientia,Series B, 2007, 27(4): 790-802.
[2]	FANG Gen-Sun, XIE Pei-Xin. COMPUTATIONAL COMPLEXITY IN WORST, STOCHASTIC AND AVERAGE CASE SETTING ON FUNCTIONAL APPROXIMATION PROBLEM OF MULTIVARIATE [J]. Acta mathematica scientia,Series B, 2005, 25(3): 439-448.
[3]	DU Jin-Yuan. ON QUADRATURE FORMULAE FOR SINGULAR \|INTEGRALS OF ARBITRARY ORDER [J]. Acta mathematica scientia,Series B, 2004, 24(1): 9-27.