Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms

  • 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.

Metadaten exportieren

  • Export nach Bibtex
  • Export nach RIS

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Stefan Heinrich, Erich Novak
URN (Permalink):urn:nbn:de:hbz:386-kluedo-50305
Schriftenreihe (Bandnummer):Interner Bericht des Fachbereich Informatik (313)
Dokumentart:Bericht
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):06.11.2017
Jahr der Veröffentlichung:2001
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):06.11.2017
Seitenzahl:15
Fachbereiche / Organisatorische Einheiten:Fachbereich Informatik
DDC-Sachgruppen:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung, nicht kommerziell, keine Bearbeitung (CC BY-NC-ND 4.0)

$Rev: 13581 $