We prove lower bounds for the error of optimal cubature formulas for
d-variate functions from Besov spaces of mixed smoothness
Bp,θα(Gd) in the case
01/p, and upper bounds for QMC methods on the Fibonacci lattice for two-variate periodic functions from
Bp,θα(G2) in the case
1≤p≤∞,
01/p, where
Gd is either the
d-dimensional torus
Td or the
d-dimensional cube
[0,1]d. In combination these results yield the correct asymptotic of the error of optimal cubature formulas for functions from
Bp,θα(G2) and indicate that a corresponding results is most likely also true in case
d>2. This is compared to the obtained correct asymptotic of optimal cubature formulas on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.
We study the complexity of high-dimensional integration of periodic functions from Besov spaces
Sp,qrB(Td) 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.