All Quantum Adversary Methods are Equivalent - Robert Špalek

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 [BSS03], weighted adversary [Amb03], strong weighted adversary [Zha04], and the Kolmogorov complexity adversary [LM04]. 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.