Deutsch与Deutsch-Jozsa算法简介

Introduction to Deutsch and Deutsch-Jozsa Algorithms

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

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.