Motivated by the recent progress on quantum integration, we study restricted Monte Carlo integration for anisotropic Hölder-Nikolskii classes. The results show that with c · log2n random bits we have the same optimal order for the n-th minimal Monte Carlo integration error as with arbitrary random numbers.
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 study the approximation of the integration of multivariate functions in the quantum model of computation. Using a new reduction approach we obtain a lower bound of the n-th minimal query error on anisotropic Sobolev classes B(Wpr([0, 1]d)), (r isin R+d). Then combining our previous results we determine the optimal bound of nth minimal query error for anisotropic Holder-Nikolskii class B(Hinfinr([0, 1]d)), (r isin R+d) and Sobolev class B(Wpr([0, 1]d)) (r isin Nd). The results show the quantum algorithms give speed up over classical algorithms.
We estimate the quantum query error of approximation to functions from the anisotropic Sobolev class B(Wpr([0,1]d)) and the Hölder-Nikolskii class B(Hpr([0,1]d)) in the Lq([0,1]d) norm for all 1≤p,q≤∞. It turns out that for the class B(Wpr([0,1]d))(r∈Nd), when p<q, the quantum algorithms can essentially improve the rate of convergence of classical deterministic and randomized algorithms; while for the class B(Hpr([0,1]d)) and B(Wpr([0,1]d))(r∈R+d), when p≥q, the optimal convergence rate is the same for all three settings.