# 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}}$$

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$

## 理论推导

### 相位回踢的完整推导

我们将辅助比特制备为 $|-\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 量子电路](../circuits/bv-circuit.png)

$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.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)