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

作　　者：叶培新 胡晓菲 

机构地区：[1]School of Mathematical Sciences and LPMC,Nankai University [2]College of Mathematical,Syracuse University

出　　处：《Acta Mathematica Scientia》2010年第5期1808-1818,共11页数学物理学报（B辑英文版）

基　　金：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 HSlder-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.We study the approximation of functions from anisotropic Sobolev classes b（WpR（[0, 1]d）） and HSlder-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.

关 键 词：quantum approximation anisotropic classes minimal query error 

分 类 号：O413[理学—理论物理] O174.41[理学—物理]