Bernstein-Vazirani 算法（BV 算法）由 Ethan Bernstein 和 Umesh Vazirani 于 1997 年提出，是量子计算中一个简洁而优美的算法。它解决的问题是：给定一个将 $n$ 比特输入映射为单比特输出的函数 $f$，已知存在某个隐藏的 $n$ 比特串 $s$ 使得 $f(x) = s \cdot x \pmod{2}$，如何找出 $s$？

经典计算机需要至少 $n$ 次查询，而量子计算机仅需 1 次查询。

问题背景：线性函数与隐藏信息

定义比特串的内积：若 $s = s_1 s_2 \cdots s_n$，$x = x_1 x_2 \cdots x_n$，则

$$s \cdot x = \bigoplus_{i=1}^{n} s_i \wedge x_i = (s_1 x_1 + s_2 x_2 + \cdots + s_n x_n) \bmod 2$$

即逐位相”与”后做异或。

给定一个黑盒（oracle）$f_s$，它承诺存在某个 $s \in \{0,1\}^n$ 使得对所有 $x \in \{0,1\}^n$：

$$f_s(x) = s \cdot x \pmod{2}$$

我们的任务是找出 $s$。

经典下界：经典计算机必须查询 $f$ 至少 $n$ 次。每次查询 $f(e_i)$（其中 $e_i$ 是第 $i$ 位为 1、其余为 0 的单位向量），恰好得到 $s_i$。因此 $n$ 次查询是必要且充分的。

量子上界：BV 算法只需1 次量子查询即可确定 $s$ 的全部 $n$ 位。

算法核心思想

BV 算法的核心技巧是利用Hadamard 变换将经典内积结构转化为量子态的全局相位，再通过干涉提取信息。

关键观察：对 $f_s$ 做相位编码（phase kickback），定义酉算子 $U_{f_s}$：

$$U_{f_s}|x\rangle|y\rangle = |x\rangle|y \oplus f_s(x)\rangle$$

当辅助比特 $|y\rangle = |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ 时，利用 $f_s(x) \in \{0,1\}$：

$$U_{f_s}|x\rangle|-\rangle = (-1)^{f_s(x)}|x\rangle|-\rangle = (-1)^{s \cdot x}|x\rangle|-\rangle$$

辅助比特保持不变，而输入寄存器获得了一个依赖于 $s \cdot x$ 的相位 $(-1)^{s \cdot x}$。这个相位编码了 $s$ 的全部信息。

算法步骤

电路构造

1. 初始化两个寄存器：$n$ 个输入比特 $|0\rangle^{\otimes n}$，1 个辅助比特 $|0\rangle$

2. 对辅助比特施加 $X$ 门，再施加 $H$ 门，制备 $|-\rangle$ 态：

$$|0\rangle \xrightarrow{X} |1\rangle \xrightarrow{H} |-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$$

3. 对输入寄存器的每个比特施加 $H$ 门：

$$|0\rangle^{\otimes n} \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle$$

4. 施加 oracle $U_{f_s}$（唯一的一次查询）：

$$\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|-\rangle \xrightarrow{U_{f_s}} \frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x}|x\rangle|-\rangle$$

5. 对输入寄存器再次施加 $H^{\otimes n}$

6. 测量输入寄存器，结果即为 $s$

理论推导

第 4 步的相位编码

将辅助比特制备为 $|-\rangle$ 的效果需要详细说明。对于计算基态 $|x\rangle|y\rangle$：

$$U_{f_s}|x\rangle|0\rangle = |x\rangle|0 \oplus f_s(x)\rangle = |x\rangle|f_s(x)\rangle$$

$$U_{f_s}|x\rangle|1\rangle = |x\rangle|1 \oplus f_s(x)\rangle$$

对 $|y\rangle = |-\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$：

$$U_{f_s}|x\rangle|-\rangle = \frac{1}{\sqrt{2}}\left(|x\rangle|f_s(x)\rangle - |x\rangle|1 \oplus f_s(x)\rangle\right)$$

当 $f_s(x) = 0$ 时：$|0\rangle - |1\rangle = \sqrt{2}|-\rangle$，相位因子为 $+1$。

当 $f_s(x) = 1$ 时：$|1\rangle - |0\rangle = -\sqrt{2}|-\rangle$，相位因子为 $-1$。

统一写作 $(-1)^{f_s(x)}|x\rangle|-\rangle$。由于 $f_s(x) = s \cdot x$，相位为 $(-1)^{s \cdot x}$。

Hadamard 变换提取 $s$

第 5 步对 $\frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x}|x\rangle$ 施加 $H^{\otimes n}$。

利用 Hadamard 变换的通用公式：

$$H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{z \in \{0,1\}^n} (-1)^{x \cdot z}|z\rangle$$

因此：

$$H^{\otimes n}\left(\frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x}|x\rangle\right) = \frac{1}{2^n} \sum_x (-1)^{s \cdot x} \sum_z (-1)^{x \cdot z}|z\rangle$$

