章节介绍

版权所有 (c) 2021 百度量子计算研究所，保留所有权利。

本章主要介绍量子计算早期的四个量子算法：

1. 伯恩斯坦-瓦兹拉尼算法（Bernstein-Vazirani Algorithm, 1992 年）
2. 多伊奇-约萨算法（Deutsch-Jozsa Algorithm, 1992 年）
3. 西蒙算法（Simon Algorithm, 1994 年）
4. 格罗弗算法（Grover Algorithm, 1996 年）

这些算法展示了在某些特定问题上，量子计算机有超越经典计算机的计算优势。前三个算法所考虑的问题并无实际用途，但它们奠定了量子算法的基本思想基础，揭示了量子计算机的潜力，激发了科学家们对量子计算的研究，进而推动了量子计算甚至是理论计算机学科的发展。格罗弗算法因为可以加速非结构化数据搜索问题，所以被认为是具有实用价值的量子算法。为了利用量子特性进行计算，量子算法首先需要将经典信息量子化。本章要介绍的四个量子算法使用一个被称为 “量子黑盒”（也称 “量子黑箱”）的核心部件来完成这个任务，它编码了目标函数的相关信息，接受一个量子态输入并给一个量子态输出。利用量子计算中的 “量子叠加” 特性，我们可以构造一个叠加态的输入，从而通过对量子黑盒的一次调用，同时得到多个输出的叠加态，这就是量子并行计算的基本原理。不过需要注意，虽然量子黑盒可以同时给出多个输出，但由于这些输出信息是叠加在一起的，通常很难把这些输出结果区分开。如何巧妙的利用这些叠加信息进行计算，是量子算法的设计难点之一。

本章介绍这四个量子算法的基本思路一致，大致分为以下部分：首先介绍算法旨在解决的问题；然后分析在经典计算机上解决该问题的复杂度；接着给出解决该问题的量子算法，基于量子电路模型详细分析它的算法细节与复杂度；最后在量易伏平台上实现该量子算法并给出简单的例子演示。

在学习与使用本知识库的过程中，欢迎积极反馈建议或者意见至 quantum at baidu.com，这将有助于我们不断地优化迭代量易简。

最后更新时间：2021年12月20日