All Quantum Adversary Methods are Equivalent
| Authors |
|
|---|---|
| Publication date | 2005 |
| Journal | Lecture Notes in Computer Science |
| Volume | Issue number | 3580 |
| Pages (from-to) | 1299-1311 |
| Organisations |
|
| 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 equal: spectral adversary [Barnum, Saks, and Szegedy, 2003], weighted adversary [Ambainis, 2003], strong weighted adversary [Zhang, 2004], and the Kolmogorov complexity adversary [Laplante and Magniez, 2003]. We also present a few new equivalent formulations of the method. This shows that there is essentially one quantum adversary method. From our approach, all known limitations of all versions of the quantum adversary method easily follow. |
| Document type | Article |
| Note |
quant-ph/0409116 Proceedings title: Proceedings of 32nd International Colloquium on Automata, Languages and Programming Publisher: Springer Place of publication: Lisboa, Portugal |
| Published at | http://www.springerlink.com/content/5ae875yw8nvwv8gk/ |
| Downloads | |
| Permalink to this page | |