量子计算（五）——Deutsch-Jozsa算法与Simon算法

一、Deutsch算法

1.Deutsch问题与经典算法

Deutsch算法是利用量子特性实现的最简单量子算法。这个算法要解决的问题是：对于一个接受一位二进制数输入并输出一位二进制数的函数 $𝑓 (𝑥)$ ，判断它是常量的(Constant)还是平衡的(Balanced)。将其称为Deutsch问题。 ¹¹ 当函数 $𝑓 (𝑥)$ 对任意输入都得到相同输出时，称它是常量的，在这个问题中例如 $𝑓_{1} (0) = 𝑓_{1} (1) = 0$ 那么 $𝑓_{1} (𝑥)$ 就是常量的；当函数的所有输出结果一半为 $0$ 而另一半为 $1$ 时，则称它是平衡的。

这个问题在经典算法里只有一种解决方法，即分别计算 $𝑓 (0), 𝑓 (1)$ ，判断结果是否相同：

def Judge(function(bool)) -> bool:
    if (function(0) == function(1)): 
        return Constant
    else: return Balanced

这显然需要对函数计算两次才能判断函数性质。当然，“判断结果是否相同”也可以利用异或来解决，当函数为平衡函数时返回真：

def Judge(function(bool)) -> bool:
    return (function(0) ^ function(1))

2.黑箱量子门

对于量子位而言，函数的作用如下：

𝑓 (| 𝑥 ⟩) = | 𝑓 (𝑥) ⟩

²² 虽然在上面的量子电路中将函数 $𝑓 (𝑥)$ 视作一个“量子门”绘制在其中，但需要注意这甚至有极大的概率是非法的——因为它不一定是严格意义的量子门、也即酉矩阵。例如对于常量函数 $𝑓_{1} (0) = 𝑓_{1} (1) = 0$ ， $𝑓_{1} (𝑥)$ 对应的矩阵 $[\begin{matrix} 1 & 1 \\ 0 & 0 \end{matrix}]$ 就不是一个酉矩阵。为了实现Deutsch算法，我们需要对函数进行进一步的封装，使其接受两个量子位的输入，将其记为一个黑箱³³ 在英文中，会称之为Oracle，意为“神谕”。 $𝐵_{𝑓}$ ，量子电路如图 2 所示。

{𝐵_{𝑓}}_{1}^{0} | 𝑥 ⟩ | 𝑦 ⟩ = | 𝑥 ⟩ | 𝑦 \oplus 𝑓 (𝑥) ⟩

⁴⁴ 其中 $\oplus$ 是异或，也即无进位二进制加法。为什么我们要大费周章设计这样一个黑箱？这是为了生成一个合法的量子门。为了证明 $𝐵_{𝑓}$ 是一个量子门(酉矩阵)，只需要假设在量子电路中连续作用两次 $𝐵_{𝑓}$ 即可。此时第一个量子依然不变；第二个量子则是 $| 𝑦 \oplus 𝑓 (𝑥) \oplus 𝑓 (𝑥) ⟩ = | 𝑦 \oplus 0 ⟩ = | 𝑦 ⟩$ ，回到原状态。因此， $𝐵_{𝑓}$ 的逆阵、转置共轭 $𝐵^{†}$ 就是其自身。

3.Deutsch算法的实现

Deutsch算法的完整量子电路如图 3 所示。

也即可以用下列公式表示：

𝐻 [0] \cdot {𝐵_{𝑓}}_{1}^{0} \cdot 𝐻 [0, 1] \cdot | 01 ⟩

最终的判断结果由对 $0$ 号量子的测量产生。计算可知这个线路如何实现函数性质的判断：

