dorsal/arxiv
View SchemaLower Bounds for Quantum Search and Derandomization
| Authors | Harry Buhrman, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9811046 |
| URL | https://arxiv.org/abs/quant-ph/9811046 |
Abstract
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.
{
"annotation_id": "a4c8621a-6f48-44a4-acd5-1d1006dbe8dd",
"date_created": "2026-03-02T18:02:45.083000Z",
"date_modified": "2026-03-02T18:02:45.083000Z",
"file_hash": "ceb58e71614aca390673018e3be15f4242db63f3026133ede1f47285e933490b",
"private": false,
"record": {
"abstract": "We prove lower bounds on the error probability of a quantum algorithm for\nsearching through an unordered list of N items, as a function of the number T\nof queries it makes. In particular, if T=O(sqrt{N}) then the error is lower\nbounded by a constant. If we want error \u003c1/2^N then we need T=Omega(N) queries.\nWe apply this to show that a quantum computer cannot do much better than a\nclassical computer when amplifying the success probability of an RP-machine. A\nclassical computer can achieve error \u003c=1/2^k using k applications of the\nRP-machine, a quantum computer still needs at least ck applications for this\n(when treating the machine as a black-box), where c\u003e0 is a constant independent\nof k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N)\nqueries for quantum bounded-error search of an ordered list of N items.",
"arxiv_id": "quant-ph/9811046",
"authors": [
"Harry Buhrman",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Lower Bounds for Quantum Search and Derandomization",
"url": "https://arxiv.org/abs/quant-ph/9811046"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6a2de6ac-461b-4fbb-a7c9-6da23b289663",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}