Acta mathematica scientia,Series B ›› 2012, Vol. 32 ›› Issue (3): 1102-1114.doi: 10.1016/S0252-9602(12)60083-6

• Articles • Previous Articles     Next Articles

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).

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

Trendmd