Acta mathematica scientia, Series B >
QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(Wpr([0, 1]d)) AND Β(Hpr([0, 1]d))
Received date: 2006-03-03
Revised date: 2008-10-10
Online published: 2010-09-20
Supported by
Supported by the Natural Science Foundation of China (10501026, 60675010,10971251).
We study the approximation of functions from anisotropic Sobolev classes B(Wpr}([0, 1]d)) and H\"{o}lder-Nikolskii classes B(Hpr}([0, 1]d)) in the Lq([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
YE Pei-Xin , HU Xiao-Fei . QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(Wpr([0, 1]d)) AND Β(Hpr([0, 1]d))[J]. Acta mathematica scientia, Series B, 2010 , 30(5) : 1808 -1818 . DOI: 10.1016/S0252-9602(10)60174-9
[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 Lp 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
/
| 〈 |
|
〉 |