QUANTUM COMPLEXITY OF THE INTEGRATION PROBLEM FOR ANISOTROPIC CLASSES

• 来源期刊: 计算数学（英文版）
• 关键词: Quantum computation Integration problem Anisotropic classes Complexity
• 年，卷（期）: 2005,（3）
• 页码范围: 233-246
• 页数: 14页
• 语种: 英文

摘要

We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes Wr∞ ([0, 1]d) and Holder Nikolskii classes Hr∞([0, 1]d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor n-1 and over randomized classical methods due to factor n-1/2. Moreover, we give an estimation for optimal query complexity in the class H∧∞ (D) whose smoothness index is the boundary of some complete set in Zd+.