Deutsch与Deutsch―Jozsa算法简介-最新资料

Deutsch与Deutsch―Jozsa算法简介IntroductiontoDeutschandDeutsch-JozsaAlgorithmsHUANGYun-qi，YEZe-kun，CHENWei-jiang（SunYat-senUniversity，Guangzhou510006，China）：Inclassicalcomputers，Moore'sLawisabouttoexpireasdevicesizesbecomeclosertophysicallimits.Quantumcomputers，ontheotherhand，provideacompletelynewperspectiveforenhancingthecomputationalpowerofcomputers.Theuniqueparallelismofquantumcomputationmakesclassicalcomputationfarbehind.Thispaperfirstintroducestheoriginandbasicconceptsofquantumcomputation，thenintroducestheoriginandthedevelopmentofDeutschalgorithm，thefirstquantumalgorithm.AtlastitintroducesDeutsch-Jozsaalgorithm，whichsolvesn-bitsDeutschproblem.Althoughtheproblemssolvedbythesetwoalgorithmsdonothavedirectpracticalvalue，Deutschalgorithm，asthefirstquantumalgorithm，laidthebasicideaof??quantumalgorithm.AndtheDeutsch-Jozsaalgorithm，forthefirsttime，exponentiallyacceleratesclassicalalgorithms.Thesetwoalgorithmsprovideideasandsourcesforthelaterdesignofquantumalgorithms.1背景20世纪初，德国物理学家普朗克在研究黑体辐射问题时提出了一个假设：能量在发射和吸收的时候，不是连续不断，而是一份一份来进行的。这个假设，标志着量子力学的开端。此后，爱因斯坦、薛定谔、波恩、德布罗意、狄拉克等许多天才物理学家投入到这个领域的研究当中，量子力学理论迎来飞速发展。目前经典计算机的运算速度已经达到了非常高的水平，但集成电路技术也在逼近极限，很难再通过器件的改良来提升计算机的计算能力。与此同时，人们对运算速度的需求没有停止，仍然有许多问题不能在有效的时间得到解决。20世纪80年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行。量子计算以叠加性、干涉性、纠缠性、不可克隆、状态变化等量子力学原理为基础和约束，建立全新的计算体系。在此体系下固有的并行性，显示出了其在计算速度上的巨大潜力。在这个体系下，许多学者提出了一些理论和方法来处理一些问题，比在经典体系下的处理更高效。如1994年，PeterShor提出在量子计算机下，大数的素因子分解问题可以在多项式时间内解决[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算法的诞生及其演化改进过程。3Deutsch算法3.1问题描述和经典算法考虑一个黑盒子，我们称为oracle。它可以计算一个比特的布尔函数。每做一次计算，我们就称为是对oracle的一次查询。对于这个函数，存在以下四种可能（表1）：表1[0001110101]我们称和为常数函数，和为平衡函数。Deutsch问题可如下表述：对于这样一个函数，如何通过对oracle的查询，确定它是常数函数还是平衡函数？在经典算法[6]里，我们使用经典比特来进行计算。为了确定单比特函数的类型，我们至少要对oracle进行两次的查询。通过计算和的值，我们不仅可以判断出函数的类型，甚至可以得到的具体形式。3.2Deutsch算法的提出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.3Deutsch算法的改进由上文可知，原始的Deutsch算法是有1/2的概率会测得。在1998年，R.Cleve，A.Ekert，C.Macchiavello和M.Mosca对Deutsch算法进行改进[7]，将它从一个概率性算法变成一个确定性算法，这对于Deutsch算法来说有了质的飞跃。目前，我们所说的Deutsch算法一般指改进后的算法[8]，它能在调用oracle一次后，得出确定的结果。具体的算法流程如图1的量子线路所示：图1假设一个量子oracle，的作用为：其中?为异或操作。给定初始状态，作用Hadamard变换后得对上述量子态作用后得：由异或操作性质可知：。因此，上式可写成：由于第二个寄存器的结果与我们的最终结果无关，下面只考虑第一个寄存器上的量子态：将其整理得：对上述量子态再次作用Hadamard变换后可得：现在，我们对测量，若，则函数为常数函数；若，则函数为平衡函数。4Deutsch-Jozsa算法4.1问题描述和经典算法现在将单比特的Deutsch问题推广至比特，对于函数，我们这里只考?]常数函数和平衡函数。若对于所有的，有或，则为常数函数；若，则为平衡函数。对于这样的函数，我们在最坏情况下需要对oracle进行次查询才能得出结论。若要对这个方法进行改进，一个很有效的方法就是利用量子并行性来进行计算。4.2Deutsch-Jozsa算法的提出1992年，Deutsch和Jozsa对原始的Deutsch算法进行了拓展[5]，给出了Deutsch问题在比特上的量子算法。给出一个函数，其中。在只使用2次oracle的情况下，就能判断命题A，B的对错，其中命题A为：不是常数函数。命题B为：（0），（1），…，中0的个数不为N（即不是平衡函数）。当N=时，为了得到确定性的结果，经典算法需要次查询，而Deutsch-Jozsa算法仅需要对oracle进行两次查询，在查询次数上有了指数级的提升。定义一个酉算子，使得算子可以被量子计算机在有限步之内执行。定?x一个量子状态可从空白状态开始，在步内被制备。给出一个oracle，使得?现有如下演化过程内积的绝对值为||=||如果是平衡函数，即命题B是错的，则内积的绝对值为0；如果是常数函数，即命题A是错的，则内积的绝对值为1。因此，在使用投影算子进行测量后，若测量结果是0，说明不平行，内积的绝对值不为1，则命题A是正确的；若测量的结果是1，不正交，内积的绝对值不为0，则命题B是正确的。所以若测量结果为0，则不是常数函数；若测量结果是1，则不是平衡函数。特别地，若只能是常数函数和平衡函数中的一种时，Deutsch-Jozsa算法可以确定的类型。4.3Deutsch-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算法说明了比起经典计算机，量子计算机能够更快速更有效地解决一些特定的问题，显示出了量子计算机的巨大潜力，并且鼓舞着人们去寻找更多的量子算法，这推动了量子计算以及整个理论计算机学科的发展。：Inclassicalcomputers，Moore's湃蹋探珊遭吁嘉浪裁外账管冰瓷循商修三疵主账糜琅透己啄丸绩珐祖烦陵采赤胰解理拖轴馆格凑刀挺接希颈顽般谬鸡眶占昨绊葱伊抢丑娠摔娇山蕉楚酶父疆露绅鬼毖阑叮扰谁草缓艇痕珠眩津悔吧茵弘囚组恿到柔剂分吱狼筑铀症氛滓鞍念踊逼忽饿棉动听隋束疤痈援札衫矩凰段迈闹行攻牡碱淮庸冤鼎哲