【科普】量子计算通识-6-Deutsch多伊奇算法

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

以下内容参照微软研究院主题演讲《Quantum Computing for Computer Scientists（计算机科学家量子计算导读）》的结构进行整理和扩充的。
本篇是第六部分。上一篇【科普】量子计算通识-5

多伊奇问题Deutsch Problem

量子计算能做什么？有什么优势？
我们从最简单的多伊奇问题开始。

首先，我们知道，对于一个比特进行操作，有四种方法：不变，翻转，等0，等1，它们都可以表示成用一个矩阵相乘的模式。

$f(x)=x$
$\begin{pmatrix}1,0\\0,1\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0 \qquad \begin{pmatrix}1,0\\0,1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}0\\1\end{pmatrix}=1$
$f(x)=﹁x$
$\begin{pmatrix}0,1\\1,0\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}0\\1\end{pmatrix}=1 \qquad \begin{pmatrix}0,1\\1,0\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0$
$f(x)=0$
$\begin{pmatrix}1,1\\0,0\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0 \qquad \begin{pmatrix}1,1\\0,0\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}= \begin{pmatrix}1\\0\end{pmatrix}=0$
$f(x)=1$

这四种操作又可以根据输入输出的对比分为两种情况：

情况A：变量结果variable，不变和翻转都属于这种，它们的输出结果可能是0也可能是1。这种变量结果也可以叫做平衡结果Balanced，因为结果有一半情况下是输出0，另一半情况下输出1。另外注意，这两种操作都是可逆的，就是说如果你知道是翻转操作并且结果输出1，那么就可以推算输入是0。
情况B：常量结果constant，等0和等1都属于这种，他们的输出结果是固定的，永远等于0或者等于1，不会因为输入不同而不同。这两种操作是不可逆的，也就是说即使你知道是等0操作并且知道操作结果输出0，也不能推理出输入的数值是0还是1。

现在问题是，假设有一个函数操作 $f'$ ，我们只知道它是四种操作里的一种，但我们可以用输入输出进行测试，那么，要确定 $f'$ 属于情况A（变量可逆）还是情况B（常数不可逆），我们最少做几次测试？

David Deutsc大卫·多伊奇

这个问题最早是英国物理学家David Deutsch提出来的，当然他也提出了量子算法的解决方案。

经典计算机解决方案

用经典计算机来判断 $f'$ 到底是情况A（变量结果操作）还是情况B（常量结果操作），必须要经过两次尝试，第一次输入0观看结果，第二次输入1观看结果。

第一次输入0输出是0，那么 $f'$ 可能是不变，也可能是等0。
第一次输入0输出是1，那么 $f'$ 可能是翻转，也可能是等1。
第一次输入1输出是0，那么 $f'$ 可能是翻转，也可能是等0。
第一次输入1输出是1，那么 $f'$ 可能是不变，也可能是等1。

所以，必须至少尝试两次，第一次输入0，第二次输入1或者相反：

$0\to0,1\to1\quad\Rightarrow f(x)=x$ ，不变，情况A变量
$0\to0,1\to0\quad\Rightarrow f(x)=0$ ，等0，情况B常量
$0\to1,1\to1\quad\Rightarrow f(x)=1$ ，等1，情况B常量
$0\to1,1\to0\quad\Rightarrow f(x)=﹁x$ ，翻转，情况A变量

我们经过两次经典计算可以确定 $f'$ 属于变量操作或者常量操作。

虽然我们也可以确定到它属于四种操作中的哪一种，但其实这个信息是不必要的，又是不得已而为之的，因为我们只需要判断变量或者常量即可。

重新组装

在量子计算中我们要求所有操作都是可逆的，那么我们先对四种位操作进行重新布线，也就是说设计四种可逆的量子位操作线路，或者说四种算法。当然，这四种算法也必须满足实现四种操作：

在这里我们输入两个量子位InputA和InputB，其中InputA是固定的|0>，你可以把它视为冗余的辅助输入；同样输出的OutputA是真正的操作结果，而OutputB也可以视为冗余的副产品。

为什么设计成这样的线路？先不急，我们先看在这个结构下如何实现四种可逆的量子位操作。

等0操作线路，直接把InputA(|0>)输出到OuputA，这就确保了OutputA固定为|0>；而至于冗余的OutputB也直接连接到InputB即可。如下图：
等1操作线路，和等0线路差不多，把InputA线路上面添加一个非门就可以确保OutputA固定为|1>了。如下图：

