云林县网站建设_网站建设公司_VS Code_seo优化

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. 总结

算法步骤简记：

1. 初始：

2. 对所有 qubit 作用 Hadamard：
   

3. 调用 Oracle​：
   

4. 对前 n 个 qubit 再次作用 Hadamard：
   

5. 测量前 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 都目标在同一个辅助比特上，最终效果是：

  ​

  这正是。

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

1. CNOT：控制​，目标

2. 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 共同给态加上相位。