Convergence rate of quantum algorithm for multivariate approximation
Jingfan Long, Sheng Zhang, Peixin Ye · 2010 Sixth International Conference on Natural Computation · 2010
We estimate the convergence rate of quantum algorithm for approximation from some smooth functions in the Lq([0, 1]d) norm for 1 ≤ q ≤ ∞. It turns out that for the Sobolev class B(Wpr([0, 1]d)) (r ∈ ℕd), when p <; q, the quantum algorithms can bring speedup over classical deterministic and randomized algorithms.