当前位置：首页 > news >正文

Bernstein–Vazirani 算法的原理

news 2026/5/12 5:57:00

1. 原理

1.1. 问题定义

有一个隐藏的二进制字符串，有一个黑盒（Oracle）实现函数：，其中是按位点乘模 2（奇偶性）。

经典上，如果只能通过输入得到，那么需要 n 次查询才能确定（每次查询确定一个比特，例如输入在第 j 位为 1 可以得到）。

Bernstein–Vazirani 算法用量子计算，只用 1 次查询就得到。

1.2. 量子 Oracle 的实现

我们实现一个量子门满足：

其中是 n qubit 寄存器，是 1 qubit 辅助寄存器。

1.3. 算法步骤

步骤 1：初始化

第一寄存器（n 个 qubit）：
第二寄存器（1 个 qubit）：

系统初态：

步骤 2：在辅助比特和输入寄存器上加 Hadamard 门

对每个 qubit 作用：

我们知道：

所以：

步骤 3：调用 Oracle

因为：

这里。

验证：
若：
若：

所以：

代入：

关键点：辅助比特依然是态，没有被纠缠，所以我们可以只看第一寄存器状态：

这个态称为s 的 Hadamard 基编码态（类似傅里叶对偶）。

步骤 4：对第一寄存器再作用 H^{\otimes n}H⊗n

回忆 Hadamard 门的性质：

逆变换相同（因为是自逆）：

交换求和顺序：

步骤 5：利用正交性

对于二进制向量，有恒等式：

其中是 n qubit 向量，当且仅当，否则为 0。

这里，所以：

即只有的那一项系数为 1，其它为 0。

因此：

步骤 6：测量

测量第一寄存器的 n 个 qubit，得到结果即为（确定性的，不是概率性的），因为量子态正好是。

1.4. 总结

算法步骤简记：

初始：
对所有 qubit 作用 Hadamard：
调用 Oracle：
对前 n 个 qubit 再次作用 Hadamard：
测量前 n 个 qubit，得到。

1.5. 与 Deutsch–Jozsa 的区别

Deutsch–Jozsa：区分常数函数与平衡函数，也需要 1 次量子查询（经典最坏次）。
Bernstein–Vazirani：找到一个隐藏的二进制字符串，经典需要 n 次查询，量子 1 次。
BV 可以视为 DJ 的一个特例（但目标不同）。

最终，BV 算法的量子加速来自于量子并行 + 相位反冲 + 量子傅里叶（Hadamard）变换的配合，让 Oracle 一次调用就在叠加态中标记所有的相位，再通过 Hadamard 变换把相位信息变成基态。

2. 深入

我们来具体构造，让它实现。

2.1. 函数定义

给定一个固定的二进制字符串，其中。
定义：

这是线性函数（模 2 加法）。

2.2. 量子 Oracle 形式

我们需要一个幺正算符 U_fUf 使得：

对于 BV 算法，辅助比特初始为时会触发相位反冲，使得：

所以对第一寄存器来说，在这种特殊情况下表现为一个相位 Oracle：

2.3. 电路构造

情况 1：只有一个 1（比如，第 j 位为 1）

那么。

实现方式：

如果且其它位，则只需在辅助比特上加一个受控于第 j 个 qubit 的 CNOT。

电路：

这就是 CNOT 门，控制位是第 j 个 qubit，目标位是辅助比特。

情况 2：一般有多个 1

例如，则（假设 n=3）。

实现方法：

对于每个 i，如果，就对辅助比特做一个CNOT，控制位是第 i 个 qubit。
因为这些 CNOT 都目标在同一个辅助比特上，最终效果是：

这正是。

例子：
电路（第一寄存器，辅助比特）：

CNOT：控制，目标
CNOT：控制，目标
（因为不参与）

检查对的效果

辅助比特初始为。

CNOT 门作用在目标为时的性质：
控制比特，目标比特：

因为是 X 的本征值为的本征态：

所以：

即，控制比特为时，整个态乘上。

对于多个 CNOT（都目标在同一辅助比特上），每个 CNOT 的相位因子是当。
总的相位因子是：

这正是我们要的相位 Oracle。

4. 完整电路图（BV 算法）

以为例：

┌───┐ ┌───┐ q0: |0>┤ H ├──■───────┤ H ├─── M ───> s1 ├───┤ │ ├───┤ q1: |0>┤ H ├──┼───────┤ H ├─── M ───> s2 ├───┤ │ ├───┤ q2: |0>┤ H ├──┼──■────┤ H ├─── M ───> s3 ├───┤┌─┴─┐│ ┌──┴──┐ q3: |1>┤ H ├┤ X ├┤ ├─ X ─┤ └───┘└───┘│ └─────┘ └───────

(注：q3 是辅助比特，初始，经过 H 变成；两个 CNOT 的控制分别是 q0 和 q2，目标都是 q3，对应)