Optimal query error of quantum approximation on some Sobolev classes

作     者：SONG ZhanJie YE PeiXin 

作者机构：School of SciencesTianjin UniversityTianjin 300072China School of Mathematical Sciences and LPMCNankai UniversityTianjin 300071China School of Electronic Information EngineeringTianjin UniversityTianjin 300072China 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2008年第51卷第9期

页      面：1664-1678页

核心收录：

学科分类：07[理学] 070102[理学-计算数学] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China (Grant Nos. 10501026, 60675010,10626029 and 60572113) the China Postdoctoral Science Foundation (Grant No. 20070420708) 

主　　题：quantum approximation Sobolev classes n-th minimal query error 41A63 65D15 

摘      要：We study the approximation of the imbedding of functions from anisotropic and generalized Sobolev classes into L q ([0, 1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from L p N to L q N , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(W p r ([0, 1] d )) to L q ([0, 1] d ) space for all 1 ? q,p ? ∞ and prove their optimality. Our results show that for p q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.