Deutsch与Deutsch—Jozsa算法简介

黄蕴琦+叶泽坤+陈韦江

摘要：在经典计算机里，随着器件尺寸越来越接近物理极限，摩尔定律也即将失效。而量子计算机则为提升计算机的计算能力提供了一个全新的角度，量子计算特有的并行性使得经典计算无法望其项背。该文首先介绍了量子计算的起源和基本概念；然后介绍第一个量子算法，Deutsch算法的提出和发展；最后介绍Deutsch-Jozsa算法，它解决了n比特的Deutsch问题。尽管该两个算法所解决的问题不具有直接的实用价值，但Deutsch算法作为第一个量子算法，奠定了量子算法的基本思想，而Deutsch-Jozsa算法则首次实现了对经典算法的指数级加速。该两个算法为后来的量子算法的设计提供了思路和源泉。

关键词：量子计算；量子算法；量子并行性；Deutsch算法；Deutsch-Jozsa算法

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2017）35-0149-04

Introduction to Deutsch and Deutsch-Jozsa Algorithms

HUANG Yun-qi， YE Ze-kun， CHEN Wei-jiang

（Sun Yat-sen University， Guangzhou 510006， China）

Abstract： In classical computers， Moore's Law is about to expire as device sizes become closer to physical limits. Quantum computers， on the other hand， provide a completely new perspective for enhancing the computational power of computers. The unique parallelism of quantum computation makes classical computation far behind. This paper first introduces the origin and basic concepts of quantum computation， then introduces the origin and the development of Deutsch algorithm， the first quantum algorithm. At last it introduces Deutsch-Jozsa algorithm， which solves n-bits Deutsch problem. Although the problems solved by these two algorithms do not have direct practical value， Deutsch algorithm， as the first quantum algorithm， laid the basic idea of ??quantum algorithm. And the Deutsch-Jozsa algorithm， for the first time， exponentially accelerates classical algorithms. These two algorithms provide ideas and sources for the later design of quantum algorithms.

Key words： quantum computation； quantum algorithm； quantum parallelism； Deutsch algorithm； Deutsch-Jozsa algorithm

1 背景

20世纪初，德国物理学家普朗克在研究黑体辐射问题时提出了一个假设：能量在发射和吸收的时候，不是连续不断，而是一份一份来进行的。这个假设，标志着量子力学的开端。此后，爱因斯坦、薛定谔、波恩、德布罗意、狄拉克等许多天才物理学家投入到这个领域的研究当中，量子力学理论迎来飞速发展。

目前经典计算机的运算速度已经达到了非常高的水平，但集成电路技术也在逼近极限，很难再通过器件的改良来提升计算机的计算能力。与此同时，人们对运算速度的需求没有停止，仍然有许多问题不能在有效的时间得到解决。

20世纪80年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行。量子计算以叠加性、干涉性、纠缠性、不可克隆、状态变化等量子力学原理为基础和约束，建立全新的计算体系。在此体系下固有的并行性，显示出了其在计算速度上的巨大潜力。在这个体系下，许多学者提出了一些理论和方法来处理一些问题，比在经典体系下的处理更高效。如1994年，Peter Shor提出在量子计算机下，大数的素因子分解问题可以在多项式时间内解决[1]。本文中我们将介绍第一个量子算法，Deutsch算法及其改进以及该算法的一般情况Deutsch-Jozsa算法。

2 量子計算基本概念

2.1 量子比特

在经典计算机里，我们利用比特作为最小单位进行存储。一个比特只能是两种状态，要么为0，要么为1。而对应的在量子计算机里我们用量子比特来进行存储。量子比特则是用和来表示对应的0，1状态，记，。与经典比特不同的是，量子比特可以是状态的线性组合[2]，又被称为叠加态，如下所示：

其中和是复数，且满足条件。

同样地，对于多量子比特来说，当时，可如下表示：

其中，是复数，且满足条件。==， ==，和类似。（是一个矩阵，是一个维矩阵，则，是一个维矩阵）

2.2 测量

对于单量子比特，可定义观测量集合{}，它们满足，其中是的共轭转置矩阵（取0或1）当我们对进行测量时[3]，有的概率测量结果为0，此时量子比特变为 有的概率测量结果为1，此时量子比特变为。特别地，当==时，以的概率测量得到0，以的概率测量得到1。

