Quantum Approximation Error on Some Sobolev Classes

We study the approximation of functions from anisotropic and generalized Sobolev classes under L_q([0, 1]d) norm in the quantum model of computation. Based on the quantum algorithm for approximation of finite imbedding from L^N _P to Li^N _Q, we develop a quantum algorithm for approximating the imbedding from anisotropic Sobolev classes B(W_p ^r(|0, 1|^d)) to Lq(|0, 1|^d) space for all 1 les q,p les infin and prove their optimality. Our results show that for p < q the quantum model of computation can bring a speedup of roughly squaring the rate of classical deterministic and randomized settings.