dorsal/arxiv
View SchemaQuantum lower bounds by quantum arguments
| Authors | Andris Ambainis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0002066 |
| URL | https://arxiv.org/abs/quant-ph/0002066 |
Abstract
We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $\Omega(\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.
{
"annotation_id": "5a3f4b64-6e31-4788-a032-1eba212f9e8c",
"date_created": "2026-03-02T18:01:37.942000Z",
"date_modified": "2026-03-02T18:01:37.942000Z",
"file_hash": "0eadb41a5932ac116b5bef167bd097f8366bb8f03c103541f5c5fa6bac006689",
"private": false,
"record": {
"abstract": "We propose a new method for proving lower bounds on quantum query algorithms.\nInstead of a classical adversary that runs the algorithm with one input and\nthen modifies the input, we use a quantum adversary that runs the algorithm\nwith a superposition of inputs. If the algorithm works correctly, its state\nbecomes entangled with the superposition over inputs. We bound the number of\nqueries needed to achieve a sufficient entanglement and this implies a lower\nbound on the number of queries for the computation.\n Using this method, we prove two new $\\Omega(\\sqrt{N})$ lower bounds on\ncomputing AND of ORs and inverting a permutation and also provide more uniform\nproofs for several known lower bounds which have been previously proven via\nvariety of different techniques.",
"arxiv_id": "quant-ph/0002066",
"authors": [
"Andris Ambainis"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum lower bounds by quantum arguments",
"url": "https://arxiv.org/abs/quant-ph/0002066"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ef1b3a7a-8d1d-43c8-93e0-55c5aca084d0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}