We study the approximation of functions from anisotropic Sobolev classes b（WpR（[0, 1]d）） and HSlder-Nikolskii classes B（HPr（[0, 1]d）） in the Lq （[0, 1]d） norm with q 〈 p in the quantum model of computation....We study the approximation of functions from anisotropic Sobolev classes b（WpR（[0, 1]d）） and HSlder-Nikolskii classes B（HPr（[0, 1]d）） in the Lq （[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.展开更多
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...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.展开更多
We study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobole...We study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobolev class R（Wpr（[0, 1]d）） （r R＋d）. Then combining this result with our previous one we determine the optimal bound of n-th minimal query error for anisotropic Hblder- Nikolskii class R（H∞r（[0,1]d）） and Sobolev class R（W∞r（[0,1]d））. The results show that for these two types of classes the quantum algorithms give significant speed up over classical deterministic and randomized algorithms.展开更多
基金Supported by the Natural Science Foundation of China(10501026,60675010,10971251)
文摘We study the approximation of functions from anisotropic Sobolev classes b（WpR（[0, 1]d）） and HSlder-Nikolskii classes B（HPr（[0, 1]d）） in the Lq （[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.
基金supported by the National Natural Science Foundation of China (Grant Nos. 10501026, 60675010,10626029 and 60572113)the China Postdoctoral Science Foundation (Grant No. 20070420708)
文摘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 National Natural Science Foundation of China (Grant Nos. 10501026 and 60675010)
文摘We study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobolev class R（Wpr（[0, 1]d）） （r R＋d）. Then combining this result with our previous one we determine the optimal bound of n-th minimal query error for anisotropic Hblder- Nikolskii class R（H∞r（[0,1]d）） and Sobolev class R（W∞r（[0,1]d））. The results show that for these two types of classes the quantum algorithms give significant speed up over classical deterministic and randomized algorithms.
