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

数学物理学报(英文版) ›› 2010, Vol. 30 ›› Issue (5): 1808-1818.doi: 10.1016/S0252-9602(10)60174-9

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

叶培新, 胡晓菲

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

收稿日期:2006-03-03 修回日期:2008-10-10 出版日期:2010-09-20 发布日期:2010-09-20
基金资助:
Supported by the Natural Science Foundation of China (10501026, 60675010,10971251).

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

摘要：

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.

关键词: quantum approximation, anisotropic classes, minimal query error

Abstract:

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

中图分类号:

41A55

叶培新, 胡晓菲. QUANTUM COMPLEXITY OF THE APPROXIMATION FOR THE CLASSES Β(W_p^r([0, 1]^d)) AND Β(H_p^r([0, 1]^d))[J]. 数学物理学报(英文版), 2010, 30(5): 1808-1818.

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.

参考文献

[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))

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	房艮孙; 龙晶凡. TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS[J]. 数学物理学报(英文版), 2007, 27(4): 790-802.
[2]	房艮孙,叶陪新. COMPUTATIONAL COMPLEXITY IN WORST, STOCHASTIC AND AVERAGE CASE SETTING ON FUNCTIONAL APPROXIMATION PROBLEM OF MULTIVARIATE[J]. 数学物理学报(英文版), 2005, 25(3): 439-448.
[3]	杜金元. ON QUADRATURE FORMULAE FOR SINGULAR \|INTEGRALS OF ARBITRARY ORDER[J]. 数学物理学报(英文版), 2004, 24(1): 9-27.