Complexity for the Approximation of Sobolev Imbeddings in the Quantum Computation Model

摘要：

Using a new and elegant reduction approach we derive a lower bound of quantum complexity for the approximation of imbeddings from anisotropic Sobolev classes B(Wrp(0, 1d)) to anisotropic Sobolev space Wsq(0, 1d) for all 1 ≤p,q ≤ ∞.When p≥q this bound is optimal. In this case the quantum algorithms are not signicantly better than the classical deterministic or randomized algorithms. When p≥q we conjecture that quantum algorithms bring speed-up over the classical deterministic and randomized ones. This conjecture was conrmed in the situation s=0.

作者: LONG Jingfan YE Peixin YUAN Xiuhua

作者单位: Beijing Information Science and Technology University, Beijing 100101, P.R.China Beijing Information Science and Technology University, Beijing 100101, P.R.China School of Mathemati School of Mathematics and LPMC, Nankai University, Tianjin 300071, P.R.China

会议类型: 国际会议

会议名称: The 30th Chinese Control Conference(第三十届中国控制会议)

会议地点: 烟台

会议语种:英文

页码: 1-5

在线出版日期: 2011-07-01（万方平台首次上网日期，不代表论文的发表时间）