Optimal query error of quantum approximation on some Sobolev classes

• 来源期刊: 中国科学A辑(英文版)
• 年，卷（期）: 2008,（9）
• 页码范围: 1664-1678
• 页数: 15页
• 语种: 英文
• DOI: 10.1007/s11425-008-0077-0

摘要

We study the approximation of the imbedding of functions from anisotropic and generalized Sobolev classes into Lq([0,1]d)space in the quantum model of computation.Based on the quantum algorithms for approximation of finite imbedding from LNp to LNp,we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes (B)(WTp([0,1]d))to Lq([0,1]d)space for all 1≤q,p≤∞ and prove their optimality.Our results show that for p＜q the quantum model of computation can bring a speedup roughly up to a squaring of the rate in the classical deterministic and randomized settings.