Deutsch与Deutsch―Jozsa算法简介.docVIP

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， Moores 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年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行。量子计算以叠加性、干涉性、纠缠性、不可克隆、状态变化等量子力学原理为