dorsal/arxiv
View SchemaAll Quantum Adversary Methods are Equivalent
| Authors | Robert Spalek, Mario Szegedy |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0409116 |
| URL | https://arxiv.org/abs/quant-ph/0409116 |
| Journal | Theory of Computing, 2(1):1-18, 2006 |
Abstract
The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equivalent: spectral adversary (Barnum, Saks, and Szegedy, 2003), weighted adversary (Ambainis, 2003), strong weighted adversary (Zhang, 2005), and the Kolmogorov complexity adversary (Laplante and Magniez, 2004). We also pa few new equivalent formulations of the method. This shows that there is essentially _one_ quantum adversary method. From our approach, all known limitations of these versions of the quantum adversary method easily follow.
{
"annotation_id": "4f6ade10-b476-486a-a46b-38e729f51444",
"date_created": "2026-03-02T18:02:10.465000Z",
"date_modified": "2026-03-02T18:02:10.465000Z",
"file_hash": "e5bf20c3480b6967190b6ac819bbcfcdc4e34adaeeceefb0d2e676b6c8390a1a",
"private": false,
"record": {
"abstract": "The quantum adversary method is one of the most versatile lower-bound methods\nfor quantum algorithms. We show that all known variants of this method are\nequivalent: spectral adversary (Barnum, Saks, and Szegedy, 2003), weighted\nadversary (Ambainis, 2003), strong weighted adversary (Zhang, 2005), and the\nKolmogorov complexity adversary (Laplante and Magniez, 2004). We also pa few\nnew equivalent formulations of the method. This shows that there is essentially\n_one_ quantum adversary method. From our approach, all known limitations of\nthese versions of the quantum adversary method easily follow.",
"arxiv_id": "quant-ph/0409116",
"authors": [
"Robert Spalek",
"Mario Szegedy"
],
"categories": [
"quant-ph"
],
"journal_ref": "Theory of Computing, 2(1):1-18, 2006",
"title": "All Quantum Adversary Methods are Equivalent",
"url": "https://arxiv.org/abs/quant-ph/0409116"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "3b86801c-01a1-4c3b-a331-138905457786",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}