而对于2位的量子比特，可定义观测量集合{}，它们满足。当我们对进行测量时，有的概率测量结果为，此时量子比特变为。（其中=0，1，2或3）

2.3 量子门

在量子世界里，我们的运算操作是由量子逻辑门完成的。量子逻辑门（简称量子门）可以由酉矩阵及其组合来进行表示。每个酉矩阵都可以定义一个有效的量子门。根据输入的比特数的不同我们可以分为单量子比特门和多量子比特门。常用的单量子比特门有Hadamard门，Pauli门等。下面举一个作用Hadamard门变换的例子：

2.4 量子算法

量子算法即是利用量子的叠加性、纠缠性和状态变化等特点来进行设计的算法。量子算法通常由上述所说的一系列量子逻辑门进行顺序操作来实现。在1985年，Deutsch首次提出了一种量子算法用于解决Deutsch问题[4]，在1992年Deutsch和Jozsa一起提出Deutsch-Jozsa算法[5]，解决了n比特的Deutsch问题，对经典算法进行了指数级速度的改进。本文的剩余部分将用于介绍Deutsch算法和Deutsch-Jozsa算法的诞生及其演化改进过程。

3 Deutsch算法

3.1 问题描述和经典算法

考虑一个黑盒子，我们称为oracle。它可以计算一个比特的布尔函数。每做一次计算，我们就称为是对oracle的一次查询。对于这个函数，存在以下四种可能（表1）：

表1

[ 0 0 0 1 1 1 0 1 0 1 ]

我们称和为常数函数，和为平衡函数。Deutsch问题可如下表述：对于这样一个函数，如何通过对oracle的查询，确定它是常数函数还是平衡函数？

在经典算法[6]里，我们使用经典比特来进行计算。为了确定单比特函数的类型，我们至少要对oracle进行两次的查询。通过计算和的值，我们不仅可以判断出函数的类型，甚至可以得到的具体形式。

3.2 Deutsch算法的提出

1985年，Deutsch首次提出了量子图灵机模型[4]，并且设计了第一个量子算法—Deutsch算法用于解决上述所说的Deutsch问题。该算法将以1/2的概率对oracle进行一次查询就能得到函数的类型。这是人类历史上首个利用量子的特性所设计出来的专门针对量子计算机的算法，开创了量子算法的先河，为后面的Shor算法，Grover算法等的量子算法的设计提供了思路。因此，作为一个开创性的算法，Deutsch算法的设计思路意义远大于它所解决问题能力的意义。

假设有这样一个量子计算机Q，对每个函数，和整数a，b，在Q上存在一个程序使得函数对寄存器a的内容进行计算，并放置到寄存器b里，即

现考虑量子程序

它将使得Q终止于状态

.

特别地，当N=2时，寄存器2，3的状态为

.

现对其进行一次测量，其观测量集合为{}，其中

-

-

+

+

若，则与正交，测量结果只可能是；若，则与正交，则测量结果只可能是。因此若结果测得是，则可以断定；若结果测得是，则可以断定；如果结果测得是，则无法得出结论。所以Deutsch算法可以以1/2的概率，只执行1次oracle就能得到的结果；而经典算法至少要计算两次。

3.3 Deutsch算法的改进

由上文可知，原始的Deutsch算法是有1/2的概率会测得。在1998年，R. Cleve， A. Ekert， C. Macchiavello和M. Mosca对Deutsch算法进行改进[7]，将它从一个概率性算法变成一个确定性算法，这对于Deutsch算法来说有了质的飞跃。目前，我们所说的Deutsch算法一般指改进后的算法[8]，它能在调用oracle一次后，得出确定的结果。

具体的算法流程如图1的量子线路所示：

图1

假设一个量子oracle，的作用为：

其中⊕为异或操作。

给定初始状态，作用Hadamard变换后得

对上述量子态作用后得：

由异或操作性质可知：

。

因此，上式可写成：

由于第二个寄存器的结果与我们的最终结果无关，下面只考虑第一个寄存器上的量子态：

将其整理得：

对上述量子态再次作用Hadamard变换后可得：

现在，我们对测量，若，则函数为常数函数；若，则函数为平衡函数。

4 Deutsch-Jozsa算法

4.1 问题描述和经典算法

