| Optimal query error of quantum approximation on some Sobolev classes |
| |
| 摘 要： | We study the approximation of the imbedding of functions from anisotropic and general-ized 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 LpN to LNq , we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(Wpr (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.
|
Optimal query error of quantum approximation on some Sobolev classes |
| |
| Authors: | ZhanJie Song and PeiXin Ye |
| |
| Institution: | (1) School of Sciences, Tianjin University, Tianjin, 300072, China;(2) School of Mathematical Sciences and LPMC, Nankai University, Tianjin, 300071, China;(3) School of Electronic Information Engineering, Tianjin University, Tianjin, 300072, China |
| |
| Abstract: | We study the approximation of the imbedding of functions from anisotropic and generalized Sobolev classes into L
q
(0, 1]d) space in the quantum model of computation. Based on the quantum algorithms for approximation of finite imbedding from L
p
N
to L
q
N
, we develop quantum algorithms for approximating the imbedding from anisotropic Sobolev classes B(W
p
r
(0, 1]
d
)) to L
q
(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.
This work was supported by the National Natural Science Foundation of China (Grant Nos. 10501026, 60675010, 10626029 and 60572113)
and the China Postdoctoral Science Foundation (Grant No. 20070420708) |
| |
| Keywords: | quantum approximation Sobolev classes n-th minimal query error |
| 本文献已被 SpringerLink 等数据库收录！ |
|
