All Quantum Adversary Methods are Equivalent

Robert Spalek, Mario Szegedy

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 advers…