本系列文章的目标是介绍一个著名的量子算法：Grover 算法（查找），个人认为只要理解了这个算法的原理，IT人需要了解的量子计算知识就足够入门了，后续自己阅读相关资料将不再困难。介绍过程中所用到的领域知识和符号都会作为基础知识一并介绍，不求全面但求够用，另会附上相关资料的链接供读者参考。

本文面向的读者是 IT 业者，需要有具备以下知识结构：

1. 高中数学基础，
2. 初步的线性代数，包括矩阵、向量的四则运算，了解内积、转置、迹等基本概念；
3. 基本的数字电路概念，有一定的编程思维，知道算法复杂度的相关概念和基本计算方法；
4. 对量子现象和概念有初步的认知，大概知道「薛定谔的猫」是怎么回事即可。

对于上面第4条，如果你完全没有接触过量子领域的任何知识，阅读本文确实会存在一定的困难。不过也不用担心，介绍这些基础知识的视频非常丰富，以下列出一些搜索关键字供参考：

量子测不准原理（不确定性原理）：

量子两双缝干涉实验（量子的叠加态）：

惠勒延迟选择实验：

量子纠缠：

还有很多相关的科普视频都很有趣，这里就不一一列举了，读者可以花些时间，顺藤摸瓜式的查阅。总之这些知识了解的越多，本文的内容也就越容易理解。而对于想深入学习的读者来说更重要的其实是耐心，要仔细理解全文中的每个公式和设置的练习。

一、概述

本章争取用 15 分钟时间让读者对量子计算的原理有一个大致了解，如果对理论层面的原理不感兴趣，那么只阅读本章也就足够了。

我们先以传统的查找算法为例：在未排序的库中找到指定的元素。如果要用数字电路实现这个算法，首先我们需要一个 个位的寄存器，一个枚举器和一个比较器。以 为例说明，分这么三步：

1. 我们用一个 4 位的寄存器就可以表示 0~15 中的任意一个数值（序号），枚举器会改变寄存器的值，依次生成 0~15 的序号，并逐一送到比较器中；
2. 一个最简单的比较器就是直接比较序号和指定的数值，如果序号和指定值相等就输出 1 ，否则输出 0；
3. 最后，当比较器输出 1 时，外部电路就根据当前序号进行相应处理即可。

该传统算法的时间复杂度是 ，平均比较次数为 。读者可能会意识到，这种直接比较序号和指定数值的比较器在实践中并没有意义。确实如此，真正的比较器往往要复杂得多，比如会先按序号从库中抽取元素，然后再通过某种运算比较该元素和指定元素。但无论比较器内部的操作有多复杂，只要其复杂度和 N 的大小无关，那么决定整个算法复杂度的唯一因素只有平均比较次数。所以为了便于读者理解量子算法，下面仍以这种最简单的「直接比较器」为例进行说明。

电子计算机基于数字比特和数字电路进行计算，而量子计算机则是基于量子比特和量子电路进行计算的。量子计算机上的查找算法（称为Grover 算法），也同样需要 个量子比特。我们仍以 为例，需要 4 个量子比特。然而，由于量子的神奇性质，这 4 个量子比特组成的系统可以同时表示 0, 1, ..., 15 ，即 16 种状态的叠加态（对此感兴趣的请参见 态叠加原理_百度百科 ）。通过量子电路我们可以制备出这种叠加态，且每一种状态的幅度都相等，均为 0.25 ：

此处不用深究辐度是什么，可以先把辐度值的平方理解为概率。例如状态 0 的辐度为 0.25，那么其概率为 0.0625。16种状态幅度的平方和为 ，即概率和为 1 。

和电子计算机类似，量子电路也拥有许多种门。用这些量子门可以组合成一个量子比较器：将指定的某个状态的辐度反转。假如我们要查找的数是 5 ，那么比较器就会把叠加了 0~15 的 16 种状态中的 5 状态的辐度进行反转。此时其它状态的幅度不变，而 5 的概率成为 -0.25 ：

但因为概率是辐度值的平方，所以 5 状态的概率仍然是 1/16，和其它状态的概率并没有区别。接下来我们还需要用另一组量子门组合而成的「量子放大器」对当前系统中辐度值为负的状态进行放大：

接下来只要将量子比较器和量子放大器一起重复执行 次，5 状态的幅度就会远高于其它状态的幅度。此时对这 4 个量子比特的值进行观测，各状态就会以各自的概率（幅度的平方）发生量子坍缩，使整个系统变成一个确定的状态。例如一个量子系统由 2 种状态 a 和 b 叠加而成，其幅度分别为 0.6 和 -0.8 ，那么对该量子系统进行观测，其结果有 的概率坍缩为 a， 的概率坍缩为 b 。回到上面的例子，在 次计算后 5 状态的幅度达到 0.98 ，那么最终测量的结果有超过 96% 的概率为 5。

由于 ，所以量子算法具有优势。

【问】比较器为什么知道要把 5 状态的相位反转？
【答】因为比较器就是我们为求解这个查找问题设计的，就像数字电路一样，量子电路也可以很容易设计出专门用于查找 5 的比较器。（具体设计详见后续章节）

【问】为什么是执行 次？
【答】由 Grover 算法的原理可以证明：执行 次后指定状态的概率已足够高，具备决定性。（具体证明详见后续章节）

【问】有没有可能求得的值是错的？
【答】虽然概率很低但确实存在。不仅理论上存在错误的可能，实际的量子计算机更容易受到噪声的干扰而发生错误。但我们遇到的很多问题其实只要大概率解对就足够了，偶尔出错也没有大影响。

【问】量子比较器和量子放大器一起执行一次要多久？如果慢于电子计算机，是否还具有性能优势？
【答】假设量子电路执行一次要 s 秒，电子计算机比较一次要 t 秒，且 。那么算法执行的平均总时间分别是 和 ，只要当 足够大，使得 ，即可以实现量子优越： 。

【问】还是没看懂，有没有更形象的解释？
【答】那就再打一个不恰当的比方吧，还是以量子的 Grover 搜索算法为例：厂里雇佣了 100 个工人。某一天厂长被警察告知这些员工中间可能有一个是逃犯，老板要配合警察把这个人找出来。但是今天刚好放假，员工都不上班，老板只有证件照图册。传统方法是拿员工的证件照一个一个比对通缉犯的照片，最差情况要比对到第 100 个才能搜出来，平均情况也得比对 50 次。而量子计算机的办法就是用一种特殊机器把这些员工照片叠在一起扫描，变成一个「量子幸运大转盘」，转盘最初有 100 个一样大小的格子，分别存放 100 个员工照片。然后再用一种记录了罪犯照片的机器来修改这个大转盘，这个机器会让罪犯所在的格子变大，其它格子变小。修改过 10 次以后，罪犯的格子就已经大到几乎覆盖整个转盘了。最后来转动这个大转盘，被转到的人很大概率就是罪犯。相比于传统算法平均比对 50 次而言，量子算法只进行 10 次放大就够了。此外，员工数量越多，量子算法的优势就越明显。

从下一章开始进入理论部分。