Quantum complexity of sobolev imbeddings

Using a new reduction approach, we derive a lower bound of quantum complexity for the approximation of imbeddings from anisotropic Sobolev classes to anisotropic Sobolev space for all 1≤p,q≤∞. When p ≥ q, we show this bound is optimal by deriving the matching upper bound. In this case, the quantum algorithms are not significantly better than the classical deterministic or randomized ones. We conjecture that the bound is also optimal for the case p < q. This conjecture was confirmed in the situation s = 0.