The quantum query complexity of composition with a relation

The negative weight adversary method, ${\mathrm{A}\mathrm{D}\mathrm{V}}^{\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{A}\mathrm{D}\mathrm{V}$^\pm(f \circ g^n) = $\mathrm{A}\mathrm{D}\mathrm{V}$^\pm(f) $\mathrm{A}\mathrm{D}\mathrm{V}$^\pm(g)$. Belovs gave a modified version of the negative weight adversary method, ${\mathrm{A}\mathrm{D}\mathrm{V}}_{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{A}\mathrm{D}\mathrm{V}$^\pm(f_a) = o($\mathrm{A}\mathrm{D}\mathrm{V}${rel}^\pm(f))$forevery$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{A}\mathrm{D}\mathrm{V}}_{rel}^{\pm }(f\circ g^n)={\mathrm{A}\mathrm{D}\mathrm{V}}_{rel}^{\pm }(f){\mathrm{A}\mathrm{D}\mathrm{V}}^{\pm }(g)\mathrm{.}$$ For an efficiently verifiable relation $f$ this means $Q(f \circ g^n) = \Theta( $\mathrm{A}\mathrm{D}\mathrm{V}${rel}^\pm(f) $\mathrm{A}\mathrm{D}\mathrm{V}$^\pm(g) )$.