TY - RPRT
A1 - Heinrich, Stefan
A1 - Novak, Erich
T1 - Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms
N2 - We survey old and new results about optimal algorithms for summation of finite sequences and for integration of functions from HÃ¶lder or Sobolev spaces. First we discuss optimal deterministic and randornized algorithms. Then we add a new aspect, which has not been covered before on conferences
about (quasi-) Monte Carlo methods: quantum computation. We give a short introduction into this setting and present recent results of the authors on optimal quantum algorithms for summation and integration. We discuss comparisons between the three settings. The most interesting case for Monte
Carlo and quantum integration is that of moderate smoothness \(k\) and large dimension \(d\) which, in fact, occurs in a number of important applied problems. In that case the deterministic exponent is negligible, so the \(n^{-1/2}\) Monte Carlo and the \(n^{-1}\) quantum speedup essentially constitute the entire convergence rate.
T3 - Interner Bericht des Fachbereich Informatik - 313
Y1 - 2001
UR - https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/5030
UR - https://nbn-resolving.org/urn:nbn:de:hbz:386-kluedo-50305
ER -