dorsal/arxiv
View SchemaOptimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms
| Authors | S. Heinrich, E. Novak |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0105114 |
| URL | https://arxiv.org/abs/quant-ph/0105114 |
Abstract
We survey old and new results about optimal algorithms for summation of finite sequences and for integration of functions from Hoelder or Sobolev spaces. First we discuss optimal deterministic and randomized 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. We observe that -- there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if k/d tends to zero; -- there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical algorithms, if k/d is small.
{
"annotation_id": "371c7411-53a1-4dad-8758-566377dd52ec",
"date_created": "2026-03-02T18:01:45.269000Z",
"date_modified": "2026-03-02T18:01:45.269000Z",
"file_hash": "60bc61538dd4ae24c140fcc583bc0bc46ee90fbb9dcf442a700d9572c9a94c73",
"private": false,
"record": {
"abstract": "We survey old and new results about optimal algorithms for summation of\nfinite sequences and for integration of functions from Hoelder or Sobolev\nspaces. First we discuss optimal deterministic and randomized algorithms. Then\nwe add a new aspect, which has not been covered before on conferences about\n(quasi-) Monte Carlo methods: quantum computation. We give a short introduction\ninto this setting and present recent results of the authors on optimal quantum\nalgorithms for summation and integration. We discuss comparisons between the\nthree settings. The most interesting case for Monte Carlo and quantum\nintegration is that of moderate smoothness k and large dimension d which, in\nfact, occurs in a number of important applied problems. In that case the\ndeterministic exponent is negligible, so the n^{-1/2} Monte Carlo and the\nn^{-1} quantum speedup essentially constitute the entire convergence rate. We\nobserve that -- there is an exponential speed-up of quantum algorithms over\ndeterministic (classical) algorithms, if k/d tends to zero; -- there is a\n(roughly) quadratic speed-up of quantum algorithms over randomized classical\nalgorithms, if k/d is small.",
"arxiv_id": "quant-ph/0105114",
"authors": [
"S. Heinrich",
"E. Novak"
],
"categories": [
"quant-ph",
"math.NA"
],
"title": "Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0105114"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "45928b5b-0b26-4437-a17b-cb0b93e5c00f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}