\begin{aligned} * After action of 𝐻 [0, 1] * \\ Origin & = 𝐻 [0] \cdot {𝐵_{𝑓}}_{1}^{0} \cdot \frac{1}{2} (| 0 ⟩ + | 1 ⟩) (| 0 ⟩ - | 1 ⟩) \\ * Expand * \\ = \frac{1}{2} 𝐻 [0] \cdot {𝐵_{𝑓}}_{1}^{0} \cdot (| 00 ⟩ - | 01 ⟩ + | 10 ⟩ - | 11 ⟩) \\ * After action of 𝐵_{𝑓} * \\ = \frac{1}{2} 𝐻 [0] \cdot {| 0 ⟩ \dot{| 0 \oplus 𝑓 (0) ⟩ - | 1 \oplus 𝑓 (0) ⟩} \\ + | 1 ⟩ \dot{| 0 \oplus 𝑓 (1) ⟩ - | 1 \oplus 𝑓 (1) ⟩}} \\ * Using | 0 \oplus 𝑥 ⟩ - | 1 \oplus 𝑥 ⟩ = {(- 1)}^{𝑥 (| 0 ⟩ - | 1 ⟩)} * \\ = \frac{1}{2} 𝐻 [0] \cdot {{(- 1)}^{𝑓 (0)} | 0 ⟩ (| 0 ⟩ - | 1 ⟩) \\ + {(- 1)}^{𝑓 (1)} | 1 ⟩ (| 0 ⟩ - | 1 ⟩)} \\ = \frac{1}{2} 𝐻 [0] \cdot ({(- 1)}^{𝑓 (0)} | 0 ⟩ + {(- 1)}^{𝑓 (1)} | 1 ⟩) \cdot (| 0 ⟩ - | 1 ⟩) \\ * {In the first parenthesis, extract (- 1)}^{𝑓 (0)} * \\ = \frac{1}{2} {(- 1)}^{𝑓 (0)} 𝐻 [0] \cdot (| 0 ⟩ + {(- 1)}^{𝑓 (0) \oplus 𝑓 (1)} | 1 ⟩) (| 0 ⟩ - | 1 ⟩) \\ * After action of 𝐻 [0] * \\ * Using 𝐻 (| 0 ⟩ + {(- 1)}^{𝑥} | 1 ⟩) = \sqrt{2} | 𝑥 ⟩ * \\ = \frac{1}{\sqrt{2}} {(- 1)}^{𝑓 (0)} \cdot | 𝑓 (0) \oplus 𝑓 (1) ⟩ (| 0 ⟩ - | 1 ⟩) \end{aligned}

由最后一式可以看出， $0$ 号量子的测量结果必然为 $𝑓 (0) \oplus 𝑓 (1)$ ，也正如之前经典算法所述，此异或结果就是函数的性质！在这个算法中，我们只运行了一次线路即得到了结果。

注 1.（相位反冲）

另一个有趣的点在于，线路最后的运行结果 $0$ 号量子和 $1$ 号量子并非是纠缠的，不论测量谁都不影响另一个量子；而且，最后只有 $0$ 号量子包含我们需要的信息， $1$ 号量子则被丢弃。

如果仔细观察，Deustch算法中，在 $𝐻 [0, 1]$ 作用后， $1$ 号量子的状态为 $\frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩)$ ； $𝐵_{𝑓}$ 作用后， $1$ 号量子的状态依然为 $\frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩)$ ！此事的蹊跷之处在于，我们一开始引入黑箱量子门 $𝐵_{𝑓}$ 时，状态不变的是 $0$ 号量子， $1$ 号量子反而才是应该发生改变的！

像这种“本应改变的量子位(通常是受控位)没变、不应变的量子位(通常是控制位)反而发生改变”的现象称为相位反冲(Phase Kick-back)。这一现象会是许多量子算法的基础。

二、Deutsch-Josza算法

1.哈达玛变换再探

对于哈达玛变换我们已经知道：

{\begin{cases} 𝐻 | 0 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩) \\ 𝐻 | 1 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \end{cases}

可以合并写为：

命题 1.（单哈达玛门的计算）

