dorsal/arxiv
View SchemaThe Multiplicative Quantum Adversary
| Authors | Robert Spalek |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0703237 |
| URL | https://arxiv.org/abs/quant-ph/0703237 |
Abstract
We present a new variant of the quantum adversary method. All adversary methods give lower bounds on the quantum query complexity of a function by bounding the change of a progress function caused by one query. All previous variants upper-bound the_difference_ of the progress function, whereas our new variant upper-bounds the_ratio_ and that is why we coin it the multiplicative adversary. The new method generalizes to all functions the new quantum lower-bound method by Ambainis [Amb05, ASW06] based on the analysis of eigenspaces of the density matrix. We prove a strong direct product theorem for all functions that have a multiplicative adversary lower bound.
{
"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
}