Adversary 界与量子状态转换

形式陈述

令合法输入集为 $D$ 。输入 $x$ 对应初态 $|\rho_x\rangle$ 与目标态 $|\sigma_x\rangle$ ，其 Gram matrices 为

\rho_{xy}=\langle\rho_x|\rho_y\rangle,\qquad \sigma_{xy}=\langle\sigma_x|\sigma_y\rangle.

本页先固定 coherent conversion 的误差口径：算法从 $|\rho_x\rangle|0\rangle$ 出发，输出纯态 $|\sigma'_x\rangle$ ，并对每个合法输入满足

\operatorname{Re}\langle\sigma'_x|\sigma_x,0\rangle \ge\sqrt{1-\varepsilon}.

$Q_\varepsilon(\rho,\sigma)$ 是达到这项逐点保证所需的最小最坏硬查询数。若只要求丢弃 workspace 后的目标寄存器具有高 fidelity，就进入下文另列的 non-coherent 版本，二者不能共用未说明的误差符号。

第 $i$ 个坐标的查询 filter 是 $\Delta_i[x,y]=\mathbf1[x_i\ne y_i]$ 。对同型矩阵 $A$ ，filtered $\gamma_2$ 定义为所有向量族 $\{u_{x,i}\},\{v_{y,i}\}$ 中

\gamma_2(A\mid\Delta) =\min \max\!\left\{ \max_x\sum_i\|u_{x,i}\|^2,\, \max_y\sum_i\|v_{y,i}\|^2 \right\},

约束为

A_{xy} =\sum_i\Delta_i[x,y]\langle u_{x,i},v_{y,i}\rangle.

量

\gamma_2(\rho-\sigma\mid\Delta)

是 query distance：它衡量必须借哪些不同坐标，把初态输入对的内积改成目标内积。该量扩展一般 adversary 界，但任意误差下的 state conversion 不能无条件写成同它常数因子相等。

精确的 robust 口径要允许邻近目标。以下普通范数是上面定义的特例 $\gamma_2(B)=\gamma_2(B\mid\{J\})$ ，其中 $J$ 为全一 filter。定义

q_\delta(\rho,\sigma) =\min_{\sigma'\succeq0} \left\{ \gamma_2(\rho-\sigma'\mid\Delta): \gamma_2(\sigma'-\sigma)\le\delta \right\}.

Lee–Mittal–Reichardt–Špalek–Szegedy 对 coherent conversion 证明

\Omega\!\left(q_{2\sqrt{2\varepsilon}}(\rho,\sigma)\right) \le Q_\varepsilon(\rho,\sigma) \le O\!\left( q_{\varepsilon^4/16}(\rho,\sigma) \frac{\log(1/\varepsilon)}{\varepsilon^2} \right).

直接使用未平滑距离也给上界

Q_\varepsilon(\rho,\sigma) =O\!\left( \gamma_2(\rho-\sigma\mid\Delta) \frac{\log(1/\varepsilon)}{\varepsilon^2} \right).

Non-coherent conversion 若允许输入相关 garbage，还要在目标 Gram matrix 与 garbage Gram matrix 的 Hadamard product上继续优化。

直觉

算法无法看到“态的名字”，只保留输入族之间的内积。若两组纯态有相同 Gram matrix，就存在同一个输入无关 isometry 把一组送到另一组；因此 $\rho\to\sigma$ 是状态转换的正确语义。

Filtered factorization 把每一项内积变化归因于某个坐标差异。一次 query 只能沿这些 filters 改变进度量，所以给下界；反过来，最优 factorization 可生成两次反射和 phase detection 算法。一般态的误差不一定能像函数标签那样多数表决，故上界保留 $\varepsilon^{-2}\log(1/\varepsilon)$ ，不能借函数求值 tightness 抹掉。

例子与边界

把一 bit 身份函数写成状态生成。输入 $x\in\{0,1\}$ ，初态都相同，因此

\rho= \begin{pmatrix}1&1\\1&1\end{pmatrix};

目标为正交标签 $|0\rangle,|1\rangle$ ，故 $\sigma=I$ 。于是

\rho-\sigma =\begin{pmatrix}0&1\\1&0\end{pmatrix} =\Delta_1.

取一维向量 $u_{0,1}=u_{1,1}=v_{0,1}=v_{1,1}=1$ ，约束在非对角项给 $1$ ，对角项被 $\Delta_1=0$ 消掉，目标值至多 $1$ ；反向的单个非零项又迫使值至少 $1$ ，所以 filtered $\gamma_2$ 恰为 $1$ 。一次标准 bit query 将 $|x\rangle$ 写入 answer register，确实完成转换。

函数求值是特例：共同初态给 $\rho=J$ ，正交输出标签给 $\sigma_{xy}=\mathbf1[f(x)=f(y)]$ 。Boolean 输出时相应 query distance 与 $\operatorname{Adv}^{\pm}(f)$ 对齐，固定常数错误下得到 $Q(f)=\Theta(\operatorname{Adv}^{\pm}(f))$ 。这条紧性依赖目标是可稳健读取的经典标签；任意非正交目标态不享有同样的错误放大。

推论与应用

State conversion 统一 function evaluation、coherent label generation 与 state generation，也解释 general adversary 的上界为何来自反射算法。它还把 composition 变成 Gram matrix 与 filters 的组合，而非只靠手工拼接电路。

引用时必须说明 coherent 还是允许 garbage、目标误差用何种 fidelity/Gram 距离、以及 $\varepsilon$ 是否固定常数。省略这些条件后写 $\Theta(\gamma_2)$ ，会把函数特例的 tightness错误推广到一般状态转换。

参考资料

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy, “Quantum Query Complexity of State Conversion,” Proceedings of FOCS 2011, pp. 344–353.
Ben W. Reichardt, “Reflections for Quantum Query Algorithms,” Proceedings of SODA 2011, pp. 560–569.
Peter Høyer, Troy Lee, and Robert Špalek, “Negative Weights Make Adversaries Stronger,” Proceedings of STOC 2007, pp. 526–535.

形式陈述 ​

反向链接

形式陈述