Complexity for the approximation of Sobolev imbeddings in the quantum computation model

Using a new and elegant reduction approach we derive a lower bound of quantum complexity for the approximation of imbeddings from anisotropic Sobolev classes B(W_p^r([0, 1]^d)) to anisotropic Sobolev space W_p^s([0, 1]^d) for all 1 ≤ p, q ≤ ∞. When p ≥ q this bound is optimal. In this case the quantum algorithms are not significantly better than the classical deterministic or randomized algorithms. When p ≥ q we conjecture that quantum algorithms bring speed-up over the classical deterministic and randomized ones. This conjecture was confirmed in the situation s = 0.