26、高级量子计算：算法、并行性与复杂度分析

高级量子计算：算法、并行性与复杂度分析

1. 简单量子算法介绍

1.1 Bernstein–Vazirani 算法

Bernstein–Vazirani 算法模拟了由小电路构建的系统的行为，每个小电路对应于 u 的每一位。从这个角度看，该电路能保证量子比特达到 |u⟩ 状态。这种解释不涉及量子叠加或“对所有可能输入进行计算”，相对简单易懂。

1.2 Simon 问题

Simon 问题是在给定一个二对一函数 f （满足 f(x) = f(x ⊕ a) 对所有 x 成立）的情况下，找出隐藏字符串 a。与 Simon 提出的方法（需要 O(n) 次调用 Uf 以及额外的 O(n²) 步来识别 a）相比，传统算法的复杂度限制在 O(2ⁿ/²)。受 Simon 算法的启发，后来出现了现在被称为 Shor 算法的因式分解技术，Shor 算法和 Simon 的自动化系统有相当大的重叠。

通过创建叠加态可以找到 a。当从寄存器右侧读取数据时，可以推断出左侧寄存器的值。若使用 Walsh–Hadamard 变换 W，有如下计算：
[
\begin{align}
W\left(\frac{1}{\sqrt{2}}(\vert x_0\rangle + \vert x_0 \oplus a\rangle)\right) &= \frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2^n}}\sum_y ((-1)^{x_0\cdot y} + (-1)^{(x_0 \oplus a)\cdot y})\vert y\rangle\right)\
&= \frac{