\begin{aligned} 𝐻 | 𝑥 ⟩ & = \frac{1}{\sqrt{2}} (| 0 ⟩ + {(- 1)}^{𝑥} | 1 ⟩) \\ = \frac{1}{\sqrt{2}} \sum_{𝑦 = 0}^{1} {(- 1)}^{𝑥 𝑦} | 𝑦 ⟩ \end{aligned}

现在我们希望像上式最后一式那样，以求和的形式，写出 $| 𝑥 ⟩ = | 𝑥_{0} 𝑥_{1} \dots 𝑥_{𝑛 - 1} ⟩$ 被 $𝐻 [0 \sim 𝑛 - 1]$ 操作的结果。难点在于如何确定 $| 𝑦 ⟩$ 的符号。注意到单个量子哈达玛变换后 $| 0 ⟩$ 必是正的，因此当 $𝑥_{𝑘} = 0$ 时不会对符号改变作出贡献(相当于用 $0$ 乘上某个数)。当 $𝑥_{𝑘} = 1$ 时，符号就由 $| 𝑦 ⟩ = | 𝑦_{0} 𝑦_{1} \dots 𝑦_{𝑛 - 1} ⟩$ 中有多少个 $1$ 决定了。由此可以得出：

命题 2.（多哈达玛门的计算）

\begin{aligned} 𝐻 [0 \sim 𝑛 - 1] | 𝑥 ⟩ & = \frac{1}{\sqrt{2^{𝑛}}} \sum_{𝑦 = 0}^{2^{𝑛} - 1} {(- 1)}^{{\sum_{𝑖 = 0}^{𝑛 - 1} 𝑥_{𝑖} 𝑦_{𝑖}}} | 𝑦 ⟩ \\ = \frac{1}{\sqrt{2^{𝑛}}} \sum_{𝑦 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝒙 \cdot 𝒚} | 𝑦 ⟩ \end{aligned}

第二行中将指数部分的求和视作了向量点乘。

2.Deutsch-Josza算法的实现

现在我们来推广Deutsch问题。现在函数 $𝑓 (𝑥)$ 接受一个长度为 $𝑛$ 的二进制串作为输入，而依然输出一位二进制数。要求判断这个函数是常量的还是平衡的。 ⁵⁵ 显然当 $𝑛 > 1$ 时，函数可以既不是常量的也不是平衡的。为了问题的进一步讨论，应当指出我们会规定其为一个承诺问题(Promised Problem)，即承诺受到判断的函数必然是常量的或是平衡的，不存在其他状态。

类似地，我们需要将函数封装为黑箱，它对量子系统的操作是：

{𝐵_{𝑓}}_{𝑛}^{0 \sim 𝑛 - 1} | 𝑥 ⟩ | 𝑦 ⟩ = | 𝑥 ⟩ | 𝑦 \oplus 𝑓 (𝑥) ⟩

其中 $| 𝑥 ⟩$ 包含 $𝑛$ 个量子，而 $𝑦 \in {0, 1}$ 。 ⁶⁶ 值得一提的是，黑箱量子门 $𝐵_{𝑓}$ 必然是一个置换矩阵(Permutation Matrix)，即每行每列都有且只有一个 $1$ ，其余元素均为 $0$ 。这也正是 $𝐵_{𝑓}$ 是一个量子门(酉矩阵)的基础。(当然这也说明置换矩阵不一定是 $𝐵_{𝑓}$ ，因为置换矩阵的转置共轭矩阵不一定与自身相等。)

解决这个问题的算法即是Deutsch算法的推广——Deutsch-Josza算法。它使用的量子电路如图 4 与Deutsch算法几乎一致：

𝐻 [0 \sim 𝑛 - 1] \cdot {𝐵_{𝑓}}_{𝑛}^{0 \sim 𝑛 - 1} \cdot 𝐻 [0 \sim 𝑛] \cdot | 00 \dots 01 ⟩

计算可得：