现在将单比特的Deutsch问题推广至比特，对于函数，我们这里只考慮常数函数和平衡函数。若对于所有的，有或，则为常数函数；若，则为平衡函数。对于这样的函数，我们在最坏情况下需要对oracle进行次查询才能得出结论。若要对这个方法进行改进，一个很有效的方法就是利用量子并行性来进行计算。

4.2 Deutsch-Jozsa算法的提出

1992年，Deutsch和Jozsa对原始的Deutsch算法进行了拓展[5]，给出了Deutsch问题在比特上的量子算法。给出一个函数，其中。在只使用2次oracle的情况下，就能判断命题A，B的对错，其中命题A为：不是常数函数。命题B为：（0），（1），…，中0的个数不为N（即不是平衡函数）。

当N=时，为了得到确定性的结果，经典算法需要次查询，而Deutsch-Jozsa算法仅需要对oracle进行两次查询，在查询次数上有了指数级的提升。

定义一个酉算子，使得

算子可以被量子计算机在有限步之内执行。

定義一个量子状态

可从空白状态开始，在步内被制备。

给出一个oracle ，使得

⊕

现有如下演化过程

内积的绝对值为

||=||

如果是平衡函数，即命题B是错的，则内积的绝对值为0；如果是常数函数，即命题A是错的，则内积的绝对值为1。因此，在使用投影算子进行测量后，若测量结果是0，说明不平行，内积的绝对值不为1，则命题A是正确的；若测量的结果是1，不正交，内积的绝对值不为0，则命题B是正确的。

所以若测量结果为0 ，则不是常数函数；若测量结果是1，则不是平衡函数。特别地，若只能是常数函数和平衡函数中的一种时，Deutsch-Jozsa算法可以确定的类型。

4.3 Deutsch-Jozsa算法的改进

对于原始的Deutsch-Jozsa算法，98年R. Cleve等作者的论文[7]也做出了改进。原始算法中，我们需要对oracle进行两次的查询来进行判断命题A，B的对错，而改进后我们只需要对oracle进行一次查询便可以得到函数的类型[9]。

具体的算法流程如图2量子线路所示。

给定初始状态，作用Hadamard变换后可得：

对上述量子态作用后，得到：

因最后一位量子态的结果与我们的最终结果无关，因此只考虑前面部分，对该部分作用Hadamard变换后我们得到

其中表示和的取模2的内积，即

对于该输出态，我们对个量子比特进行测量。如果函数是常数函数，那么我们测量得到的概率为1，如果是平衡函数，那么测到这个态的概率为0。这样，只需要对oracle进行一次查询，我们就可以确定函数是常数的还是平衡的，这与经典算法里需要次的查询有了指数级速度的提升。

由于Deutsch-Jozsa算法所解决的问题并不像Shor算法，Grover算法等那样具有实际应用价值，它并不常被人们提及。但是它作为第一个体现量子算法优越性的算法，是非常具有里程碑式的意义的。

5 结束语

作为首个量子算法和首个体现指数级加速的量子算法，Deutsch算法和Deutsch-Jozsa算法说明了比起经典计算机，量子计算机能够更快速更有效地解决一些特定的问题，显示出了量子计算机的巨大潜力，并且鼓舞着人们去寻找更多的量子算法，这推动了量子计算以及整个理论计算机学科的发展。

参考文献：

[1] Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM review， 1999， 41（2）：303-332.

[2] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge： Cambridge University Press， 2000： 13-15.

[3] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge： Cambridge University Press， 2000： 84-85.

[4] Deutsch D. Quantum theory， the Church-Turing principle and the universal quantum computer[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1985， 400（1818）：97-117.

[5] Deutsch D， Jozsa R. Rapid solution of problems by quantum computation[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1992， 439（1907）：553-558.

[6] 吴盛俊， 周锦东， 张永德. 量子算法简介[J]. 大学物理， 1999， 18（12）：1-5.

[7] Cleve R， Ekert A， Macchiavello C， et al. Quantum algorithms revisited[C]. Proceedings of the Royal Society of London A： Mathematical， Physical and Engineering Sciences. The Royal Society， 1998， 454（1969）：339-354.

[8] Nielsen M A， Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge：Cambridge University Press， 2000： 32-36.

[9] Strini G， Benenti G， Casati G. Principles of Quantum Computation and Information： Basic Tools And Special Topics[M]. NJ， USA：World Scientific Publishing Co.， 2007： 108-110.