Adversary 界与量子状态转换

形式陈述

采用有限符号查询接口，取 $n\ge1$ 、有限非空字母表 $\Sigma$ 及非空 $D\subseteq\Sigma^n$ 。与通常函数求值不同，这里把依赖输入的初态作为已提供的资源，不计其制备查询。给定两族归一化复向量 $|\rho_x\rangle,|\sigma_x\rangle$ ，并固定它们各自的相位代表；coherent 误差会比较这些代表，不能逐输入任意重选相位。其 Gram matrices 为

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

先固定 $0<\varepsilon<1/2$ ，采用 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 版本，二者不能共用未说明的误差符号。

两个 Gram 矩阵都 Hermitian 半正定且对角元为一；它们是以输入为指标的内积矩阵，不是系统上的密度算子。第 $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.

若约束不可行，值记为 $+\infty$ 。对这里的坐标 filters，所有对角项都为零，所以非零对角的 $A$ 不可行；反之，每个非对角输入对至少有一个不同坐标，可逐项分配独立向量坐标完成分解。故该有限范数的自然空间是零对角矩阵，而 $\rho-\sigma$ 总在此空间中。

量

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

是 query distance：它衡量必须借哪些不同坐标，把初态输入对的内积改成目标内积。该量扩展一般 adversary 界。带误差的转换还要允许输出接近目标，因而需要对邻近目标继续优化。

精确的 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).

记未平滑距离 $W=\gamma_2(\rho-\sigma\mid\Delta)$ 。当 $0<\varepsilon<\min\{1/2,W\}$ 时，直接调用同文 Theorem 4.1 还给上界

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

$W=0$ 时两族 Gram 矩阵相同，下面的共同等距映射给出精确零查询转换；不满足上述参数范围时，可直接使用前面的平滑界，不能无声扩大所引用 Theorem 4.1 的条件。

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

直觉

算法无法看到“态的名字”，只保留输入族之间的内积。若两组向量有相同 Gram matrix，映射 $\sum_xa_x|\rho_x\rangle\mapsto\sum_xa_x|\sigma_x\rangle$ 保持每个线性组合的平方范数，因而良定义且在两族张成空间间等距。扩充工作空间后可延拓成共同酉操作，所以它不需要查询。相位固定后的 Gram 矩阵正好记录这种共同操作必须保留的信息。

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

例子与边界

把一 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$ ；反向对单个非零项应用Cauchy–Schwarz 不等式，有 $1\le\|u_{0,1}\|\|v_{1,1}\|$ ，迫使目标值至少 $1$ ，所以 filtered $\gamma_2$ 恰为 $1$ 。一次标准 bit query 将 $|x\rangle$ 写入 answer register，确实完成转换。

相位约定也有一个一 bit 反例：初态都为 $|0\rangle$ ，目标向量取 $(-1)^x|0\rangle$ 。两个目标密度算子相同，所以 non-coherent 转换零查询就够；coherent 要求则不能由同一个零查询输出同时接近 $|0\rangle$ 与 $-|0\rangle$ 的正实重叠。一查询的 phase kickback 可以精确完成。因此“最终密度状态一样”不能替代本页的 coherent 误差条件。[1, §2.1]

函数求值是特例：共同初态给 $\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 的组合，而非只靠手工拼接电路。

应用这些界时，先固定是否允许输入相关的 garbage，再选择相应的误差距离和邻近目标优化。上下界在不同平滑半径处取值，而一般状态转换的复杂度可在很小的误差区间内突变。因此即使 $\varepsilon$ 固定，两个优化值之间仍可能存在显著差距。

参考资料

[1] 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，Definition 2.1、Theorems 4.1 与 4.9。
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.

形式陈述 ​

反向链接

形式陈述