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，对应
)
5. 为什么经典查询需要 n 次？
经典只能输入得到
。
要确定，需选取
个线性无关的
，例如：
…
每个查询得到的一个比特，所以需要
次。
6. 量子一次查询的原因
量子可以输入叠加态：
Oracle 一次作用在叠加态上，同时对所有计算
并编码为相位
。
然后通过 Hadamard 变换把相位模式 变成
。
Hadamard 变换在这里起到二进制傅里叶变换的作用，把线性相位的叠加变成单个基态。
总结
的具体实现是,对每个满足
的比特 i，在辅助比特上加一个 CNOT 门（控制位是第 i 个 qubit）。当辅助比特初始化为
时，这些 CNOT 共同给态
加上相位
。
