Quantum Approximation on Some Classes of Multivarite Functions

We study the quantum query error of approximation of functions from anisotropic Sobolev class B(W_p ^r([0, 1]^d)) and Holder-Nikolskii class B(H_p ^r([0, 1]^d)) in the L_q([0, 1]^d) norm for all 1 les p, q les infin. The results show that for the class B(W_p ^r([0, 1]^d)) (r isin N^d) when p < q the quantum algorithms can essentially improve the rate of convergence of classical deterministic and randomized algorithms, while for the class B(H_p ^r([0, 1]^d)) and B(W_p ^r([0, 1]^d)) (r isin R₊ ^d) when p ges q the optimal convergence rate is the same for all three settings.