金刚石量子计算体系简述6：Deutsch-Jozsa算法-金刚石原子间什么力
多公式预警！
对于量子计算是全球各国在新科技革命背景下的重要竞争领域，也是国内各高校、科研机构竞相布局的战略性科技创新前沿领域。利用量子力学的叠加和纠缠，量子计算具有经典计算不可比拟的强大计算功能，因此量子计算研究具有重要的科学意义和战略意义。Deutsch-Jozsa算法是最经典的量子算法之一，解决的是判断函数类型的问题，证明量子计算在解决某些问题时具有指数加速的能力。
1 Deutsch-Jozsa算法简介
1992 年由David Deutsch 和 Richard Jozsa提出了第一个量子算法Deutsch-Jozsa 量子算法, 简称D-J 算法，这是第一个展示了量子计算和经典计算在解决具体问题时所具有明显差异性的算法。
Deutsch-Jozsa算法解决的主要问题是：考虑一个函数
, 它将n 个字符串x 作为输入并返回0 或 1，n 个字符串也是由0 和1 组成。简单来说，就是定义在
上的函数
，满足
。那么输出就分为两种情况。一种是，对于任意输入，它只输出0 或者1，我们称之为常函数；另一种情况是，恰好对于一半的输入，输出为0，另一半输入，输出为1，我们称之为平衡函数。
对于未知的
，我们要区分它是常函数还是平衡函数。如果采用经典计算的方式，需要挨个检查输出结果，要得到准确无误的判断，最坏的情况需要进行
次计算。这是因为，如果进行了
次计算后，得到的是
个相同的输出，这时候仍不能确定
是常函数还是平衡函数。若果采用量子计算的方式，对于同样的问题，只需要一次计算就可以得出结果，解决这个问题的量子算法称为Deutsch-Jozsa算法。
Deutsch 算法即是D-J 算法n=1 的情况，下面我们以Deutsch 算法为例进行详细讲解。Deutsch算法显示了量子相干性的强大计算能力。考虑一个黑匣子，我们把他叫做谕示(oracle)，它可以自己算一个比特的布尔函数
，每做一次计算，我们称对谕示做一次查询。存在4个这样的函数，如表1所示：
表1.单比特逻辑函数
和
是常数的，它们与其余两个（
和
）具有不同的整体性质，对于
和
，我们称它们为平衡函数（balanced）。所要解决的问题是，对于一个给定的函数，确定它是常数的还是平衡的。要得到该问题的答案，经典计算机需要对谕示做两次查询。这里我们将证明，量子计算机只需要做一次查询就可以解决这个问题。实现Deutsch 算法的量子线路图如下。
对函数
的计算是可逆的，并且利用了一个辅助量子比特
。幺正变换
把
变成
；也就是说，只有当
时，它才反转第二个量子比特。量子比特的初态取为
。然后，用Hadamard门将第1比特制备为叠加态
下面我们会证明，这样的得到的态允许量子计算机在一次运算同时计算
和
。这种可能性超出了经典计算机的能力范围，我们还需要另外一个Hadamard门，把辅助量子比特制备在态
。这是关键的一步，因为，这样一来，对于每一个
也就是说，在左边第一个量子比特前产生一个相因子
，有时，人们称该相因子是向后传播的。这样，完成函数计算之后，量子计算机的态是
第2个量子比特不再有用，从此可忽略。最后的Hadamard门是第1个量子比特进入状态
如果
，该态为
。而如果
，它为
（这两种情况，都只是准确到一个没有物理意义的相因子）。这样，第一个量子比特的终态可以统一写成:
于是，如果函数是常数的，对于第一个量子比特的测量会百分之百得到0；而如果函数是平衡的，那么测量结果肯定是1。因此，在仅仅调用函数一次之后，其整体性质就被编码在一个单量子比特之中。这是因为量子计算机可以同时计算
和
。关键在于，两个可供选择的“路径”被最后一个Hadamard门组合起来，从而差生了所需的干涉效果。对于输出
，干涉是相干的，而对于相反的输出，干涉是相消的。
2 Deutsch-Jozsa问题
现在来考虑Deutsch问题的某些推广。Deutsch-Jozsa算法通过对谕示做一次询问，这样可以解决以下问题：对于一个为常数的或者是平衡（平衡的意思是它具有相同数目的0和1）的n比特二级制函数
，确定它为两者中的哪一个。解决该问题的量子线路与Deutsch算法的线路相同，除了这里用到是n个量子比特来存储输入
，Hadamard门被并行地作用于所有n个量子比特
容易验证，
作用于计算基矢态
给出
其中,
即
将Deutsch算法量子线路图推广到n个量子比特，意味着将变换
作用于输入
，并且产生输出
对于该输出态，我们测量者n个量子比特在计算基矢上的情况。如果为常数的，则测量会以百分之百的概率得到态；而如果是平衡的，那么测到的这个态的概率为0。这样，单单运行一次该算法，对函数仅查询一次，既可以确定是常数的还是平衡的。这的确给人深刻的印象，因为在经典计算中，只有
次查询后，才能确切的知道函数是否是平衡的。
说明：该系列文章中描述的相关实验均可通过国仪量子金刚石量子计算教学机实现。
