QUANTUMCOMPLEXITYOFTHEAPPROXIMATIONFORTHECLASSESB(Wpr（[0,1]d）)ANDB(Hpr（[0,1]d）)

被引：1

作者：

叶培新 ^{[1
]}

胡晓菲 ^{[2
]}

机构：

[1] School of Mathematical Sciences and LPMC,Nankai University

[2] College of Mathematical,Syracuse University

来源：

Acta Mathematica Scientia | 2010年 / 30卷 / 05期

关键词：

quantum approximation; anisotropic classes; minimal query error;

D O I：

暂无

中图分类号：

O413 [量子论]; O174.41 [逼近论];

学科分类号：

070201 ; 070104 ;

摘要：

We study the approximation of functions from anisotropic Sobolev classes B(Wpr（[0,1]d）) and H¨older-Nikolskii classes B(Wpr（[0,1]d）) in the L q（[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.

引用

页码：1808 / 1818

页数：11

共 6 条

[1] COMPUTATIONAL COMPLEXITY IN WORST, STOCHASTIC AND AVERAGE CASE SETTING ON FUNCTIONAL APPROXIMATION PROBLEM OF MULTIVARIATE [J].