This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B(Wrp([0, 1]d)) in the deterministic, randomized and average case settings, and obtains the exact orders of the n-th minimal error of these problems in all three settings. The results show that in the case of B(Wrp([0, 1]d)) being not imbedded into the space of continuous functions C([0, 1]d), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor n-1+ε for any ε > 0, and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.
We obtain the optimal order of high-dimensional integration complexity in the quantum computation model in anisotropic Sobolev classes
W∞r([0,1]d) and Hölder Nikolskii classes
H∞r([0,1]d). It is proved that for these classes of functions there is a speed-up of quantum algorithms over deterministic classical algorithms due to factor
n−1 and over randomized classical methods due to factor
n−1/2. Moreover, we give an estimation for optimal query complexity in the class
H∞Λ(D) whose smoothness index is the boundary of some complete set in
Z+d.
We are concerned with the numerical integration of functions from the Sobolev space
Hr,mix([0,1]d) of dominating mixed smoothness
r∈N over the
d-dimensional unit cube. In 1976, K. K. Frolov introduced a deterministic quadrature rule whose worst case error has the order
n−r(logn)(d−1)/2 with respect to the number
n of function evaluations. This is known to be optimal. 39 years later, Erich Novak and me introduced a randomized version of this algorithm using
d random dilations. We showed that its error is bounded above by a constant multiple of
n−r−1/2(logn)(d−1)/2 in expectation and by
n−r(logn)(d−1)/2 almost surely. The main term
n−r−1/2 is again optimal and it turns out that the very same algorithm is also optimal for the isotropic Sobolev space
Hs([0,1]d) of smoothness
s>d/2. We also added a random shift to this algorithm to make it unbiased. Just recently, Mario Ullrich proved that the expected error of the resulting algorithm on
Hr,mix([0,1]d) is even bounded above by
n−r−1/2. This thesis is a review of the mentioned upper bounds and their proofs.
The Feynman-Kac path integration problem was studied in the worst case setting by Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case and by Kwas and Li (J. Comp. 19 (2003) 730) for the multivariate case with d space variables. In this paper we consider the multivariate Feynman-Kac path integration problem in the randomized and quantum settings. For smooth multivariate functions, it was proven in Kwas and Li (2003) that the classical worst case complexity suffers from the curse of dimensionality in d. We show that in both the randomized and quantum settings the curse of dimensionality is vanquished, i.e., the number of function evaluations and/or quantum queries required to compute an e-approximation has a bound independent of d and depending polynomially on 1/e. The exponents of these polynomials are at most 2 in the randomized setting and at most 1 in the quantum setting. Hence we have exponential speedup over the classical worst case setting and quadratic speedup of the quantum setting over the randomized setting. However, both the randomized and quantum algorithms presented here still require extensive precomputing, similar to the algorithms of Plaskota et al. (2000) and Kwas and Li(2003).