1 Deutsch-Jozsa 算法
定义一个函数 𝑓 : {0, 1}
𝑛
→ {0, 1}, 并约定它只能是下面两种类型之一
• 常函数: 对于任意输入 𝑥, 都有 𝑓 (𝑥) = 0 或者 𝑓 (𝑥) = 1
• 平衡函数: 对于一半的输入 𝑥, 有 𝑓 (𝑥) = 0, 另一半的输入 𝑥, 有 𝑓 (𝑥) = 1
希望尽可能少地调用函数 𝑓 , 来判断它是常函数还是平衡函数. 在经典计算中, 最坏情况下需要调用 2
𝑛−1
+
1 次才能确定 𝑓 的类型. 利用 Deutsch-Jozsa 算法, 只需要调用一次量子版本的函数 𝑓 , 就可以确定它的
类型, 线路图如下
.
.
.
.
.
.
.
.
.
|
0
⟩
1
𝐻
𝑈
𝑓
𝐻
|
0
⟩
2
𝐻 𝐻
.
.
.
|
0
⟩
𝑛
𝐻 𝐻
|
1
⟩
𝐻
其中 𝑈
𝑓
是 𝑓 的量子版本, 它的作用是
𝑈
𝑓
|𝑥⟩|𝑦⟩ = |𝑥⟩|𝑦 ⊕ 𝑓 (𝑥)⟩
其中
|
𝑥
⟩
是 𝑛 比特的量子态,
|
𝑦
⟩
是 1 比特的量子态. 系统的初始态为
|𝜓
0
⟩ = |0⟩
⊗𝑛
|1⟩
经过第一组 Hadamard 门之后, 系统的态变为
|𝜓
1
⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑡=0
|𝑡⟩
⊗
|0⟩ − |1⟩
√
2
=
1
√
2
𝑛+1
2
𝑛
−1
Õ
𝑡=0
(|𝑡⟩ ⊗ |0⟩ − |𝑡⟩ ⊗ |1⟩)
其中左侧的
|
𝑡
⟩
表示 𝑛 比特的量子态处于 𝑡 的二进制表示, 整个左半部分是 𝑓 (𝑥) 所有可能输入 𝑥 的均匀
叠加态. 注意到
𝑈
𝑓
|
𝑥
⟩ |
0
⟩
=
|
𝑥
⟩ |
0
⟩
, 𝑓 (𝑥) = 0
|
𝑥
⟩ |
1
⟩
, 𝑓 (𝑥) = 1
, 𝑈
𝑓
|
𝑥
⟩ |
1
⟩
=
|
𝑥
⟩ |
1
⟩
, 𝑓 (𝑥) = 0
|
𝑥
⟩ |
0
⟩
, 𝑓 (𝑥) = 1
因而
𝑈
𝑓
(|𝑡⟩ ⊗ |0⟩ − |𝑡⟩ ⊗ |1⟩) =
|𝑡⟩ ⊗ |0⟩ − |𝑡⟩ ⊗ |1⟩, 𝑓 (𝑡) = 0
|𝑡⟩ ⊗ |1⟩ − |𝑡⟩ ⊗ |0⟩ = −(|𝑡⟩ ⊗ |0⟩ − | 𝑡⟩ ⊗ |1⟩), 𝑓 (𝑡) = 1
所以
|𝜓
2
⟩ = 𝑈
𝑓
|𝜓
1
⟩ =
1
√
2
𝑛+1
2
𝑛
−1
Õ
𝑡=0
(−1)
𝑓 (𝑡 )
(|𝑡⟩ ⊗ |0⟩ − |𝑡⟩ ⊗ |1⟩) =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑡=0
(−1)
𝑓 (𝑡 )
|𝑡⟩
⊗
|0⟩ − |1⟩
√
2
此时, 函数 𝑓 的结果转移到了相位上. 后续不再对最后一个比特进行操作, 专注于前 𝑛 个比特
|𝜓
′
2
⟩
=
1
√
2
𝑛
2
𝑛
−1
Õ
𝑡=0
(−1)
𝑓 (𝑡 )
|𝑡⟩
随后让它们通过一组 Hadamard 门, 并测量这些比特是否为 |0⟩
⊗𝑛
. 考察概率
⟨0|
⊗𝑛
𝐻
⊗𝑛
|𝜓
′
2
⟩
注意到 Hadamard 算符是厄密的, 因此可以将其看作是作用在左侧的. 那么
⟨
0
|
⊗𝑛
𝐻
⊗𝑛
=
1
√
2
𝑛
2
𝑛
−1
Õ
𝑠=0
⟨
𝑠
|
因此全部比特测量为
|
0
⟩
⊗𝑛
的概率为
𝑃 = |⟨0|
⊗𝑛
𝐻
⊗𝑛
|𝜓
′
2
⟩|
2
=
1
2
𝑛
2
𝑛
−1
Õ
𝑠
=
0
2
𝑛
−1
Õ
𝑡
=
0
(−1)
𝑓 (𝑡 )
⟨𝑠|𝑡⟩
2
=
1
2
𝑛
2
𝑛
−1
Õ
𝑡
=
0
(−1)
𝑓 (𝑡 )
2
如果 𝑓 对于一半的输入为 0, 另一半为 1, 那么上式中正负项数量相等, 因而 𝑃 = 0. 如果 𝑓 对于所有输入
均为 0 或者均为 1, 那么上式中所有项符号相同, 因而 𝑃 = 1. 即
• 如果测量结果为 |0⟩
⊗𝑛
, 则 𝑓 是常函数
• 如果测量结果不为 |0⟩
⊗𝑛
, 则 𝑓 是平衡函数
2 Simon 算法
给定一个未知的奇妙函数
𝑓 : {0, 1}
𝑛
→ {0, 1}
𝑛
不过已知存在一个可爱输入 𝑠 ∈ {0, 1}
𝑛
, 使得
𝑓 (𝑥) = 𝑓 (𝑦) ⇐⇒ 𝑥 ⊕ 𝑦 = 𝑠
希望尽可能少地调用函数 𝑓 , 来找出这个可爱的 𝑠. 在经典计算中, 需要指数级别的调用次数. 利用 Simon
算法, 只需要多项式级别的调用次数, 就可以找出 𝑠. 线路图如下
𝑛 𝑛 𝑛
𝑛 𝑛
|
0
⟩
⊗𝑛
𝐻
⊗𝑛
𝑈
𝑓
𝐻
⊗𝑛
测量结果 𝑦
(𝑖)
|
0
⟩
⊗𝑛
观测值 𝑓 (𝑥)
其中 𝑈
𝑓
是 𝑓 的量子版本, 它的作用是
𝑈
𝑓
|𝑥⟩|𝑦⟩ = |𝑥⟩|𝑦 ⊕ 𝑓 (𝑥)⟩
其中的
|
𝑥
⟩
和
|
𝑦
⟩
均为 𝑛 比特的量子态. 系统的初始态为
|𝜓
0
⟩ = |0⟩
⊗𝑛
|0⟩
⊗𝑛
首先让第一个寄存器通过一组 Hadamard 门, 得到所有可能输入的均匀叠加态
|𝜓
1
⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑥=0
|𝑥⟩
⊗ |0⟩
⊗𝑛
=
1
√
2
𝑛
2
𝑛
−1
Õ
𝑥=0
(|𝑥⟩ ⊗ |0⟩
⊗𝑛
)
随后让它通过函数 𝑓 的量子版本 𝑈
𝑓
, 得到所有输入及其对应输出的均匀叠加态
|𝜓
2
⟩ = 𝑈
𝑓
|𝜓
1
⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑥=0
(|𝑥⟩ ⊗ | 𝑓 (𝑥)⟩)
此后上下两个线路再无交集, 那么测量第二个寄存器, 得到某个输出值 𝑓 (𝑥
0
), 那么第一个寄存器坍缩为
|𝜓
3
⟩ =
1
√
2
(|𝑥
0
⟩ + |𝑥
0
⊕ 𝑠⟩)
这是因为根据 𝑓 的性质, 只有 𝑥
0
和 𝑥
0
⊕ 𝑠 会映射到同一个输出 𝑓 (𝑥
0
). 随后让第一个寄存器通过另一组
Hadamard 门, 根据 Hadamard 门的作用
𝐻
⊗𝑛
|𝑥⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑦=0
(−1)
𝑥·𝑦
|𝑦⟩
其中 𝑥 · 𝑦 表示 𝑥 和 𝑦 的按位与结果的各个位之和, 那么
|𝜓
4
⟩ = 𝐻
⊗𝑛
|𝜓
3
⟩ =
1
√
2
𝑛+1
2
𝑛
−1
Õ
𝑦=0
(−1)
𝑥
0
·𝑦
+ (−1)
(𝑥
0
⊕𝑠)·𝑦
|
𝑦
⟩
注意到
(𝑥
0
⊕ 𝑠) · 𝑦 ≡ 𝑥
0
· 𝑦 + 𝑠 · 𝑦 (mod 2)
若 𝑠 · 𝑦 为奇数, 则上式中两项符号相反, 相互抵消; 所以能够留下来的只有 𝑠 · 𝑦 为偶数的项. 因而测量第
一个寄存器, 得到的结果 𝑦
(𝑖)
满足
𝑠 · 𝑦
(𝑖)
= 0 (mod 2)
重复上述过程多次, 可以得到多组满足 𝑠 · 𝑦
(𝑖)
= 0 (mod 2) 的线性方程组. 当方程组中独立方程数量达到
𝑛 − 1 时, 就可以解出唯一的 𝑠
3 Grover 搜索算法
若给定一个无序数据库, 包含 𝑁 个元素, 其中有一个特殊元素需要被找到. 特殊元素用一个函数表示
𝑓 (𝑥) =
1, 𝑥 = 𝑥
0
0, 𝑥 ≠ 𝑥
0
在经典计算中, 最坏情况下需要 𝑂(𝑁) 次查询才能找到 𝑥
0
. 利用 Grover 搜索算法, 只需要 𝑂 (
√
𝑁) 次查询
就可以找到 𝑥
0
. 线路图如下
Oracle
Diusion (Amplitude Amplication)
𝑛
|
0
⟩
⊗𝑛
𝐻
⊗𝑛
𝑈
𝑤
𝐻
⊗𝑛
𝑋
⊗𝑛
𝑍
𝑋
⊗𝑛
𝐻
⊗𝑛
Result 𝑤
|
1
⟩
𝐻
|
−
⟩
其中 𝑈
𝑤
是 𝑓 的量子版本, 它的作用是
𝑈
𝑤
|𝑥⟩|𝑦⟩ = |𝑥⟩|𝑦 ⊕ 𝑓 (𝑥)⟩
系统的初始态为
|𝜓
0
⟩ = |0⟩
⊗𝑛
|1⟩
首先经过与 Deutsch-Jozsa 算法类似的步骤, 在 𝑈
𝑤
之后, 系统的态变为
|𝜓
1
⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑥=0
(−1)
𝑓 (𝑥 )
|𝑥⟩
⊗
|0⟩ − |1⟩
√
2
由于 𝑓 (𝑥) 只有在 𝑥 = 𝑥
0
时为 1, 其他时候均为 0, 因而上式可以写成
|𝜓
1
⟩ =
1
√
2
𝑛
Õ
𝑥≠𝑥
0
|𝑥⟩ −
1
√
2
𝑛
|𝑥
0
⟩
⊗
|0⟩ − |1⟩
√
2
此后辅助比特不再参与运算, 专注于前 𝑛 个比特
|𝜓
′
1
⟩ =
1
√
2
𝑛
Õ
𝑥≠𝑥
0
|𝑥⟩ −
1
√
2
𝑛
|𝑥
0
⟩
如果将这个过程只关注前 𝑛 个比特表示为算符 𝑈
′
𝑤
, 那么它的作用是
𝑈
′
𝑤
= 𝐼 − 2|𝑥
0
⟩⟨ 𝑥
0
|
它只将目标态
|
𝑥
0
⟩
的相位取反, 而其他态保持不变. 注意到此时只有目标态的幅度变为负值, 其他态的幅
度均为正值. 为了将布居集中到目标态上, 注意到下面的算子
𝑈
𝑠
= 2|𝑠⟩⟨𝑠| − 𝐼, |𝑠⟩ =
1
√
2
𝑛
2
𝑛
−1
Õ
𝑥=0
|𝑥⟩
𝜓
′
1
可以表示为
|𝜓
′
1
⟩ = |𝑠⟩ −
2
√
2
𝑛
|𝑥
0
⟩
那么
𝑈
𝑠
|𝜓
′
1
⟩ =
2|𝑠⟩⟨𝑠| − 𝐼
|𝑠⟩ −
2
√
2
𝑛
|𝑥
0
⟩
=
1 −
4
√
2
𝑛
|𝑠⟩ +
2
√
2
𝑛
|𝑥
0
⟩
目标态的概率增加了! 更加一般地, 构造一个与
|
𝑥
0
⟩
正交的态
|
𝑠
′
⟩
=
1
√
2
𝑛
− 1
Õ
𝑥≠𝑥
0
|𝑥⟩
那么它们构成了一组二位系统的基矢, 那么
|
𝑠
⟩
可以表示为
|𝑠⟩ =
√
2
𝑛
− 1
√
2
𝑛
|𝑠
′
⟩ +
1
√
2
𝑛
|𝑥
0
⟩ = cos 𝜃
0
|𝑠
′
⟩ +sin 𝜃
0
|𝑥
0
⟩, 𝜃
0
= arcsin
1
√
2
𝑛
≈
1
√
2
𝑛
在次基矢上, 𝑈
′
𝑤
和 𝑈
𝑠
的矩阵表示分别为
𝑈
′
𝑤
=
1 0
0 −1
!
, 𝑈
𝑠
=
2 sin
2
𝜃
0
− 1 2 sin 𝜃
0
cos 𝜃
0
2 sin 𝜃
0
cos 𝜃
0
1 − 2 sin
2
𝜃
0
!
=
cos 2𝜃
0
sin 2𝜃
0
sin 2𝜃
0
−cos 2𝜃
0
!
一次迭代 𝑈
𝑠
𝑈
′
𝑤
的矩阵表示为
𝑈
𝑠
𝑈
′
𝑤
=
cos 2𝜃
0
sin 2𝜃
0
−sin 2𝜃
0
cos 2𝜃
0
!
这正是一个旋转矩阵, 它表示绕原点逆时针旋转 2𝜃
0
角度. 初态在迭代了 𝑘 次之后变为
|𝜓
′
𝑘
⟩ = cos((2𝑘 + 1)𝜃
0
)|𝑠
′
⟩ +sin((2𝑘 + 1)𝜃
0
)|𝑥
0
⟩
希望将幅度尽可能多地集中到目标态上, 那么迭代次数就是
𝑘 =
𝜋/2 − 𝜃
0
2𝜃
0
≈
𝜋
4
√
2
𝑛
注意到全空间的维度为 𝑁 = 2
𝑛
, 因而迭代次数为 𝑂(
√
𝑁). 相比于经典算法的 𝑂(𝑁), 提供了平方级别的加
速. 为了用量子门写出 𝑈
𝑠
, 注意到
|
𝑠
⟩
= 𝐻
⊗𝑛
|
0
⟩
因而
𝑈
𝑠
= 2|𝑠⟩⟨𝑠| − 𝐼 = 𝐻
⊗𝑛
(2|0⟩⟨0| − 𝐼)𝐻
⊗𝑛
所以只需要实现 2|0⟩⟨0| − 𝐼, 它的含义是保持 |0⟩ 不变, 其他态的相位取反. 这可以用多控制 Z 门实现
𝑀𝐶𝑍 |0⟩ = |0⟩, 𝑀𝐶 𝑍 |𝑥⟩ = −|𝑥⟩, 𝑥 ≠ 0
这正好与 2|0⟩⟨0| − 𝐼 的作用相反, 因而需要前后各加一个 𝑋 门把 0 态和 1 态交换
2|0⟩⟨0| − 𝐼 = 𝑋
⊗𝑛
𝑀𝐶𝑍 𝑋
⊗𝑛
即得到线路图中的扩散算符部分
4 Hadamard Test 算法
Hadamard Test 算法用于估计量子态 |𝜓⟩ 在酉算符 𝑈 作用下的期望值
⟨𝜓|𝑈|𝜓⟩
线路图如下
Ancilla:
|
0
⟩
𝐻 𝐻
System:
|
𝜓
⟩
𝑈
首先系统的初始态为
|𝜓
0
⟩ = |0⟩ ⊗ |𝜓⟩
经过第一个 Hadamard 门之后, 系统的态变为叠加态
|𝜓
1
⟩ =
1
√
2
(|0⟩ + |1⟩) ⊗ |𝜓⟩ =
1
√
2
(|0⟩ ⊗ |𝜓⟩ + |1⟩ ⊗ |𝜓⟩)
受控 𝑈 门是指当控制比特为 |1⟩ 时, 才对目标比特施加 𝑈 算符, 因而系统的态变为
|𝜓
2
⟩ =
1
√
2
(|0⟩ ⊗ |𝜓⟩ + |1⟩ ⊗ 𝑈|𝜓⟩)
随后再经过一个 Hadamard 门, 系统的态变为
|𝜓
3
⟩ =
1
2
|0⟩ ⊗ (|𝜓⟩ +𝑈|𝜓⟩) + |1⟩ ⊗ (|𝜓⟩ −𝑈 |𝜓⟩)
测量辅助比特, 得到 |0⟩ 的概率为
𝑃(0) =
1
2
(|𝜓⟩ +𝑈|𝜓⟩)
2
=
1
4
⟨𝜓|𝜓⟩ + ⟨𝜓|𝑈|𝜓⟩ + ⟨𝜓|𝑈
†
|𝜓⟩ + ⟨𝜓| 𝑈
†
𝑈|𝜓⟩
=
1
2
+
1
2
𝑅𝑒(⟨𝜓|𝑈 |𝜓⟩)
通过多次重复该过程, 可以估计出 ⟨𝜓|𝑈|𝜓⟩ 的实部. 若想估计虚部, 则需要在第一个 Hadamard 门之前,
先对辅助比特施加一个 𝑆
†
门, 即
Ancilla:
|
0
⟩
𝐻
𝑆
†
𝐻
System:
|
𝜓
⟩
𝑈
𝑆 门的作用 𝑅
𝑧
(𝜋/2), 即
𝑆|0⟩ = |0⟩, 𝑆|1⟩ = 𝑖|1⟩
其逆 𝑆
†
门的作用是转 −𝜋/2, 即
𝑆
†
|0⟩ = |0⟩, 𝑆
†
|1⟩ = −𝑖|1⟩
那么在进入受控 𝑈 门之前, 系统的态变为
|𝜓
′
1
⟩ =
1
√
2
(|0⟩ −𝑖|1⟩) ⊗ |𝜓⟩ =
1
√
2
(|0⟩ ⊗ |𝜓⟩ − 𝑖|1⟩ ⊗ |𝜓⟩)
经过受控 𝑈 门之后, 系统的态变为
|𝜓
′
2
⟩ =
1
√
2
(|0⟩ ⊗ |𝜓⟩ − 𝑖|1⟩ ⊗ 𝑈|𝜓⟩)
随后再经过一个 Hadamard 门, 系统的态变为
|𝜓
′
3
⟩ =
1
2
|0⟩ ⊗ (|𝜓⟩ −𝑖𝑈 |𝜓⟩) + |1⟩ ⊗ (|𝜓⟩ +𝑖𝑈 |𝜓⟩)
测量辅助比特, 得到 |0⟩ 的概率为
𝑃(0) =
1
2
(|𝜓⟩ −𝑖𝑈|𝜓⟩)
2
=
1
4
⟨𝜓|𝜓⟩ −𝑖⟨𝜓|𝑈 |𝜓⟩ +𝑖⟨𝜓|𝑈
†
|𝜓⟩ + ⟨𝜓| 𝑈
†
𝑈|𝜓⟩
=
1
2
+
1
2
𝐼𝑚(⟨𝜓|𝑈|𝜓⟩)
通过多次重复该过程, 可以估计出 ⟨𝜓|𝑈 |𝜓⟩ 的虚部
5 swap Test 算法
Swap Test 算法用于估计两个量子态的重叠度
|⟨𝜓|𝜙⟩|
2
线路图如下
Ancilla:
|
0
⟩
𝐻 𝐻
State 1:
|
𝜓
⟩
State 2:
|
𝜙
⟩
这实际上长得跟 Hadamard Test 算法很像, 但实际上并不是很像而是完全一样. 中间的受控门是受控
SWAP 门, 它的作用是当控制比特为 |1⟩ 时, 交换目标比特的两个量子态. 系统的初始态为
|𝜓
0
⟩ = |0⟩ ⊗ |𝜓⟩ ⊗ |𝜙⟩
这实际上可以看作是
|𝜓
0
⟩ = |0⟩ ⊗
|𝜓⟩
2
⊗ |𝜙⟩
3
按照 Hadamard Test 算法的分析过程, 最终的测量结果为 |0⟩ 的概率为
𝑃(0) =
1
2
+
1
2
𝑅𝑒(⟨𝜓| ⊗ ⟨𝜙|𝑆𝑊 𝐴𝑃|𝜓⟩ ⊗ |𝜙⟩)
注意到后半部分
⟨𝜓| ⊗ ⟨𝜙|𝑆𝑊 𝐴𝑃|𝜓⟩ ⊗ |𝜙⟩ = ⟨𝜓|𝜙⟩⟨𝜙|𝜓⟩ = |⟨𝜓|𝜙⟩|
2
