dorsal/arxiv
View SchemaSearching an Ordered List on a Quantum Computer
| Authors | Hein Roehrig |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812061 |
| URL | https://arxiv.org/abs/quant-ph/9812061 |
Abstract
Withdrawn by the author due to irreparable errors. We present a quantum algorithm that in the black-box model performs a search in an ordered list of N elements. Using 3/4 log N + O(1) queries, it achieves a success probability of at least 1/2, whereas classically, log N - O(1) queries are needed to obtain constant success probability. Moreover, our algorithm employs the Haar transform and thus differs substantially from Grover's search algorithm and from algorithms relying on the quantum Fourier transform.
{
"annotation_id": "ab282baf-a49e-407a-bca1-60aac0ebd699",
"date_created": "2026-03-02T18:02:44.965000Z",
"date_modified": "2026-03-02T18:02:44.965000Z",
"file_hash": "e756ca0361066d08f188a228fceee58cd1a8f9bc136e327df0d90d7caf1245ea",
"private": false,
"record": {
"abstract": "Withdrawn by the author due to irreparable errors.\n We present a quantum algorithm that in the black-box model performs a search\nin an ordered list of N elements. Using 3/4 log N + O(1) queries, it achieves a\nsuccess probability of at least 1/2, whereas classically, log N - O(1) queries\nare needed to obtain constant success probability. Moreover, our algorithm\nemploys the Haar transform and thus differs substantially from Grover\u0027s search\nalgorithm and from algorithms relying on the quantum Fourier transform.",
"arxiv_id": "quant-ph/9812061",
"authors": [
"Hein Roehrig"
],
"categories": [
"quant-ph"
],
"title": "Searching an Ordered List on a Quantum Computer",
"url": "https://arxiv.org/abs/quant-ph/9812061"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4d784130-1e99-4d9c-b305-13e9f7d8a8a7",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}