Quantum Approximation Error on Some Sobolev Classes
Peixin Ye · 2007
We study the approximation of functions from anisotropic and generalized Sobolev classes under Lq([0, 1]d) norm in the quantum model of computation. Based on the quantum algorithm for approximation of finite imbedding from LNPto LiNQ, we develop a quantum algorithm for approximating the imbedding from anisotropic Sobolev classes B(Wpr(|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.