Quantum integration in Besov spaces with mixed smoothness

Abstract

We study the complexity of high-dimensional integration of periodic functions from Besov spaces $S_{p,q}^{r}B({\mathbb{T}}^d)$ with mixed smoothness in the quantum model of computation. We construct new quantum algorithms based on the multivariate Faber-Schauder decomposition of such functions and analyze their convergence rates. We show a gain of one convergence order compared to the well-known deterministic rates of convergence. We additionally obtain lower bounds showing the optimality of our results up to logarithms.

arXiv comment23 pages, 2 figures