Sobolev Approximation 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 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 algorithms.