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 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.展开更多
基金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.