Hadamard 测试 | Codeboy's Blog

形式陈述

给定可重复制备的归一化态 $|\psi\rangle$ ，以及真正可用的受控酉

\operatorname{c}U=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U,

Hadamard测试产生一个 $\{+1,-1\}$ 随机变量，其均值为 $\operatorname{Re}\langle\psi|U|\psi\rangle$ ；加入规定的控制相位后，均值变为虚部。[1, §2.2]

电路顺序为：控制辅助从 $|0\rangle$ 出发，先施 $H$ ，再调用受控 $U$ ；实部版本直接施 $H$ 后测控制 $Z$ ，虚部版本先施 $S^\dagger=\operatorname{diag}(1,-i)$ ，再施 $H$ 后测。把测量位 $m$ 换成数值 $(-1)^m$ 。

这使用电路测量的分支语义。受控调用和数据制备都是输入资源；仅能调用一个未知黑盒 $U$ ，并不自动满足受控 $U$ 的假设。

直觉

控制位的两条路径分别让数据“不做U”和“做U”。最后的Hadamard把两条路径干涉，干涉强弱由两份数据态的内积决定。

直接干涉读出实部；先把一条路径转四分之一圈，再干涉就读出虚部。单次测量只给一个随机bit，复数期望需要许多次独立制备和测量后取平均。

实部版本为H、受控U、H和Z测量，虚部版本在最后H前加入S逆；两者分别给概率零等于一加实部或虚部再除二。

例子与边界

实部为什么出现在概率里

受控 $U$ 后，联合态为

\frac{|0\rangle|\psi\rangle+|1\rangle U|\psi\rangle}{\sqrt2}.

再施 $H$ ，控制0和1的未归一化数据向量分别为

\frac{(I+U)|\psi\rangle}{2},\qquad \frac{(I-U)|\psi\rangle}{2}.

令 $z=\langle\psi|U|\psi\rangle$ ，展开平方范数得到

\Pr(m=0)=\frac{1+\operatorname{Re}z}{2},\qquad \Pr(m=1)=\frac{1-\operatorname{Re}z}{2}.

相减即为 $\mathbb E(-1)^m=\operatorname{Re}z$ 。不需要 $|\psi\rangle$ 是 $U$ 的特征向量；任意叠加都适用。

虚部的正负号取决于S还是S逆

在末端 $H$ 前施 $S^\dagger$ ，联合态第二项变成 $-i|1\rangle U|\psi\rangle$ 。于是控制0分支为 $(I-iU)|\psi\rangle/2$ ，

\Pr(m=0)=\frac{1+\operatorname{Im}z}{2}.

若误施 $S$ ，第二项是 $+iU$ ，读出的均值会变成 $-\operatorname{Im}z$ 。两种约定都能使用，但必须明确符号，不能只画一个未说明的相位门。

一个真正含虚部的例子

取 $|\psi\rangle=|+\rangle$ 、 $U=\operatorname{diag}(1,i)$ ，则

z=\frac{1+i}{2}.

实部版本控制0的未归一化向量是

\frac{2|0\rangle+(1+i)|1\rangle}{2\sqrt2},

其范数平方为 $(4+2)/8=3/4$ 。虚部版本对应

\frac{(1-i)|0\rangle+2|1\rangle}{2\sqrt2},

范数平方同样为 $3/4$ 。因此两种随机符号的均值都为 $3/4-1/4=1/2$ ，合起来才重建复数 $z$ 。

如果目标只是知道 $z$ ，并不需要输出整份 $U|\psi\rangle$ 的经典坐标；反过来，这两个均值也远不足以描述一般高维输出态。

推论与应用

样本账：一次调用不等于一次精确估计

对某一版本独立运行 $m$ 次，记输出符号为 $X_1,\ldots,X_m$ 。它们在 $[-1,1]$ ，由Hoeffding不等式，

\Pr\left[\left|\frac1m\sum_iX_i-\mathbb EX_i\right|\ge\epsilon\right] \le2e^{-m\epsilon^2/2}.

给定 $0<\epsilon<1$ 、 $0<\delta<1$ ，若要求实部、虚部各自加法误差不超过 $\epsilon$ ，用并集界把两项失败概率各控制在 $\delta/2$ ，则每个版本取整数

m\ge\frac2{\epsilon^2}\log\frac4\delta

即可；在共同成功事件上，复数模误差至多 $\sqrt2\epsilon$ 。总计 $2m$ 次数据制备、 $2m$ 次受控 $U$ ，再加 $O(m)$ 个控制位门和测量。若制备一次成本 $C_\psi$ 、受控调用成本 $C_U$ ，基本工作量为 $O(m(C_\psi+C_U+1))$ 。

每次运行要有新的一份输入。测过控制位后，数据通常已按分支改变，不能无条件把同一份未知数据反复使用并仍声称样本独立。若有更强的相干幅度估计接口，可能改善精度依赖，但那是另一个算法与资源模型。

输入与门误差怎样影响均值

若实际数据态与理想态的迹距离至多 $\eta_\psi$ ，实际酉与目标的算子范数误差满足 $\|\widetilde U-U\|\le\eta_U$ ，则相应复期望偏差至多

2\eta_\psi+\eta_U.

|\operatorname{Tr}(U(\rho-\sigma))| \le\sum_j|\lambda_j|=2D(\rho,\sigma).

第二项由算子范数界 $|\operatorname{Tr}((\widetilde U-U)\rho)|\le\eta_U$ 得到。统计误差应另加到这个系统偏差上，增加样本数不会自动消除制备或门合成偏差。其他控制门的误差可按逐门合成预算统一控制。

受控未知黑盒为什么不是免费的

单独作用的 $U$ 与 $e^{i\theta}U$ 只差整体相位，作为黑盒通道无法区分。但它们的受控版本不同：相位只加在控制1分支，成为可测的相对相位。

特别地， $I$ 与 $-I$ 是同一个不带控制的通道；若能免费把它们变成受控门，作用于控制 $|+\rangle$ 就会分别得到 $|+\rangle$ 和 $|-\rangle$ ，可以完全区分。因此通用的“给未知酉加控制”不可能仅凭原黑盒通道自动实现。

已知门分解时，可以逐门编译受控电路并保留整体相位约定；接口直接给 controlled- $U$ 时，也可以按一次相应oracle调用计费。两种情况下都应把访问方式写清。

参考资料

[1] Dorit Aharonov, Vaughan Jones and Zeph Landau, A Polynomial Quantum Algorithm for Approximating the Jones Polynomial, 2006作者版，§2.2：Hadamard测试的随机符号均值与虚部初始相位。本页把该相位移至末端 $S^\dagger$ ，独立展开两个分支和样本界。

形式陈述 ​

实部为什么出现在概率里 ​

虚部的正负号取决于S还是S逆 ​

一个真正含虚部的例子 ​

样本账：一次调用不等于一次精确估计 ​

输入与门误差怎样影响均值 ​

受控未知黑盒为什么不是免费的 ​