Quantum Complexity of the Approximation on the Classes B(Wrp([0, 1]d)) and B(Hrp([0, 1]d))

The optimal order of complexity of the approximation of the imbedding from anisotropic Sobolev classes B(W_p ^r ([0, 1]^d)) and Holder Nikolskii classes B(H_p ^r([0, 1]^d)) into the L_q([0, 1]d) with q les p quantum computation model is obtained up to logarithmic factors. It shows that the quantum algorithms are not significantly better than the classical ones for this type of problems.