Q The Query Complexity Zoo

The adversary methods

From Ambainis' 2000 lower bound to the SDP that exactly characterises quantum query complexity.

Positive weights -- \(\mathrm{Adv}(f)\)

Ambainis' original method, in the form $\mathrm{Adv}(f)=\max_{\Gamma\ge 0}\|\Gamma\|/\max_i\|\Gamma\circ D_i\|$. Špalek-Szegedy showed the spectral, weighted, Kolmogorov-complexity and minimax formulations all coincide [SpalekSzegedy06].

Barrier: $\mathrm{Adv}(f)\le\sqrt{\mathrm{C}^0(f)\mathrm{C}^1(f)}$ [SpalekSzegedy06, Zhang05], strengthened to $\sqrt{\mathrm{RC}^0(f)\mathrm{RC}^1(f)}$ [KulkarniTal16]. So the positive adversary is useless for \(\mathrm{ED}_n\), where $\mathrm{C}=2$ but $\mathrm{Q}=\Theta(n^{2/3})$.

Negative weights -- \(\mathrm{Adv}^{\pm}(f)\)

Dropping the non-negativity constraint gives $\mathrm{Adv}^{\pm}$, which exactly characterises quantum query complexity: $\mathrm{Q}(f)=\Theta(\mathrm{Adv}^{\pm}(f))$ [HLS07, Reichardt11, LMRSS11], for total functions, partial functions, and state conversion. It is an SDP, hence computable in principle, and it composes perfectly.

Classical analogues

\(\mathrm{CA}(f)\), the classical adversary bound, and the certificate-game family \(\mathrm{CG}(f)\) / \(\mathrm{CG}^{\mathrm{pub}}(f)\) / \(\mathrm{CG}^{*}(f)\) / \(\mathrm{CG}^{\mathrm{ns}}(f)\) [CGLMSG23]. All classical adversary methods are equivalent for total functions [ABIKPS17]. Two pleasant identities from the certificate-game paper: the single-bit public-coin game is $\Theta(\mathrm{s}(f))$, and the single-bit private-coin game is $\lambda(f)^2$.

The private-coin game is the odd one out and worth a warning, because it breaks the habit every other row of the zoo trains you into. Three of the four variants collapse to $\mathrm{CA}$; $\mathrm{CG}$ does not. It sits above $\mathrm{R}_0$, not below it, and the $\lambda^2$ identity above generalises to $\mathrm{CG}(f)=\Omega(\mathrm{Adv}(f)^2)$ -- which means $\mathrm{CG}$ is not bounded by $\mathrm{D}$ and can exceed the number of variables outright. Parity is the clean example: $\mathrm{CG}(\oplus_n)=\Theta(n^2)$, squeezed between $\mathrm{Adv}^2=n^2$ below and $\mathrm{C}^0\mathrm{C}^1=n^2$ above.

Spectral sensitivity -- \(\lambda(f)\)

$\lambda(f)$, the spectral norm of the sensitivity graph, is the simplest quantity below $\mathrm{Adv}$: $\lambda\le\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(\mathrm{Q})$, and $\sqrt{\mathrm{s}}\le\lambda\le\mathrm{s}$ [ABKRT21].