QUANTUM APPROXIMATION ON ANISOTROPIC SOBOLEV AND HÖLDER-NIKOLSKII CLASSES

Abstract

We estimate the quantum query error of approximation to functions from the anisotropic Sobolev class ${\cal B}(W_p^{\bf r}([0,1]^d))$ and the Hölder-Nikolskii class ${\cal B}(H_p^{\bf r}([0,1]^d))$ in the $L_q([0,1]^d)$ norm for all $1 \leq p,q \leq \infty$. It turns out that for the class ${\cal B}(W_p^{\bf r}([0,1]^d))$ $({\bf r}\in {\mathbb{N}^d})$, when $p \lt q$, the quantum algorithms can essentially improve the rate of convergence of classical deterministic and randomized algorithms; while for the class ${\cal B}(H_p^{\bf r}([0,1]^d))$ and ${\cal B}(W_p^{\bf r}([0,1]^d))$ $({\bf r}\in {\mathbb{R}_+^d})$, when $p \geq q$, the optimal convergence rate is the same for all three settings.