Optimal query error of quantum approximation on some Sobolev classes  

作　　者：SONG ZhanJie YE PeiXin 

机构地区：[1]School of Sciences,Tianjin University,Tianjin 300072,China [2]School of Mathematical Sciences and LPMC,Nankai University,Tianjin 300071,China [3]School of Electronic Information Engineering,Tianjin University,Tianjin 300072,China

出　　处：《Science China Mathematics》2008年第9期1664-1678,共15页中国科学：数学（英文版）

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

摘　　要：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.We study the approximation of the imbedding of functions from anisotropic and general-ized Sobolev classes into Lq([0,1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr ([0,1]d)) to Lq([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.

关 键 词：quantum approximation Sobolev classes n-th minimal query error 41A63 65D15 

分 类 号：O241[理学—计算数学]