Bernstein-Vazirani 算法详解：一次查询找出隐藏比特串

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\]

其中 \(\oplus\) 表示按位异或。直观地说，我们把 \(s\) 与 \(x\) 逐位相"与"，再把所得各比特异或起来，得到单个比特。容易看出该内积对第二个变元是线性的：对任意 \(x, x'\) 与比特 \(c\)，有 \(s \cdot (x \oplus x') = (s \cdot x) \oplus (s \cdot x')\)，\(s \cdot (c \cdot x') = c \wedge (s \cdot x')\)。这一线性性是下文所有推导的代数基础。

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

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

我们的任务是找出 \(s\)。

经典下界：经典算法必须查询 \(f\) 至少 \(n\) 次。\(n\) 次查询是充分的：每次查询 \(f(e_i)\)（其中 \(e_i\) 是第 \(i\) 位为 1、其余为 0 的单位向量），由内积的线性性恰好得到 \(s_i\)，\(n\) 次查询即可拼出完整的 \(s\)。"少于 \(n\) 次必定不够"的严格论证见下文"经典下界的严格论证"一节。

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

算法核心思想

BV 算法的核心技巧分两步：先用 Hadamard 变换把输入寄存器制备成均匀叠加态，让 oracle 通过相位回踢（phase kickback，也称相位编码）把 \(s \cdot x\) 编码为相位；再用一次 Hadamard 变换让这些相位发生干涉，从干涉结果中读出 \(s\)。

我们定义与 \(f_s\) 对应的酉算子 \(U_{f_s}\)：

\[U_{f_s}|x\rangle|y\rangle = |x\rangle|y \oplus f_s(x)\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}}\]

  1. 对输入寄存器的每个比特施加 \(H\) 门：

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

  1. 施加 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\]

  1. 对输入寄存器再次施加 \(H^{\otimes n}\)

  2. 测量输入寄存器，结果即为 \(s\)

理论推导

相位回踢的完整推导

我们将辅助比特制备为 \(|-\rangle\) 的效果完整算一遍。oracle 作用在计算基态上时按定义翻转辅助比特：

\[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\]

由于 \(U_{f_s}\) 是线性的，我们把它作用到 \(|-\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)\) 的取值分两种情况代入：

  • 当 \(f_s(x) = 0\) 时，两个分量分别为 \(|0\rangle\) 与 \(|1\rangle\)，于是上式为 \(\frac{1}{\sqrt{2}}(|x\rangle|0\rangle - |x\rangle|1\rangle) = |x\rangle|-\rangle\)，相位因子为 \(+1\)；

  • 当 \(f_s(x) = 1\) 时，两个分量分别为 \(|1\rangle\) 与 \(|0\rangle\)，于是上式为 \(\frac{1}{\sqrt{2}}(|x\rangle|1\rangle - |x\rangle|0\rangle) = -|x\rangle|-\rangle\)，相位因子为 \(-1\)。

两种情况可以统一写成 \((-1)^{f_s(x)}|x\rangle|-\rangle\)：\(f_s(x) = 0\) 时指数为偶数给出 \(+1\)，\(f_s(x) = 1\) 时指数为奇数给出 \(-1\)。再代入承诺条件 \(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}\)。整个推导只用两件事实：单比特恒等式 \(H|0\rangle = \frac{|0\rangle + |1\rangle}{\sqrt 2}\)、\(H|1\rangle = \frac{|0\rangle - |1\rangle}{\sqrt 2}\)，以及 \(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\]

（验证：右端对每个分量比特恰好贡献 \((-1)^{x_i}\) 因子当且仅当 \(z_i = 1\)，展开张量积即得。）

记 \(N = 2^n\)，则第 5 步的态为

\[H^{\otimes n}\left(\frac{1}{\sqrt{N}} \sum_x (-1)^{s \cdot x}|x\rangle\right) \overset{\text{线性性}}{=} \frac{1}{\sqrt{N}} \sum_x (-1)^{s \cdot x} \cdot \frac{1}{\sqrt{N}} \sum_z (-1)^{x \cdot z}|z\rangle = \frac{1}{N} \sum_x \sum_z (-1)^{s \cdot x}(-1)^{x \cdot z}|z\rangle\]

