论文标题
与关系的量子查询复杂性
The quantum query complexity of composition with a relation
论文作者
论文摘要
负重对手方法，$ \ mathrm {adv}^\ pm（g）$，已知来表征任何布尔函数$ g $的有限误差量子查询复杂性，并且也要服从完美的组成定理$ \ mathrm $ \ mathrm {adv}}^\ pm（f \ circ g^n） \ Mathrm {adv}^\ pm（g）$。 Belovs给出了负重对手方法的修改版本，$ \ mathrm {adv} _ {rel}^\ pm（f）$，其特征是关系$ f \ subseteq \ subseteq \ subseteq \ subseteq \ subseteq \ subseteq \ {0,1 \}^n \ times [k times [k times [k] $的界限 - error量子查询复杂性，如果$ \ mathrm {adv}^\ pm（f_a）= o（\ mathrm {adv} _ {rel}^\ pm（f））$在[k] $ in [k] $中，$ f_a $是boolean函数定义为$ f_a（yif $ f_a（if），则有效证明是有效的。在此注释中，我们显示了一个完美的组成定理，用于与布尔函数$ g $ \ [\ mathrm {adv} _ {rel}^\ pm（f \ circ g^n）= \ mathrm {adv} _ {adv} _ {res} _ {rel}^{rel}^\ pm（f） \]对于有效的可验证关系$ f $这意味着$ q（f \ circ g^n）=θ（\ mathrm {adv} _ {rel}^\ pm（f）\ mathrm {adv}^\ pm（g））$。
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) = Θ( \mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) )$.