\begin{aligned} * After action of 𝐻 [0 \sim 𝑛] * \\ Origin & = \frac{1}{\sqrt{2^{𝑛 + 1}}} 𝐻 [0 \sim 𝑛 - 1] \cdot {𝐵_{𝑓}}_{𝑛}^{0 \sim 𝑛 - 1} \cdot {\sum_{𝑥 = 0}^{2^{𝑛} - 1} | 𝑥 ⟩} (| 0 ⟩ - | 1 ⟩) \\ * After action of {𝐵_{𝑓}}_{𝑛}^{0 \sim 𝑛 - 1} * \\ = \frac{1}{\sqrt{2^{𝑛 + 1}}} 𝐻 [0 \sim 𝑛 - 1] \cdot {\sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝑓 (𝑥)} | 𝑥 ⟩} (| 0 ⟩ - | 1 ⟩) \\ * After action of 𝐻 [0 \sim 𝑛 - 1] * \\ = \frac{1}{\sqrt{2^{2 𝑛 + 1}}} \cdot {\sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝑓 (𝑥)} \sum_{𝑦 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝒙 \cdot 𝒚} | 𝑦 ⟩} (| 0 ⟩ - | 1 ⟩) \\ = {\sum_{𝑦 = 0}^{2^{𝑛} - 1} (\frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝑓 (𝑥) + 𝒙 \cdot 𝒚}) | 𝑦 ⟩} \cdot \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) \end{aligned}

也就是说，最后 $0 \sim 𝑛 - 1$ 号量子的状态是：

\sum_{𝑦 = 0}^{2^{𝑛} - 1} (\frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝑓 (𝑥) + 𝒙 \cdot 𝒚}) | 𝑦 ⟩

其中，计算基态 $| 0^{𝑛} ⟩$ 的振幅是：

\frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝑓 (𝑥)}

因此，当函数是常量的时，计算基态 $| 0^{𝑛} ⟩$ 的概率是：

{| \frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{0 or 1} |}^{2} = 1

而问题又是受承诺的，因此当测量结果并非全 $0$ 时，函数就必然是平衡的了。

注 2.

总结：这个算法的测量结果全部为

0

时，函数是常量的；否则是平衡的。

3.与经典算法对比

也许您在阅读Deutsch算法时会认为，量子算法计算一次相比经典算法的计算两次来说也并没有多大优势，甚至在时序上量子算法还要经过三个量子门，是完全的小题大做。但量子算法的优势需要在大规模数据前体现。例如对于推广的Deutsch问题来说，经典算法最差时、以及完全确定时需要计算 $2^{𝑛 - 1} + 1$ 次，而Deutsch-Josza算法依然只需要计算一次。

当然，从实用性来说，Deutsch问题确实不具有太大的现实意义，更像是为了彰显量子优越性刻意设计的问题。但也正因如此，我们得以见识一个设计精妙的量子算法可以产生多大的加速效果。

经典算法的解决思路是：纯随机无重复地从 $0 \sim 2^{𝑛} - 1$ 的字符串中挑选代入函数，如果出现一次计算结果与之前不同，即可确定是平衡函数；否则，以指数上升的概率认为其是常量函数；直到计算到第 $2^{𝑛 - 1} + 1$ 次即可完全确定函数性质。

三、Simon算法

1.Simon问题

Simon问题也是一个与函数有关的承诺问题。设函数 $𝑓 (𝑥)$ 接受长度为 $𝑛$ 的二进制字符串输入，输出也是长度为 $𝑛$ 的二进制串。承诺如果两个输入 $𝑠_{1}, 𝑠_{2}$ 有相同的输出即 $𝑓 (𝑠_{1}) = 𝑓 (𝑠_{2})$ ，那么两者的(按位)异或必然是 $𝑛$ 位全零字符串、或是某个特定字符串 $𝑠$ ，即：

𝑠_{1} \oplus 𝑠_{2} \in {0^{𝑛}, 𝑠}

应当注意我们允许特殊字符串 $𝑠$ 是 $0^{𝑛}$ ，此时函数是一一映射的。

这个问题要解决的是：寻找到这个特定字符串 $𝑠$ 。

