The quantum query complexity of composition with a relation
- Publication Type:
- Journal Article
- Citation:
- 2020
- Issue Date:
- 2020-04-14
Recently Added
Filename | Description | Size | |||
---|---|---|---|---|---|
2004.06439v1.pdf | Accepted Manuscript | 195.91 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is new to OPUS and is not currently available.
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) )$.
Please use this identifier to cite or link to this item: