Quantum Adversary Method

Context: one of the two major techniques for proving quantum query lower bounds.

Adversary method: early work

• [Amb00] Quantum lower bounds by quantum arguments by Andris Ambainis
  • arXiv, BibTeX, [Other formats: STOC00, JCSS]
  • Summary:

Generalized (negative-weight) adversary method

Quantum algorithms induced by adversary method

Extensions

• [BBH+17] Provably secure key establishment against quantum adversaries by Aleksandrs Belovs, Gilles Brassard, Peter Hoyer, Marc Kaplan, Sophie Laplante, Louis Salvail
  • arXiv, BibTeX
  • Summary: an adversary method for average-case query complexity