【科普】量子计算通识-7-Deutsch算法解析

作者: zhyuzh3d | 来源:发表于2019-08-06 23:08 被阅读18次

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
更多相关文章请点击【量子计算通识】
上一篇：【科普】量子计算通识-6

这一篇我们来看一下多伊奇算法是怎么推导出来的。

多伊奇问题

我们用 $x\in \{0,1\}^n$ 表示 $x$ 是由0或1组成的任意 $n$ 位二进制数，比如 $n=3$ 位的011、 $n=7$ 位的1010011。

我们又知道对于单比特的四种操作可以分为两类：

常量操作constant：等0，等1；
平衡操作balanced：不变，翻转。

更多参考这里：【科普】量子计算通识-2-四种操作与乘积态

综合上面两个情况，我们就可以描述为， $\forall x \in \{0,1\}^n$ ，对于0和1组成的任意 $n$ 位长度二进制数的两种操作：

Constant：
$f(x)=0\quad或\quad f(x)=0$
Balanced：
$50\%情况 $f(x)=0\quad 另外50\%情况 f(x)=1$

多伊奇的问题就是，如果有一个符合以上条件的未知函数，那么如何尝试最少且足够的次数，来确定它是Constant操作还是Balanced操作。

经典计算机解法

$n$ 位2进制最多表示 $2^n$ 个数字，比如2位的00、01、10、11共有 $2^2=4$ 种，可以表示十进制的0 ~ 3；同样3位的000、001、010、011、100、101、110、111共可以表示0 ~ 7，即 $2^3=8$ 种；同样8位可以表示 $2^8=256$ 。

所以，对于经典计算机来说，需要尝试 $2^n*\frac{1}{2}+1$ 次（也就是一半多一次），才能确保足够可以判断未知函数属于哪一种，因为前提已经承诺，如果是Balanced类型，那么一半多一次恰好刚刚超过50%，如果这么多情况的结果都是相同的，那么它就是Constant类型操作（因为Constant类型操作所有结果都一样），否则就是Balanced类型操作。

这就好比一共8张卡片，要么都一样颜色，要么黑白各一半。这时我们只要最多翻开5张，就能知道属于那种情况了。

量子计算解法

如前面文章所述，在量子计算机中，只需要一次尝试就可以做出准确判断。当然我们要进行一些特殊处理。

图中的符号 $\Psi$ 读作|p’sai|

首先我们需要设计一个电路 $U$ ，它包含我们需要进行判断的函数 $f(x)$ ，可以说是我们在 $f(x)$ 的基础上又增加了一些处理使其成为函数 $U$ 。

$U$ 的作用就是可以传入一些量子比特，然后输出另外一些比特量子比特，并且可以让我们从输出的量子比特中一眼就可以看出其中 $f(x)$ 是Constant操作还是Balanced操作。

听上去这个 $U$ 电路一定很难设计，实际却是不难，它只要满足能够把 $|x>|y$ 映射成为 $|x>|y\oplus f(x)>$ 即可：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

这里的圆圈加号 $\oplus$ 的意思是异或，即：

$0\oplus 0=0$

$1\oplus 1=0$

$1\oplus 0=1$

$0\oplus 1=1$

异或即相同得0，相异得1。这里有些有趣的规律：

异或看起来和CNOT门很像，第一位是0的结果和第二位相同，第一位是1的结果和第二位相反。
两位顺序颠倒也能成立，第二位是0的时候，结果和第一位相同，第二位是1的时候，结果和第一位相反。

关于CNOT门，参照【科普】量子计算通识-3-CNOT可控非门

总之我们先记住 $U$ 操作就是把输入的两个量子位变成输出的另外两个量子位，输出中的后一位是第二个输入位和 $f$ 函数输入第一位的异或结果：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

实际上我们只要根据输出的 $|x>$ 就可以判断出 $f(x)$ 属于Constant还是Balanced操作，下面我们进行推理演算 $n=1$ 即2个比特位的情况。

计算Hadamard之后的 $\Psi_1$

如图，我们输入两个量子比特，一个0一个1，所以
$\Psi_0=|0>|1>$

下面来计算两个比特分别经过Hadamard门之后的 $\Psi_1$ 。

关于哈达玛门，相当于乘以一个特殊矩阵，即 $H=\frac{1}{\sqrt{2}}\begin{pmatrix}1,1\\1,-1\end{pmatrix}$ ，即 $|0>$ 变为 $\frac{|0>+|1>}{\sqrt{2}}$ ，即 $|1>$ 变为 $\frac{|0>-|1>}{\sqrt{2}}$ ，更多请参照【科普】量子计算通识-5-哈达玛门与单位圆状态机

$\begin{align} \Psi_1&=H|0>\otimes H|1>=(\frac{|0>+|1>}{\sqrt{2}})\otimes (\frac{|0>-|1>}{\sqrt{2}})\\ &=\frac{1}{2}(|0>+|1>)(|0>- |1>) \end{align}$

计算U之后的 $\Psi_2$

针对函数 $U$ ，由于我们有：

$U:|x>|y>\Rightarrow|x>|y\oplus f(x)>$

所以经过 $U$ 把 $|x>|y>$ 替换为 $|x>|y\oplus f(x)>$ 之后的 $\Psi_1$ 就变为 $\Psi_2$ ：

$\begin{align} \Psi_1&=\frac{1}{2}(|0>+|1>)(|0>-|1>)\\ &=\frac{1}{2}(|0>|0>-|0>|1>+|1>|0>-|1>|1>)\\ \end{align}$

