dorsal/arxiv
View SchemaTight adversary bounds for composite functions
| Authors | Peter Hoyer, Troy Lee, Robert Spalek |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0509067 |
| URL | https://arxiv.org/abs/quant-ph/0509067 |
Abstract
The quantum adversary method is a versatile method for proving lower bounds on quantum algorithms. It yields tight bounds for many computational problems, is robust in having many equivalent formulations, and has natural connections to classical lower bounds. A further nice property of the adversary method is that it behaves very well with respect to composition of functions. We generalize the adversary method to include costs--each bit of the input can be given an arbitrary positive cost representing the difficulty of querying that bit. We use this generalization to exactly capture the adversary bound of a composite function in terms of the adversary bounds of its component functions. Our results generalize and unify previously known composition properties of adversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of Barnum and Saks on the quantum query complexity of read-once functions.
{
"annotation_id": "95d2083c-2a34-4ff3-bc5b-8509aee68c1f",
"date_created": "2026-03-02T18:02:19.495000Z",
"date_modified": "2026-03-02T18:02:19.495000Z",
"file_hash": "3d6626c98ebd3fcd28b5c6d677d1aa329549b50fa7dcdd626aa554dee529dcf2",
"private": false,
"record": {
"abstract": "The quantum adversary method is a versatile method for proving lower bounds\non quantum algorithms. It yields tight bounds for many computational problems,\nis robust in having many equivalent formulations, and has natural connections\nto classical lower bounds. A further nice property of the adversary method is\nthat it behaves very well with respect to composition of functions. We\ngeneralize the adversary method to include costs--each bit of the input can be\ngiven an arbitrary positive cost representing the difficulty of querying that\nbit. We use this generalization to exactly capture the adversary bound of a\ncomposite function in terms of the adversary bounds of its component functions.\nOur results generalize and unify previously known composition properties of\nadversary methods, and yield as a simple corollary the Omega(sqrt{n}) bound of\nBarnum and Saks on the quantum query complexity of read-once functions.",
"arxiv_id": "quant-ph/0509067",
"authors": [
"Peter Hoyer",
"Troy Lee",
"Robert Spalek"
],
"categories": [
"quant-ph"
],
"title": "Tight adversary bounds for composite functions",
"url": "https://arxiv.org/abs/quant-ph/0509067"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "656fc9a2-f44d-444a-84da-656943fcf23e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}