- All Quantum Adversary Methods are Equivalent
- Lecture Notes in Computer Science
- Pages (from-to)
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
Proceedings title: Proceedings of 32nd International Colloquium on Automata, Languages and Programming
Place of publication: Lisboa, Portugal
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.