The quantum query complexity of composition with a relation
Authors:
Preprint
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) )$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Improved Quantum Query Algorithms for Triangle Detection and Associativity TestingAlgorithmica, 2015
- Quantum Algorithms for Learning Symmetric Juntas via the Adversary Boundcomputational complexity, 2015
- Span Programs are Equivalent to Quantum Query AlgorithmsSIAM Journal on Computing, 2014
- Quantum Adversary (Upper) BoundLecture Notes in Computer Science, 2012
- Quantum Algorithms for the Triangle ProblemSIAM Journal on Computing, 2007
- Quantum Walk Algorithm for Element DistinctnessSIAM Journal on Computing, 2007
- Polynomial degree vs. quantum query complexityJournal of Computer and System Sciences, 2006
- On the power of Ambainis lower boundsTheoretical Computer Science, 2005
- All Quantum Adversary Methods Are Equivalent2005
- Quantum Lower Bounds by Quantum ArgumentsJournal of Computer and System Sciences, 2002