金刚石量子计算教学机介绍6：Deutsch-Jozsa算法

对于量子计算是全球各国在新科技革命背景下的重要竞争领域，也是国内各高校、科研机构竞相布局的战略性科技创新前沿领域。利用量子力学的叠加和纠缠，量子计算具有经典计算不可比拟的强大计算功能，因此量子计算研究具有重要的科学意义和战略意义。Deutsch-Jozsa算法是最经典的量子算法之一，解决的是判断函数类型的问题，证明量子计算在解决某些问题时具有指数加速的能力。

1

Deutsch-Jozsa算法简介

1992 年由David Deutsch 和 Richard Jozsa提出了第一个量子算法Deutsch-Jozsa 量子算法, 简称D-J 算法，这是第一个展示了量子计算和经典计算在解决具体问题时所具有明显差异性的算法。

图1. David Deutsch 和 Richard Jozsa

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 算法的量子线路图如下。

图2. 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。这样，单单运行一次该算法，对函数仅查询一次，既可以确定是常数的还是平衡的。这的确给人深刻的印象，因为在经典计算中，只有次查询后，才能确切的知道函数是否是平衡的。

3

实验部分

接下来，我们将介绍利用教学机NV 色心作为量子比特实现D.J.算法实验。即通过施加不同的微波脉冲组合对NV色心自旋进行不同的操作，根据回波探测的结果，判断操作的函数类型。

表示四个不同的函数，和是常函数，是平衡函数。实现量子算法时，我们将和编码成量子比特，为辅助能级。在系统用激光初始化到后，输入态由微波波源1的π/2脉冲作用在上而制备得到。控制门通过2π 脉冲的四种组合实现。当微波波源2的2π 微波脉冲作用在辅助态上时，会在上产生π相位，等效于和张成的子空间进行绕z 轴的π旋转。

常函数作用结束后，末态是 。平衡函数作用结束后，末态是。两种末态分别对应正向的回波和反向的回波。因此，我们就以通过回波测量，来判断控制门操作对应的是常函数还是平衡函数。

图3. 实现D-J 算法的脉冲序列，从上到下依次命名为DJ1到DJ4。

在D.J.实验中，我们利用NV色心的三能级系统，将两个量子比特编码到S=1的电子自旋上。只需要进行一次计算，我们就可以根据末态的测量结果判断是常函数还是平衡函数，当探测结果为正向回波时操作的是常函数，当探测结果为反向回波时操作的是平衡函数。而根据经典算法，则需要两次计算。D.J.实验向我们展示了，在解决某些问题时，量子算法比经典算法更高效。

图4. 量子算法实验界面

基于金刚石量子计算教学机，国仪量子可以提供量子计算教学相关的实验室建设、教学讲义、教学视频、教学课件、示范课培训等整体配套解决方案，辅助学校轻松开设实验课程。

▼