The quantum query complexity of composition with a relation

Abstract

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))$.

15 pages

References in corpus (4)

• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Span-program-based quantum algorithm for evaluating formulas
• Variations on Quantum Adversary