Bernstein-Vazirani 算法

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

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

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

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

$s\cdot x={⨁}_{i=1}^n{s}_i\wedge x_i=(s_1{x}_1+s_2{x}_2+\cdots +s_n{x}_n)\mathrm{mod}2$

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

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

$f_s(x)=s\cdot x(\mathrm{mod}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⟩|y⟩=|x⟩|y\oplus f_s(x)⟩$

当辅助比特处于 $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ 时，利用 $f_s(x)\in \{0,1\}$ 可以算出：

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

即辅助比特保持不变，而输入寄存器获得了一个依赖于 $s\cdot x$ 的相位 $(-1{)}^{s\cdot x}$。逐项计算的完整过程见下文”相位回踢的完整推导”。这个相位编码了 $s$ 的全部信息。

算法步骤

电路构造

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

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

$|0⟩\stackrel{X}{\to }|1⟩\stackrel{H}{\to }|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$

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

$|0{⟩}^{\otimes n}\stackrel{H^{\otimes n}}{\to }\frac{1}{\sqrt{2^n}}{\sum }_{x\in \{0,1{\}}^n}|x⟩$

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

$\frac{1}{\sqrt{2^n}}{\sum }_x|x⟩|-⟩\stackrel{U_{f_s}}{\to }\frac{1}{\sqrt{2^n}}{\sum }_x(-1{)}^{s\cdot x}|x⟩|-⟩$

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

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

理论推导

相位回踢的完整推导

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

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

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

由于 $U_{f_s}$ 是线性的，我们把它作用到 $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ 上，两个分量分别计算：

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

现在按 $f_s(x)$ 的取值分两种情况代入：

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

两种情况可以统一写成 $(-1{)}^{f_s(x)}|x⟩|-⟩$：$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⟩$ 施加 $H^{\otimes n}$。整个推导只用两件事实：单比特恒等式 $H|0⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}$、$H|1⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$，以及 $H^{\otimes n}$ 的线性性。把它们合起来就得到 Hadamard 变换的通用公式：

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

（验证：右端对每个分量比特恰好贡献 $(-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⟩\right)\stackrel{\text{线性性}}{=}\frac{1}{\sqrt{N}}{\sum }_x(-1{)}^{s\cdot x}\cdot \frac{1}{\sqrt{N}}{\sum }_z(-1{)}^{x\cdot z}|z⟩=\frac{1}{N}{\sum }_x{\sum }_z(-1{)}^{s\cdot x}(-1{)}^{x\cdot z}|z⟩$

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

$=\frac{1}{N}{\sum }_z\left({\sum }_x(-1{)}^{s\cdot x}(-1{)}^{x\cdot z}\right)|z⟩$

接下来合并指数。由于 $(-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)(\mathrm{mod}2)$

（逐位验证：${⨁}_i{x}_i{s}_i$ 与 ${⨁}_i{x}_i{z}_i$ 异或，等于 ${⨁}_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},w\in \{0,1{\}}^n$

• 若 $w=0$：每一项都是 $(-1{)}^0=1$，共 $N$ 项，和为 $N$。
• 若 $w\ne 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⟩\right)=\frac{1}{N}{\sum }_z\left(N\cdot {\delta }_{s,z}\right)|z⟩=|s⟩$

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

经典下界的严格论证

必要性（少于 $n$ 次查询不够）：设某算法总共查询了 $k$ 个输入 $x^{(1)},\dots ,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\ge n-O(1)$，即仍需 $\Theta (n)$ 次查询。

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

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

量子计算中，$H^{\otimes n}$ 将所有 $2^n$ 个输入 $x$ 的叠加态”打包”到一次查询中。oracle 对叠加态的响应同时”编码”了 $s$ 在所有方向上的内积信息。第二次 $H^{\otimes n}$ 通过全局干涉将这些信息”解码”回计算基态 $|s⟩$：正交和等式 ${\sum }_x(-1{)}^{x\cdot (s\oplus z)}=N{\delta }_{s,z}$ 正是”错误答案的概率幅两两相消、正确答案的概率幅相长叠加”的定量表述。

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

量子电路图

![Bernstein-Vazirani 量子电路](../assets/circuits/b

$U_f$ 作用为 $|x⟩|y⟩\mapsto |x⟩|y\oplus (s\cdot x)⟩$，可通过 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⟩|0⟩$

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

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

$|000⟩\stackrel{H^{\otimes 3}}{\to }\frac{1}{\sqrt{8}}{\sum }_{x=0}^7|x⟩$

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

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

各项的相位：

$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(\mathrm{mod}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⟩=\left(\frac{|0⟩-|1⟩}{\sqrt{2}}\right)\otimes \left(\frac{|0⟩+|1⟩}{\sqrt{2}}\right)\otimes \left(\frac{|0⟩-|1⟩}{\sqrt{2}}\right)=|-⟩|+⟩|-⟩$

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

$H^{\otimes 3}|-⟩|+⟩|-⟩=|1⟩|0⟩|1⟩=|101⟩=|s⟩$

与一般推导的结论一致。

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

复杂度分析

	经典	量子（BV）
查询次数	$n$	$1$
门操作	$O(n)$	$O(n)$
测量次数	$n$	$1$

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

推广与意义

与 Deutsch-Jozsa 算法的关系

BV 的黑盒函数类（线性函数）落在 Deutsch-Jozsa 算法的承诺类之内：$s=0$ 时 $f$ 是常函数（恒为 0）；$s\ne 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.

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch04-classic-algorithms/bernstein-vazirani-algorithm-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议