2.Simon算法的实现

Simon算法使用的量子电路如图 5 和式(15) 所示。

𝐻 [0 \sim 𝑛 - 1] \cdot {𝐵_{𝑓}}_{𝑛 \sim 2 𝑛 - 1}^{0 \sim 𝑛 - 1} \cdot 𝐻 [0 \sim 𝑛 - 1] \cdot | 0^{𝑛} ⟩ | 0^{𝑛} ⟩

其中，黑箱 $𝐵_{𝑓}$ 的作用与D-J算法差不多，但现在是二进制串间的按位异或：

𝐵_{𝑓} | 𝑥 ⟩ | 𝑦 ⟩ = | 𝑥 ⟩ | 𝑓 (𝑥) \oplus 𝑦 ⟩

因此，计算算法运行过程可得：

\begin{aligned} * After action of 𝐻 [0 \sim 𝑛 - 1] * \\ Origin & = \frac{1}{\sqrt{2^{𝑛}}} 𝐻 [0 \sim 𝑛 - 1] \cdot {𝐵_{𝑓}}_{𝑛 \sim 2 𝑛 - 1}^{0 \sim 𝑛 - 1} \cdot {\sum_{𝑥 = 0}^{2^{𝑛} - 1} | 𝑥 ⟩} | 0^{𝑛} ⟩ \\ * After action of {𝐵_{𝑓}}_{𝑛 \sim 2 𝑛 - 1}^{0 \sim 𝑛 - 1} * \\ = \frac{1}{\sqrt{2^{𝑛}}} 𝐻 [0 \sim 𝑛 - 1] \cdot \sum_{𝑥 = 0}^{2^{𝑛} - 1} | 𝑥 ⟩ | 𝑓 (𝑥) ⟩ \\ * After action of 𝐻 [0 \sim 𝑛 - 1] * \\ = \frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} \sum_{𝑦 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝒙 \cdot 𝒚} | 𝑦 ⟩ | 𝑓 (𝑥) ⟩ \\ = \sum_{𝑦 = 0}^{2^{𝑛} - 1} | 𝑦 ⟩ (\frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝒙 \cdot 𝒚} | 𝑓 (𝑥) ⟩) \end{aligned}

最后我们只对 $0 \sim 𝑛 - 1$ 号量子测量。当特殊字符串 $𝑠 = 0^{𝑛}$ 时， $𝑓 (𝑥)$ 是一一映射函数，因此 ${𝑓 (𝑥)} = {𝑥}$ ——也就是说，所有计算基态 $| 𝑥 ⟩$ 都会作为态矢量 $| 𝑓 (𝑥) ⟩$ 出现，只是不一定按自然数递增顺序出现而已。因此，在 $𝑠 = 0^{𝑛}$ 的情况下对 $0 \sim 𝑛 - 1$ 号量子的测量，任意一个状态出现的概率都是 $\frac{1}{2^{𝑛}}$ 。

当 $𝑠 \neq 0^{𝑛}$ 时，那么在 $𝑓 (𝑥)$ 的值域中的任意一个输出 $𝑧$ ，应当存在且仅存在两个不同的输入 $𝑥_{𝑧 1}, 𝑥_{𝑧 2}$ 使 $𝑥_{𝑧 1} \oplus 𝑥_{𝑧 2} = 𝑠$ 。而由于按位异或是循环的，前式也能写为 $𝑥_{𝑧 2} = 𝑠 \oplus 𝑥_{𝑧 1}$ 。于是，计算任意态 $| 𝑦 ⟩$ 被测量得到的概率为：