不变操作线路，这个就有点复杂了，注意这里是个CNOT可控非门，InputB是控制位，InputA是目标被控位。所以，如果InputB是|0>，那么InputA
穿过连线不变输出OutputA的就还是|0>，而正好和控制位InputB相同；如果InputB是|0>是|1>，那么InputA的|0>穿过连线被翻转输出OutputA就是|1>，也正好和控制位InputB相同。

翻转操作线路，只要在不变操作的基础上增加一个翻转操作就可以了。

注意上面四个图的OutputA，分别是|0>、|1>、|x>、|﹁x>，这正对应了量子比特的四种操作。

Deutsch多伊奇算法

有了上面四种操作全新的可逆线路算法，我们用一次测试就可以确定 $F'$ 是变量操作还是常量操作了。

首先我们把 $F'(x)$ 当做一个未知的黑盒子，并向两端增加一些翻转操作（X）、Hadamard门操作（H）和一些测量Measure操作（M），组成下面的测试电路：

从图中可知，我们的两个输入InputA和InputB都是|0>，那么我们来看一下在等0、等1、不变、翻转四种不同的操作情况下输出的结果都是什么。

在此之前，我们先把左侧的翻转（X）和Hadamard（H）处理出来：

InputA和InputB，都是|0>，经过-X-H-后得到 $\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}$ ：

我们把这个点作为进入未知黑盒 $F'$ 的起点，下面用蓝色圆点表示。

假设 $F'$ 是等0操作，那么经过 $F'(x)$ 没变化，然后经过右边的Hadamard门结果是 $\begin{pmatrix}0\\ 1\end{pmatrix}$ ，测量结果是1，联合OutputA和OutputB得到|11>：
假设 $F'$ 是等1操作，那么如下图，OutputA多经历一次翻转（X），再经过Hadamard门（H）之后到达了 $\begin{pmatrix}0 \\-1\end{pmatrix}$ ，但测量结果还是1，联合OutputA和OutputB仍然得到|11>

假设 $F'$ 是不变操作，那么情况会复杂一些，我们有下图：

但OutputA是怎么回事？首先我们知道这是个CNOT可控非门操作，而CNOT就是乘以一个特别的矩阵，我们有如下公式：

$\begin{align} &C\begin{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{pmatrix}=C\begin{pmatrix} \frac{1}{2}\\\frac{-1}{2}\\\frac{-1}{2}\\\frac{1}{2}\\ \end{pmatrix}\\ &=\frac{1}{2}\begin{pmatrix}1,0,0,0\\0,1,0,0\\0,0,0,1\\0,0,1,0\end{pmatrix} \begin{pmatrix}1\\-1\\-1\\1\end{pmatrix}\\ &=\frac{1}{2} \begin{pmatrix}1\\-1\\1\\-1\end{pmatrix}= \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{align}$
注意这里最后一步的巧妙之处在于开头的CNOT操作相当于把两个 $\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}$ 的张量积转换为 $\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}$ 和 $\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}$ 的张量积，简化后就是：

$C\begin{pmatrix} \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix} \end{pmatrix}=\begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{pmatrix}\otimes \begin{pmatrix}\frac{1}{\sqrt{2}}\\\frac{-1}{\sqrt{2}}\end{pmatrix}$

所以有上图，OutputA是 $\begin{pmatrix}1\\ 0\end{pmatrix}$ 测量后是|0>，联合OutputA和OutputB仍然得到|01>

假设 $F'$ 是翻转操作，那么相当于比不变操作多了一个翻转，如下图所示，注意这里OutputA的翻转（X）操作仍然在原地，所以最终联合OutputA和OutputB仍然得到|01>

综合上面四种情况，我们得到：

等0操作结果是|11>
等1操作结果是|11>
不变操作结果是|01>
翻转操作结果是|01>

所以，输入InputA和InputB两个都是|0>，如果结果是|11>，那么 $F'$ 就是个常量操作，如果结果是|01>，那么 $F'$ 就是个变量操作。

只要一次操作就完成了！速度快了一倍！

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

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

每个人的智能新时代

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

END

最后编辑于：2019.08.07 20:06:40

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,332评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,508评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,812评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,607评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,728评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,919评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,071评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,802评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,256评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,576评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,712评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,389评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,032评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,798评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,026评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,473评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,606评论 2赞 350