dorsal/arxiv
View SchemaFast quantum algorithms for numerical integrals and stochastic processes
| Authors | Daniel S. Abrams, Colin P. Williams |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9908083 |
| URL | https://arxiv.org/abs/quant-ph/9908083 |
Abstract
We discuss quantum algorithms that calculate numerical integrals and descriptive statistics of stochastic processes. With either of two distinct approaches, one obtains an exponential speed increase in comparison to the fastest known classical deterministic algorithms and a quadratic speed increase in comparison to classical Monte Carlo (probabilistic) methods. We derive a simpler and slightly faster version of Grover's mean algorithm, demonstrate how to apply quantum counting to the problem, develop some variations of these algorithms, and show how both (apparently quite different) approaches can be understood from the same unified framework. Finally, we discuss how the exponential speed increase appears to (but does not) violate results obtained via the method of polynomials, from which it is known that a bounded-error quantum algorithm for computing a total function can be only polynomially more efficient than the fastest deterministic classical algorithm.
{
"annotation_id": "6ad4ddfd-a26a-4ffb-8f0c-c3b1f24b4189",
"date_created": "2026-03-02T18:02:48.457000Z",
"date_modified": "2026-03-02T18:02:48.457000Z",
"file_hash": "80c2b4875fbb4c695c9f526b9801e2967f1e5bec8d6525fb7cabd1b62f247ece",
"private": false,
"record": {
"abstract": "We discuss quantum algorithms that calculate numerical integrals and\ndescriptive statistics of stochastic processes. With either of two distinct\napproaches, one obtains an exponential speed increase in comparison to the\nfastest known classical deterministic algorithms and a quadratic speed increase\nin comparison to classical Monte Carlo (probabilistic) methods. We derive a\nsimpler and slightly faster version of Grover\u0027s mean algorithm, demonstrate how\nto apply quantum counting to the problem, develop some variations of these\nalgorithms, and show how both (apparently quite different) approaches can be\nunderstood from the same unified framework. Finally, we discuss how the\nexponential speed increase appears to (but does not) violate results obtained\nvia the method of polynomials, from which it is known that a bounded-error\nquantum algorithm for computing a total function can be only polynomially more\nefficient than the fastest deterministic classical algorithm.",
"arxiv_id": "quant-ph/9908083",
"authors": [
"Daniel S. Abrams",
"Colin P. Williams"
],
"categories": [
"quant-ph"
],
"title": "Fast quantum algorithms for numerical integrals and stochastic processes",
"url": "https://arxiv.org/abs/quant-ph/9908083"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8ed8975f-f451-4f68-acc9-cfed50d94a3c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}