交换求和顺序：

$$= \frac{1}{2^n} \sum_z \left(\sum_x (-1)^{x \cdot (s \oplus z)}\right)|z\rangle$$

对内层求和，分两种情况：

• 当 $z = s$ 时：$(-1)^{x \cdot (s \oplus s)} = (-1)^{x \cdot 0} = 1$ 对所有 $x$，求和为 $2^n$
• 当 $z \neq s$ 时：存在某个 $x$ 使得 $x \cdot (s \oplus z) = 1$，由对称性求和为 $0$

因此最终量子态为：

$$H^{\otimes n}\left(\frac{1}{\sqrt{2^n}} \sum_x (-1)^{s \cdot x}|x\rangle\right) = |s\rangle$$

测量结果以概率 1 为 $s$。完美提取，无需重复。

为什么经典需要 $n$ 次而量子只需 1 次

经典计算中，每次查询 $f(x)$ 只能得到 $s \cdot x$ 这 1 bit 信息。要确定 $n$ 个未知数 $s_1, \ldots, s_n$，至少需要 $n$ 个线性无关的方程，即 $n$ 次查询。

量子计算中，$H^{\otimes n}$ 将所有 $2^n$ 个输入 $x$ 的叠加态”打包”到一次查询中。oracle 对叠加态的响应同时”编码”了 $s$ 在所有方向上的内积信息。第二次 $H^{\otimes n}$ 通过全局干涉将这些信息”解码”回计算基态 $|s\rangle$。

这是量子并行性（quantum parallelism）与干涉（interference）协同工作的典范：并行性提供了访问所有输入的能力，而干涉消除了”错误答案”的概率幅、放大了”正确答案”的概率幅。

量子电路图

$U_f$ 作用为 $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus (s \cdot x)\rangle$，可通过 CNOT 门级联实现。

具体例子：$n = 3$，$s = 101$

隐藏串 $s = 101$，即 $s_1 = 1,\; s_2 = 0,\; s_3 = 1$。oracle 计算 $f(x) = x_1 \oplus x_3$。

步骤 1：初始态 $|000\rangle|0\rangle$

步骤 2：辅助比特 $\to |-\rangle$

步骤 3：$H^{\otimes 3}$ 作用于输入寄存器：

$$|000\rangle \xrightarrow{H^{\otimes 3}} \frac{1}{\sqrt{8}} \sum_{x=0}^{7} |x\rangle$$

步骤 4：查询 oracle（唯一一次）：

$$\frac{1}{\sqrt{8}} \sum_x (-1)^{s \cdot x}|x\rangle = \frac{1}{\sqrt{8}} \sum_x (-1)^{x_1 \oplus x_3}|x\rangle$$

各项的相位：

步骤 5：施加 $H^{\otimes 3}$，由推导知结果必为 $|101\rangle = |s\rangle$。

步骤 6：测量得到 $s = 101$，验证：$f(x) = x_1 \oplus x_3$ ✓

复杂度分析

BV 算法是一个精确量子加速（exact quantum speedup）：量子算法以概率 1 给出正确答案，不存在概率性误差，加速比为 $n$ 倍。

推广与意义

与 Deutsch-Jozsa 算法的关系

Deutsch-Jozsa 算法判断 $f$ 是常函数还是平衡函数，可视为 BV 算法在 $s = 0$（常函数）和 $s \neq 0$（平衡函数）情形下的特例。

与 Simon 算法的关系

Simon 算法处理 $f(x) = f(x \oplus s)$（函数具有隐藏周期 $s$），是 BV 算法向非线性函数的推广。Simon 算法需要 $O(n)$ 次查询，但相比经典的 $\Omega(2^{n/2})$ 次，已有指数加速。Shor 算法正是在 Simon 算法的基础上发展而来。

在量子学习理论中的应用

BV 算法是证明量子优势的基本构件之一。Bernstein 和 Vazirani 利用它构造了第一个相对于 oracle 具有指数分离的量子复杂度结果：存在一个语言，量子多项式时间（BQP）可判定，而经典概率多项式时间（BPP）不可判定。

实际应用

虽然 BV 算法本身是一个理论算法，但其相位编码和 Hadamard 干涉的技术被广泛用于：

• 量子随机存取存储器（QRAM）的查询验证
• 量子机器学习中的内积估计
• 量子密码学中的协议设计

总结

Bernstein-Vazirani 算法以极简的电路（$2n+2$ 个量子门 + 1 次 oracle 查询）实现了对经典下界的突破，展示了量子叠加态如何在单次操作中”并行”处理所有输入，再通过 Hadamard 干涉精确提取全局信息。它是理解量子计算优势来源的最佳入门案例之一。

参考文献：

1. Bernstein, E., & Vazirani, U. (1997). Quantum Complexity Theory. SIAM Journal on Computing, 26(5), 1411–1473.
2. Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press.
3. Aaronson, S. (2013). Quantum Computing Since Democritus. Cambridge University Press.