交换双重求和的顺序，把对 \(x\) 的求和放到内层：

\[= \frac{1}{N} \sum_z \left(\sum_x (-1)^{s \cdot x}(-1)^{x \cdot z}\right)|z\rangle\]

接下来合并指数。由于 \((-1)\) 的幂只依赖指数的奇偶性，\((-1)^{s \cdot x}(-1)^{x \cdot z} = (-1)^{s \cdot x + x \cdot z}\)；又由内积的逐位分配律，

\[s \cdot x + x \cdot z \equiv x \cdot (s \oplus z) \pmod{2}\]

（逐位验证：\(\bigoplus_i x_i s_i\) 与 \(\bigoplus_i x_i z_i\) 异或，等于 \(\bigoplus_i x_i (s_i \oplus z_i)\)。）于是内层求和变为

\[\sum_{x \in \{0,1\}^n} (-1)^{x \cdot (s \oplus z)}\]

我们证明关键的正交和等式：

\[\sum_{x \in \{0,1\}^n} (-1)^{w \cdot x} = N \cdot \delta_{w, 0}, \qquad w \in \{0,1\}^n\]

  • 若 \(w = 0\)：每一项都是 \((-1)^0 = 1\)，共 \(N\) 项，和为 \(N\)。

  • 若 \(w \neq 0\)：取某个满足 \(w_j = 1\) 的位 \(j\)。映射 \(x \mapsto x \oplus e_j\)（翻转第 \(j\) 位）是 \(\{0,1\}^n\) 到自身的双射，把 \(N\) 个求和项两两配对；并且

\[(x \oplus e_j) \cdot w = x \cdot w \oplus e_j \cdot w = x \cdot w \oplus w_j = x \cdot w \oplus 1\]

所以配对的两项 \((-1)^{x \cdot w}\) 与 \((-1)^{(x \oplus e_j) \cdot w} = (-1)^{x \cdot w \oplus 1} = -(-1)^{x \cdot w}\) 恰好相互抵消，整个和为 \(0\)。

把 \(w = s \oplus z\) 代回：内层求和等于 \(N\) 当且仅当 \(z = s\)，否则为 \(0\)。因此

\[H^{\otimes n}\left(\frac{1}{\sqrt{N}} \sum_x (-1)^{s \cdot x}|x\rangle\right) = \frac{1}{N} \sum_z \left(N \cdot \delta_{s,z}\right)|z\rangle = |s\rangle\]

测量结果以概率 1 为 \(s\)。提取是精确的，无需重复运行。

经典下界的严格论证

必要性（少于 \(n\) 次查询不够）：设某算法总共查询了 \(k\) 个输入 \(x^{(1)}, \ldots, x^{(k)}\)（允许自适应——对固定的应答序列，被查询的输入集合也随之确定），它获得的全部信息只是 \(k\) 个比特 \(b_i = s \cdot x^{(i)}\)，即关于未知向量 \(s\) 的 \(k\) 个线性方程。当 \(k < n\) 时，这些方程系数张成的子空间维数至多为 \(k\)，其正交补中存在非零向量 \(u\)，满足 \(u \cdot x^{(i)} = 0\) 对所有 \(i\) 成立。于是 \(s\) 与 \(s \oplus u\) 是两个不同的隐藏串，却对所有被查询的输入给出相同应答：

\[(s \oplus u) \cdot x^{(i)} = s \cdot x^{(i)} \oplus u \cdot x^{(i)} = s \cdot x^{(i)} = b_i\]

任何确定性算法在这两个实例上的执行轨迹完全相同，必然在其中一个上出错。

对带随机性、以常数概率成功为目标的算法，同样的计数给出下界：\(k\) 次查询的答案把候选 \(s\) 限制在一个大小至少为 \(2^{n-k}\) 的仿射子空间内，且每个候选在给定答案条件下等可能，故单次输出猜对的概率不超过 \(2^{-(n-k)}\)。要达到常数成功概率，必须 \(k \geq n - O(1)\)，即仍需 \(\Theta(n)\) 次查询。

