dorsal/arxiv
View SchemaA fast quantum mechanical algorithm for estimating the median
| Authors | Lov K. Grover |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9607024 |
| URL | https://arxiv.org/abs/quant-ph/9607024 |
Abstract
Consider the problem of estimating the median of N items to a precision epsilon, i.e., the estimate should be such that, with a high probability, the number of items, with values both smaller than and larger than this estimate, is less than N*(1+epsilon)/2. Any classical algorithm to do this will need at least O(1/epsilon^2) samples. Quantum mechanical systems can simultaneously carry out multiple computations due to their wave like properties. This paper describes an O(1/epsilon) step algorithm for the above estimation.
{
"annotation_id": "597e6105-812c-479a-a564-918e7e3ab4bc",
"date_created": "2026-03-02T18:02:37.967000Z",
"date_modified": "2026-03-02T18:02:37.967000Z",
"file_hash": "ea7c0d755bfada3517a5dc79c78ceba06abe41898901e247b408bd99a2edca66",
"private": false,
"record": {
"abstract": "Consider the problem of estimating the median of N items to a precision\nepsilon, i.e., the estimate should be such that, with a high probability, the\nnumber of items, with values both smaller than and larger than this estimate,\nis less than N*(1+epsilon)/2. Any classical algorithm to do this will need at\nleast O(1/epsilon^2) samples. Quantum mechanical systems can simultaneously\ncarry out multiple computations due to their wave like properties. This paper\ndescribes an O(1/epsilon) step algorithm for the above estimation.",
"arxiv_id": "quant-ph/9607024",
"authors": [
"Lov K. Grover"
],
"categories": [
"quant-ph"
],
"title": "A fast quantum mechanical algorithm for estimating the median",
"url": "https://arxiv.org/abs/quant-ph/9607024"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1dd5ba9d-330c-46a6-9718-5f414b1ebb26",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}