The General Adversary Bound: A Survey

• DOI: 10.48550/arxiv.2104.06380
• Publication Date: 2021-01-01
• Authors: Lily Li; Morgan Shirley
• Keywords: Intuition

Ben Reichardt showed in a series of results that the general adversary bound function characterizes its quantum query complexity. This survey seeks to aggregate background and definitions necessary understand proof. Notable among these are lower proof, span programs, witness size, semi-definite programs. These definitions, addition examples detailed expositions, serve give reader better intuition graph-theoretic nature upper bound. We also include an applications this result bounds on DeMorgan formula size.