Deutsch与Deutsch—Jozsa算法简介

龙源期刊网 https://www.wendangku.net/doc/e216649239.html,

Deutsch与Deutsch—Jozsa算法简介

作者：黄蕴琦叶泽坤陈韦江

来源：《电脑知识与技术》2017年第35期

摘要：在经典计算机里，随着器件尺寸越来越接近物理极限，摩尔定律也即将失效。而量子计算机则为提升计算机的计算能力提供了一个全新的角度，量子计算特有的并行性使得经典计算无法望其项背。该文首先介绍了量子计算的起源和基本概念；然后介绍第一个量子算法，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世纪初，德国物理学家普朗克在研究黑体辐射问题时提出了一个假设：能量在发射和

吸收的时候，不是连续不断，而是一份一份来进行的。这个假设，标志着量子力学的开端。此