以下内容参照微软研究院主题演讲《Quantum Computing for Computer Scientists（计算机科学家量子计算导读）》的结构进行整理和扩充的。
本篇是第六部分。上一篇 【科普】量子计算通识-5
量子计算能做什么？有什么优势？
我们从最简单的多伊奇问题开始。
首先，我们知道，对于一个比特进行操作，有四种方法：不变，翻转，等0，等1，它们都可以表示成用一个矩阵相乘的模式。
这四种操作又可以根据输入输出的对比分为两种情况：
现在问题是，假设有一个函数操作 ，我们只知道它是四种操作里的一种，但我们可以用输入输出进行测试，那么，要确定 属于情况A（变量可逆）还是情况B（常数不可逆），我们最少做几次测试？
这个问题最早是英国物理学家David Deutsch提出来的，当然他也提出了量子算法的解决方案。
用经典计算机来判断 到底是情况A（变量结果操作）还是情况B（常量结果操作），必须要经过两次尝试，第一次输入0观看结果，第二次输入1观看结果。
所以，必须至少尝试两次，第一次输入0，第二次输入1或者相反：
我们经过两次经典计算可以确定 属于变量操作或者常量操作。
在量子计算中我们要求所有操作都是可逆的，那么我们先对四种位操作进行重新布线，也就是说设计四种可逆的量子位操作线路，或者说四种算法。当然，这四种算法也必须满足实现四种操作：
在这里我们输入两个量子位InputA和InputB，其中InputA是固定的|0>，你可以把它视为冗余的辅助输入；同样输出的OutputA是真正的操作结果，而OutputB也可以视为冗余的副产品。
为什么设计成这样的线路？先不急，我们先看在这个结构下如何实现四种可逆的量子位操作。
注意上面四个图的OutputA，分别是|0>、|1>、|x>、|﹁x>，这正对应了量子比特的四种操作。
有了上面四种操作全新的可逆线路算法，我们用一次测试就可以确定 是变量操作还是常量操作了。
首先我们把 当做一个未知的黑盒子，并向两端增加一些翻转操作（X）、Hadamard门操作（H）和一些测量Measure操作（M），组成下面的测试电路：
从图中可知，我们的两个输入InputA和InputB都是|0>，那么我们来看一下在等0、等1、不变、翻转四种不同的操作情况下输出的结果都是什么。
在此之前，我们先把左侧的翻转（X）和Hadamard（H）处理出来：
InputA和InputB，都是|0>，经过-X-H-后得到 ：
我们把这个点作为进入未知黑盒 的起点，下面用蓝色圆点表示。
但OutputA是怎么回事？首先我们知道这是个CNOT可控非门操作，而CNOT就是乘以一个特别的矩阵，我们有如下公式：
注意这里最后一步的巧妙之处在于开头的CNOT操作相当于把两个 的张量积转换为 和 的张量积，简化后就是：
所以有上图，OutputA是 测量后是|0>，联合OutputA和OutputB仍然得到|01>
综合上面四种情况，我们得到：
所以，输入InputA和InputB两个都是|0>，如果结果是|11>，那么 就是个常量操作，如果结果是|01>，那么 就是个变量操作。
只要一次操作就完成了！速度快了一倍！
下一篇： 【科普】量子计算通识-7-Deutsch算法解析
END