Acta mathematica scientia, Series B >
QUANTUM COMPLEXITY OF SOBOLEV IMBEDDINGS
Received date: 2010-08-27
Revised date: 2010-12-09
Online 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, q ≤∞. 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
XIE Pei-Xin . QUANTUM COMPLEXITY OF SOBOLEV IMBEDDINGS[J]. Acta mathematica scientia, Series B, 2012 , 32(3) : 1102 -1114 . DOI: 10.1016/S0252-9602(12)60083-6
[1] Fang Gensun, Ye Peixin. Computational complexity in worst, stochastic and average case setting on functional approximation problem of multi-variate. Acta Mathematica Scientia, 2005,25B(3): 439–448
[2] Fang Gensun, Hickernell F J, Li Huan. Approximation on anisotropic Besov classes with mixed norm by standarded information. J Complexity, 2005, 21: 294–313
[3] Fang Gensun, Long Jingfan. Tractability of multivariate integration problem for periodic continuous functions. Acta Mathematica Scientia, 2007, 27B(4): 790–802
[4] Fang Gensun, Duan Liqin. The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods. J Complexity, 2008, 24: 398–409
[5] Heinrich S. Quantum approximation I. Imbeddings of finite-dimensional Lp spaces. J Complexity, 2004, 20: 5–26
[6] Heinrich S. Quantum approximation II. Sobolev imbeddings. J Complexity, 2004, 20: 27–45
[7] Heinrich S. The quantum query complexity of elliptic PDE. J Complexity, 2006, 22: 691–725
[8] Heinrich S. Numerical Analysis on a Quantum Computer//Lecture Notes in Computer Science 3743, 28–39. Berlin: Springer-Verlag, 2006
[9] Heinrich S. Quantum lower bounds by entropy numbers. J Complexity, 2007, 23: 793–801
[10] Heinrich S. Randomized approximation of Sobolev imbeddings//Keller A, Heinrich S, Niederreiter H. Monte Carlo and Quasi-Monte Carlo 2006. Springer–Verlag, 2008: 445–459
[11] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2000
[12] Nikolskii S M. Approximation of Functions of Several Variables and Imbedding Theorems. Springer-Verlag, 1975
[13] Song Zhanjie, Ye Peixin. Optimal query error of quantum approximation on some Sobolev classes. Science in China, 2008, 51A(9): 1561–1752
[14] Ye Peixin, Hu Xiaofei. Quantum complexity of the approximation for the classes B(Wrp ([0, 1]d)) and B(Hrp([0, 1]d)). Acta Mathematica Scientia, 2010, 30B(5): 1808–1818
/
| 〈 |
|
〉 |