以下内容参照微软研究院主题演讲《Quantum Computing for Computer Scientists(计算机科学家量子计算导读)》的结构进行整理和扩充的.
本篇是第六部分. 上一篇[科普] 量子计算通识 - 5
多伊奇问题 Deutsch Problem
量子计算能做什么? 有什么优势?
我们从最简单的多伊奇问题开始.
首先, 我们知道, 对于一个比特进行操作, 有四种方法: 不变, 翻转, 等 0, 等 1, 它们都可以表示成用一个矩阵相乘的模式.
这四种操作又可以根据输入输出的对比分为两种情况:
情况 A: 变量结果 variable, 不变和翻转都属于这种, 它们的输出结果可能是 0 也可能是 1. 这种变量结果也可以叫做平衡结果 Balanced, 因为结果有一半情况下是输出 0, 另一半情况下输出 1. 另外注意, 这两种操作都是可逆的, 就是说如果你知道是翻转操作并且结果输出 1, 那么就可以推算输入是 0.
情况 B: 常量结果 constant, 等 0 和等 1 都属于这种, 他们的输出结果是固定的, 永远等于 0 或者等于 1, 不会因为输入不同而不同. 这两种操作是不可逆的, 也就是说即使你知道是等 0 操作并且知道操作结果输出 0, 也不能推理出输入的数值是 0 还是 1.
现在问题是, 假设有一个函数操作 , 我们只知道它是四种操作里的一种, 但我们可以用输入输出进行测试, 那么, 要确定 属于情况 A(变量可逆)还是情况 B(常数不可逆), 我们最少做几次测试?
David Deutsc 大卫. 多伊奇
这个问题最早是英国物理学家 David Deutsch 提出来的, 当然他也提出了量子算法的解决方案.
经典计算机解决方案
用经典计算机来判断 到底是情况 A(变量结果操作)还是情况 B(常量结果操作), 必须要经过两次尝试, 第一次输入 0 观看结果, 第二次输入 1 观看结果.
第一次输入 0 输出是 0, 那么 可能是不变, 也可能是等 0.
第一次输入 0 输出是 1, 那么 可能是翻转, 也可能是等 1.
第一次输入 1 输出是 0, 那么 可能是翻转, 也可能是等 0.
第一次输入 1 输出是 1, 那么 可能是不变, 也可能是等 1.
所以, 必须至少尝试两次, 第一次输入 0, 第二次输入 1 或者相反:
, 不变, 情况 A 变量
, 等 0, 情况 B 常量
, 等 1, 情况 B 常量
, 翻转, 情况 A 变量
我们经过两次经典计算可以确定 属于变量操作或者常量操作.
虽然我们也可以确定到它属于四种操作中的哪一种, 但其实这个信息是不必要的, 又是不得已而为之的, 因为我们只需要判断变量或者常量即可.
重新组装
在量子计算中我们要求所有操作都是可逆的, 那么我们先对四种位操作进行重新布线, 也就是说设计四种可逆的量子位操作线路, 或者说四种算法. 当然, 这四种算法也必须满足实现四种操作:
在这里我们输入两个量子位 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 多伊奇算法
有了上面四种操作全新的可逆线路算法, 我们用一次测试就可以确定 是变量操作还是常量操作了.
首先我们把 当做一个未知的黑盒子, 并向两端增加一些翻转操作 (X),Hadamard 门操作(H) 和一些测量 Measure 操作(M), 组成下面的测试电路:
从图中可知, 我们的两个输入 InputA 和 InputB 都是 | 0>, 那么我们来看一下在等 0, 等 1, 不变, 翻转四种不同的操作情况下输出的结果都是什么.
在此之前, 我们先把左侧的翻转 (X) 和 Hadamard(H)处理出来:
InputA 和 InputB, 都是 | 0>, 经过 - X-H - 后得到:
假设 是等 0 操作, 那么经过 没变化, 然后经过右边的 Hadamard 门结果是, 测量结果是 1, 联合 OutputA 和 OutputB 得到 | 11>:
假设 是等 1 操作, 那么如下图, OutputA 多经历一次翻转 (X), 再经过 Hadamard 门(H) 之后到达了, 但测量结果还是 1, 联合 OutputA 和 OutputB 仍然得到 | 11>
假设 是不变操作, 那么情况会复杂一些, 我们有下图:
但 OutputA 是怎么回事? 首先我们知道这是个 CNOT 可控非门操作, 而 CNOT 就是乘以一个特别的矩阵, 我们有如下公式:
注意这里最后一步的巧妙之处在于开头的 CNOT 操作相当于把两个 的张量积转换为 和的张量积, 简化后就是:
所以有上图, OutputA 是 测量后是 | 0>, 联合 OutputA 和 OutputB 仍然得到 | 01>
假设 是翻转操作, 那么相当于比不变操作多了一个翻转, 如下图所示, 注意这里 OutputA 的翻转 (X) 操作仍然在原地, 所以最终联合 OutputA 和 OutputB 仍然得到 | 01>
综合上面四种情况, 我们得到:
等 0 操作结果是 | 11>
等 1 操作结果是 | 11>
不变操作结果是 | 01>
翻转操作结果是 | 01>
所以, 输入 InputA 和 InputB 两个都是 | 0>, 如果结果是 | 11>, 那么 就是个常量操作, 如果结果是 | 01>, 那么 就是个变量操作.
只要一次操作就完成了! 速度快了一倍!
下一篇我们再深入了解多伊奇乔扎 Deutsch-Josza 算法, 它可以针对更多量子操作实现类似的加速.
来源: http://www.jianshu.com/p/42bf4e5665ae