dorsal/arxiv
View SchemaOn the Complexity of Searching Maximum of a Function on a Quantum Computer
| Authors | Maciej Gocwin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0507060 |
| URL | https://arxiv.org/abs/quant-ph/0507060 |
Abstract
We deal with a problem of finding maximum of a function from the Holder class on a quantum computer. We show matching lower and upper bounds on the complexity of this problem. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of a discrete sequence. To prove lower bounds we use results for finding logical OR of sequence of bits. We show that quantum computation yields a quadratic speed-up over deterministic and randomized algorithms.
{
"annotation_id": "1f7d0919-5380-4920-9ec7-b05011e73347",
"date_created": "2026-03-02T18:02:17.213000Z",
"date_modified": "2026-03-02T18:02:17.213000Z",
"file_hash": "2e1ca98bacdf0a6fae93d0d2dbc17ba9128072d45cfd41e126f78549de22498e",
"private": false,
"record": {
"abstract": "We deal with a problem of finding maximum of a function from the Holder class\non a quantum computer. We show matching lower and upper bounds on the\ncomplexity of this problem. We prove upper bounds by constructing an algorithm\nthat uses the algorithm for finding maximum of a discrete sequence. To prove\nlower bounds we use results for finding logical OR of sequence of bits. We show\nthat quantum computation yields a quadratic speed-up over deterministic and\nrandomized algorithms.",
"arxiv_id": "quant-ph/0507060",
"authors": [
"Maciej Gocwin"
],
"categories": [
"quant-ph"
],
"title": "On the Complexity of Searching Maximum of a Function on a Quantum Computer",
"url": "https://arxiv.org/abs/quant-ph/0507060"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "45bd82f5-38f3-4c23-b7c4-a3b2a1259567",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}