The negative weight adversary method, $mathrm{ADV}^pm(g)$, is known to characterize the bounded-error quantum query complexity of any Boolean function $g$, and also obeys a perfect composition theorem $mathrm{ADV}^pm(f circ g^n) = mathrm{ADV}^pm(f) mathrm{ADV}^pm(g)$. Belovs gave a modified version of the negative weight adversary method, $mathrm{ADV}_{rel}^pm(f)$, that characterizes the bounded-error quantum query complexity of a relation $f subseteq {0,1}^n times [K]$, provided the relation is efficiently verifiable. A relation is efficiently verifiable if $mathrm{ADV}^pm(f_a) = o(mathrm{ADV}_{rel}^pm(f))$ for every $a in [K]$, where $f_a$ is the Boolean function defined as $f_a(x) = 1$ if and only if $(x,a) in f$. In this note we show a perfect composition theorem for the composition of a relation $f$ with a Boolean function $g$ [ mathrm{ADV}_{rel}^pm(f circ g^n) = mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) enspace . ] For an efficiently verifiable relation $f$ this means $Q(f circ g^n) = Theta( mathrm{ADV}_{rel}^pm(f) mathrm{ADV}^pm(g) )$.
Download