\begin{aligned} {| \frac{1}{2^{𝑛}} \sum_{𝑥 = 0}^{2^{𝑛} - 1} {(- 1)}^{𝒙 \cdot 𝒚} | 𝑓 (𝑥) ⟩ |}^{2} \\ = & {| \frac{1}{2^{𝑛}} \sum ({(- 1)}^{{𝒙_{𝑧 1} \cdot 𝒚}} + {(- 1)}^{{𝒙_{𝑧 2} \cdot 𝒚}}) | 𝑧 ⟩ |}^{2} \\ = & {| \frac{1}{2^{𝑛}} \sum ({(- 1)}^{{𝒙_{𝑧 1} \cdot 𝒚}} + {(- 1)}^{{(𝑠 \oplus 𝒙_{𝑧 1}) \cdot 𝒚}}) | 𝑧 ⟩ |}^{2} \\ = & {| \frac{1}{2^{𝑛}} \sum {(- 1)}^{{𝒙_{𝑧 1} \cdot 𝒚}} (1 + {(- 1)}^{𝒔 \cdot 𝒚}) | 𝑧 ⟩ |}^{2} \\ = & {\begin{cases} \frac{1}{2^{𝑛 - 1}} & ,if 𝒔 \cdot 𝒚 = 0 (mod 2) \\ 0 & ,if 𝒔 \cdot 𝒚 \neq 0 (mod 2) \end{cases} \end{aligned}

也就是说，在这种情况下，测量出的态 $| 𝑦 ⟩$ 必定符合条件 $𝒔 \cdot 𝒚 = 0 (mod 2)$ 。但显然要想确定特殊字符串 $𝑠$ ，测量一次绝对是不够的—— $𝑠$ 中含有 $𝑛$ 个未知字符，按照方程理论，需要 $𝑛$ 个线性无关的方程才能完全确定(也就是 $𝑛$ 次测量)，但实际上受“二进制字符串且不是 $0^{𝑛}$ ”这个条件的限制，只需要 $𝑛 - 1$ 个线性无关的方程即可。

因此要想算得 $𝑠$ ，至少需要通过测量得到 $𝑛 - 1$ 个线性无关的计算基态。在 $𝑛 - 1$ 次测量下得到 $𝑛 - 1$ 个线性无关的计算基态的概率是：

𝑝 = \prod_{𝑘 = 1}^{+ \infty} (1 - \frac{1}{2^{𝑘}})

取对数后放缩可得：

\begin{aligned} ln 𝑝 & = \sum_{𝑘 = 1}^{+ \infty} ln (1 - \frac{1}{2^{𝑘}}) \\ \geq \sum_{𝑘 = 1}^{+ \infty} 2 ln 2 \cdot (- \frac{1}{2^{𝑘}}) \\ = - 2 ln 2 \cdot \sum_{𝑘 = 1}^{+ \infty} \frac{1}{2^{𝑘}} \\ \to - 2 ln 2 \end{aligned}

也就是 $𝑝 > \frac{1}{4}$ ，几乎三成的概率可以在 $𝑛 - 1$ 次测量下得到线性无关方程组。

使用计算机可以得到实际近似值约为：

public class Main {
    public static void main(String[] args) {
        System.out.println(Tandem(100));
    }

    public static BigDecimal Tandem(int iteration) {
        BigDecimal halve = BigDecimal.valueOf(1);
        BigDecimal result = BigDecimal.valueOf(1);
        for (int it = 1; it <= iteration; it++) {
            halve = halve.divide(BigDecimal.valueOf(2));
            result = result.multiply(BigDecimal.ONE.subtract(halve));
        }
        return result;
    }
}

--->result = 0.28878809508660242127...

当然您会说三成的概率小的离谱了，从抽卡经验来看相当于必歪呀！但如果将这 $𝑛 - 1$ 次测量再进行 $𝑚$ 次呢？那么能够得到线性无关方程组的概率就非常大了——只需要计算不能得到的概率至多为：

𝑝^{'} = {(1 - \frac{1}{4})}^{𝑚} = {(\frac{3}{4})}^{𝑚} < e^{- \frac{𝑚}{4}}

例如当将整个过程重复 $10$ 次时，不能得到线性无关方程组的概率就降为 $5.63 %$ ，几乎是必然可以解决问题的。这大抵就是量子算法与概率的魅力吧。