{
  "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
}