Quantum complexity of the approximation for the classes B(Wrp ([0, 1]d)) and B(Hrp ([0, 1]d))

We study the approximation of functions from anisotropic Sobolev classes B(Wrp([0,1]d)) and Hölder-Nikolskii classes B(Hrp([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.