摘要
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.
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.
基金
supported by the National Natural Science Foundation of China (Grant Nos. 10501026, 60675010,10626029 and 60572113)
the China Postdoctoral Science Foundation (Grant No. 20070420708)