为什么经典需要 \(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\)：正交和等式 \(\sum_x (-1)^{x \cdot (s \oplus z)} = N\,\delta_{s,z}\) 正是"错误答案的概率幅两两相消、正确答案的概率幅相长叠加"的定量表述。

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

量子电路图

Bernstein-Vazirani 量子电路

\(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\]

各项的相位：

\(x\)

\(x_1 x_2 x_3\)

\(s \cdot x\)

相位

0

000

0

\(+1\)

1

001

1

\(-1\)

2

010

0

\(+1\)

3

011

1

\(-1\)

4

100

1

\(-1\)

5

101

0

\(+1\)

6

110

1

\(-1\)

7

111

0

\(+1\)

步骤 5：施加 \(H^{\otimes 3}\)。这里可以把态显式算出来：由于 \(x_1 \oplus x_3 \equiv x_1 + x_3 \pmod 2\)，有 \((-1)^{x_1 \oplus x_3} = (-1)^{x_1} \cdot (-1)^{x_3}\)，于是整个态可以按比特因子化：

\[\frac{1}{\sqrt{8}} \sum_{x_1, x_2, x_3} (-1)^{x_1}(-1)^{x_3}|x_1 x_2 x_3\rangle = \left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right) \otimes \left(\frac{|0\rangle + |1\rangle}{\sqrt{2}}\right) \otimes \left(\frac{|0\rangle - |1\rangle}{\sqrt{2}}\right) = |-\rangle|+\rangle|-\rangle\]

第 2 位上没有任何相位，所以它保持为 \(|+\rangle\)；第 1、3 位各带一个 \((-1)^{x_i}\) 因子，成为 \(|-\rangle\)。再逐位施加 \(H\)：\(H|-\rangle = |1\rangle\)、\(H|+\rangle = |0\rangle\)，因此

\[H^{\otimes 3}\,|-\rangle|+\rangle|-\rangle = |1\rangle|0\rangle|1\rangle = |101\rangle = |s\rangle\]

与一般推导的结论一致。

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

复杂度分析

经典

量子（BV）

查询次数

\(n\)

\(\mathbf{1}\)

门操作

\(O(n)\)

\(O(n)\)

测量次数

\(n\)

\(1\)

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

推广与意义

与 Deutsch-Jozsa 算法的关系

BV 的黑盒函数类（线性函数）落在 Deutsch-Jozsa 算法的承诺类之内：\(s = 0\) 时 \(f\) 是常函数（恒为 0）；\(s \neq 0\) 时 \(f\) 是平衡函数——取任一满足 \(s_j = 1\) 的位 \(j\)，配对 \(x\) 与 \(x \oplus e_j\)，则 \(f(x \oplus e_j) = f(x) \oplus s_j = f(x) \oplus 1\)，即输入两两配对、输出取反，恰有一半输入取 0、一半取 1。两个算法的量子电路完全相同；区别在于承诺更强时能提取更多信息：Deutsch-Jozsa 只需判断测量结果是否为 \(0^n\)，而在"线性"这一特例上，测量结果本身就是 \(s\)，且以概率 1 正确。

与 Simon 算法的关系

Simon 算法处理满足 \(f(x) = f(x \oplus s)\) 的函数（函数具有隐藏的异或周期 \(s\)），它把 BV 的"隐藏线性结构"换成"隐藏仿射周期结构"，需要 \(O(n)\) 次查询，但相比经典的 \(\Omega(2^{n/2})\) 次查询已有指数加速。两者连同 Shor 算法都可以纳入阿贝尔隐藏子群问题（abelian hidden subgroup problem）的统一框架，Shor 的阶查找算法正是把"叠加 + 周期函数 + 傅里叶采样"这一范式从 \(\mathbb{Z}_2^n\) 推广到循环群上的结果。

在量子学习理论中的应用

BV 算法是证明量子优势的基本构件之一。Bernstein 和 Vazirani 利用它构造了第一个相对于 oracle 具有指数分离（exponential separation）的量子复杂度结果：存在一个语言，量子多项式时间（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.