{
  "annotation_id": "c48c9161-6d4c-4499-8779-98f4a5ebc83c",
  "date_created": "2026-03-02T18:02:37.247000Z",
  "date_modified": "2026-03-02T18:02:37.247000Z",
  "file_hash": "b1fb5dcb0b750037b8f44a1d9c1172945abe935a45f233e75d5c9706aa89c83e",
  "private": false,
  "record": {
    "abstract": "We present a new variant of the quantum adversary method. All adversary\nmethods give lower bounds on the quantum query complexity of a function by\nbounding the change of a progress function caused by one query. All previous\nvariants upper-bound the_difference_ of the progress function, whereas our new\nvariant upper-bounds the_ratio_ and that is why we coin it the multiplicative\nadversary. The new method generalizes to all functions the new quantum\nlower-bound method by Ambainis [Amb05, ASW06] based on the analysis of\neigenspaces of the density matrix. We prove a strong direct product theorem for\nall functions that have a multiplicative adversary lower bound.",
    "arxiv_id": "quant-ph/0703237",
    "authors": [
      "Robert Spalek"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "The Multiplicative Quantum Adversary",
    "url": "https://arxiv.org/abs/quant-ph/0703237"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c4d0d23e-10bd-4410-a7fc-193e67da587e",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}