Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4664176 | Acta Mathematica Scientia | 2010 | 11 Pages |
Abstract
We study the approximation of functions from anisotropic Sobolev classes B(Wrp([0,1]d)) and Hölder-Nikolskii classes B(Hrp([0,1]d)) in the Lq([0,1]d) norm with q ≤ p in the quantum model of computation. We determine the quantum query complexity of this problem up to logarithmic factors. It shows that the quantum algorithms are significantly better than the classical deterministic or randomized algorithms.
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)