dorsal/arxiv
View SchemaA New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
| Authors | Andris Ambainis, Robert Spalek, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511200 |
| URL | https://arxiv.org/abs/quant-ph/0511200 |
Abstract
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
{
"annotation_id": "d16083bb-74de-4121-bd3d-327537c648e8",
"date_created": "2026-03-02T18:02:22.880000Z",
"date_modified": "2026-03-02T18:02:22.880000Z",
"file_hash": "4784cd95e867070d3ae8334185632e17eb09af922ce7b20ffea8cf9c9786c99f",
"private": false,
"record": {
"abstract": "We give a new version of the adversary method for proving lower bounds on\nquantum query algorithms. The new method is based on analyzing the eigenspace\nstructure of the problem at hand. We use it to prove a new and optimal strong\ndirect product theorem for 2-sided error quantum algorithms computing k\nindependent instances of a symmetric Boolean function: if the algorithm uses\nsignificantly less than k times the number of queries needed for one instance\nof the function, then its success probability is exponentially small in k. We\nalso use the polynomial method to prove a direct product theorem for 1-sided\nerror algorithms for k threshold functions with a stronger bound on the success\nprobability. Finally, we present a quantum algorithm for evaluating solutions\nto systems of linear inequalities, and use our direct product theorems to show\nthat the time-space tradeoff of this algorithm is close to optimal.",
"arxiv_id": "quant-ph/0511200",
"authors": [
"Andris Ambainis",
"Robert Spalek",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs",
"url": "https://arxiv.org/abs/quant-ph/0511200"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b28ed3ea-c4a6-49ba-97b5-d159579ccb29",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}