Information-Based Complexity of Integration in the Randomized and Quantum Computation Model

In this paper, we investigate the integration of the Holder-Nikolskii classes in the randomized and quantum computation model. We develop randomized and quantum algorithms for integration of functions from this class and analyze their convergence rates. Comparing our result with the convergence rates in the deterministic setting, we see that quantum computing can reach an exponential speedup over deterministic classical computation and a quadratic speedup over randomized classical computation.