$\begin{align} \Psi_2&=U:\Psi_1\\ &=\frac{1}{2}(|0>|0\oplus f(0)>-|0>|1\oplus f(0)>+|1>|0\oplus f(1)>-|1>|1\oplus f(1)>)\\ &=\frac{1}{2}(|0>(|0\oplus f(0)>-|1\oplus f(0)>)+|1>(|0\oplus f(1)>-|1\oplus f(1)>)) \end{align}$

我们注意到按照约定， $f(0)$ 只能取0或1，那么

当 $f(0)=0$ 时， $(-1)^{f(0)}=1$ ，并且有：
$|0\oplus f(0)>-|1\oplus f(0)>=|0\oplus 0>-|1\oplus 0>=|0>-|1>=(-1)^{f(0)}(|0>-|1>)$

当 $f(0)=1$ 时， $(-1)^{f(0)}=-1$ ，并且有：
$|0\oplus f(0)>-|1\oplus f(0)>=|0\oplus 1>-|1\oplus 1>=|1>-|0>=(-1)^{f(0)}(|0>-|1>)$

结合这两种情况，一定有：
$|0\oplus f(0)>-|1\oplus f(0)>=(-1)^{f(0)}(|0>-|1>)$

同样的道理， $f(1)$ 也可以等于0或1，所以也会有：
$|0\oplus f(1)>-|1\oplus f(1)>=(-1)^{f(1)}(|0>-|1>)$

把这两个式子带入 $\Psi_2$ 得到：

$\begin{align} \Psi_2&=\frac{1}{2}(|0>(|0\oplus f(0)>-|1\oplus f(0)>)+|1>(|0\oplus f(1)>-|1\oplus f(1)>))\\ &=\frac{1}{2}((-1)^{f(0)}|0>(|0>-|1>)+(-1)^{f(1)}|1>(|0>-|1>))\\ &=\frac{1}{2}((-1)^{f(0)}|0>+(-1)^{f(1)}|1>)(|0>-|1>)\\ \end{align}$

计算U之后的 $\Psi_3$

对 $\Psi_2$ 乘以Hadamard矩阵，即 $|0>$ 变为 $\frac{|0>+|1>}{\sqrt{2}}$ ，即 $|1>$ 变为 $\frac{|0>-|1>}{\sqrt{2}}$ ，这就得到 $\Psi_3$ 。注意如图所示，是整体进行操作而不是每一位分别Hadamard操作：

$\begin{align} \Psi_3&=\frac{1}{2}((-1)^{f(0)}|0>+(-1)^{f(1)}|1>)(|0>-|1>)\\ &=\frac{1}{2}((-1)^{f(0)}\frac{|0>+|1>}{\sqrt{2}}+(-1)^{f(1)}\frac{|0>-|1>}{\sqrt{2}})(|0>-|1>)\\ &=((-1)^{f(0)}\frac{|0>+|1>}{2}+(-1)^{f(1)}\frac{|0>-|1>}{2})(\frac{|0>-|1>}{\sqrt{2}})\\ &=(\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>)(\frac{|0>-|1>}{\sqrt{2}})\\ \end{align}$

测量结果

$\Psi_3$ 式子有点长，但我们只关注前面括号内的部分，也就是 $\Psi_3$ 要被 $M$ 测量的部分：

$\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>$

注意 $|0>$ 和 $|1>$ 对应系数的两个分母实际是A+B和A-B的格式，那么假设 $f(x)$ 是Constant即 $f(0)=f(1)=0$ 那么这个结果就是：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f( 0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{(-1)^0+(-1)^0}{2}|0>+\frac{(-1)^0-(-1)^0}{2}|1>\\ &=\frac{2}{2}|0>+\frac{0}{2}|1>\\ &=|0>\\ \end{align}$

如果 $f(0)=f(1)=1$ ，那么结果也类似的：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{(-1)^1+(-1)^1}{2}|0>+\frac{(-1)^1-(-1)^1}{2}|1>\\ &=\frac{-2}{2}|0>+\frac{0}{2}|1>\\ &=-|0>\\ \end{align}$

对于 $M$ 测量操作求平方计算结果来说， $|0>$ 和 $-|0>$ 结果都是0。

关于测量请参照这里【科普】量子计算通识-4-量子位

但是，如果 $f(x)$ 是个Balanced操作，即 $f(0)=1-f(1)$ 结果会怎样？

如果 $f(0)=1$ ， $f(1)=0$ ，那么：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{-1+1}{2}|0>+\frac{-1-1}{2}|1>\\ &=-|1>\\ \end{align}$

如果 $f(0)=0$ ， $f(1)=1$ ，那么：

$\begin{align} &\frac{(-1)^{f(0)}+(-1)^{f(1)}}{2}|0>+\frac{(-1)^{f(0)}-(-1)^{f(1)}}{2}|1>\\ &=\frac{1-1}{2}|0>+\frac{1-(-1)}{2}|1>\\ &=|1>\\ \end{align}$

综上，如果我们最后 $M$ 测量的结果是0，那么 $f(x)$ 一定是Constant操作，如果我们最后 $M$ 测量的结果是1，那么 $f(x)$ 一定是Balanced操作。

这里只针对 $n=1$ ，也就是两个量子位的计算，后面我们来推导多个量子位的情况。

欢迎关注我的专栏( つ•̀ω•́)つ【人工智能通识】
更多相关文章请点击【量子计算通识】

每个人的智能新时代

如果您发现文章错误，请不吝留言指正；
如果您觉得有用，请点喜欢；
如果您觉得很有用，欢迎转载~

END

【科普】量子计算通识-7-Deutsch算法解析

多伊奇问题

经典计算机解法

量子计算解法

计算Hadamard之后的 $\Psi_1$

计算U之后的 $\Psi_2$

计算U之后的 $\Psi_3$

测量结果

每个人的智能新时代

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

人工智能通识

自然科普

量子计算