Deutsch与Deutsch-Jozsa算法简介

摘要：

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

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

所属期刊栏目：13

分类号：TP301.6(计算技术、计算机技术)

资助基金：中山大学实验室开放基金项目20170117

在线出版日期：2018-01-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：149-152