数学物理学报(英文版) ›› 2012, Vol. 32 ›› Issue (3): 1102-1114.doi: 10.1016/S0252-9602(12)60083-6

• 论文 • 上一篇    下一篇

QUANTUM COMPLEXITY OF SOBOLEV IMBEDDINGS

叶培新   

  1. School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
  • 收稿日期:2010-08-27 修回日期:2010-12-09 出版日期:2012-05-20 发布日期:2012-05-20
  • 基金资助:

    Supported by the Natural Science Foundation of China (10971251).

QUANTUM COMPLEXITY OF SOBOLEV IMBEDDINGS

 XIE Pei-Xin   

  1. School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
  • Received:2010-08-27 Revised:2010-12-09 Online:2012-05-20 Published:2012-05-20
  • Supported by:

    Supported by the Natural Science Foundation of China (10971251).

摘要:

Using a new reduction approach, we derive a lower bound of quantum com-plexity for the approximation of imbeddings from anisotropic Sobolev classes B(Wrp ([0, 1]d)) to anisotropic Sobolev space Wsq ([0, 1]d) for all 1 ≤ p, ≤∞. When p q, we show this bound is optimal by deriving the matching upper bound. In this case, the quantum al-gorithms are not significantly better than the classical deterministic or randomized ones. We conjecture that the bound is also optimal for the case p < q. This conjecture was confirmed in the situation s = 0.

关键词: Sobolev imbeddings, quantum computation, n-th minimal error

Abstract:

Using a new reduction approach, we derive a lower bound of quantum com-plexity for the approximation of imbeddings from anisotropic Sobolev classes B(Wrp ([0, 1]d)) to anisotropic Sobolev space Wsq ([0, 1]d) for all 1 ≤ p, ≤∞. When p q, we show this bound is optimal by deriving the matching upper bound. In this case, the quantum al-gorithms are not significantly better than the classical deterministic or randomized ones. We conjecture that the bound is also optimal for the case p < q. This conjecture was confirmed in the

Key words: Sobolev imbeddings, quantum computation, n-th minimal error