1. Deutsch问题

问题描述：有一函数 ，

若 ，则称 为常数函数

若 ，则称 为对称函数

现给定一个一位计算机做黑盒，执行函数 ，但不知道这个函数是何种类型，目标就是确定这个函数是常数函数还是对称函数。

这个问题是Deutsch于1985年首次提出的，故被称为Deutsch问题^[1]。

在经典计算中，显然必须运行两次才能得到正确结果：

（1）

（2）

基于两次的结果，进行比较，就能得出 是常数函数还是对称函数。

而在量子计算中，基于量子力学的性质，仅运行一次就可得到正确结果。下面介绍一种量子算法，这种算法是Deutsch在1985年提出的原始算法的改进版本，由1998年Cleve，Ekert，Macchiavello提出。

在介绍这个算法之前，我们先对下面这个量子电路总结出规律，再将其运用到算法中去：

其中“量子黑盒” 的操作为： .

^[2]在经过NOT门后变为 ，再经过一个Hadamard门后变为 ，最后经过一个黑盒操作 后，输出为： ^[3]，观察第二位的输出：

若 ，则

若 ，则

因此，可总结为：若输入为 ，则输出可写为：

基于此规律，下面来介绍Deutsch问题的量子算法：

该量子算法是基于上图量子电路来完成的，首先第一位 在经过一个Hadamard门之后，变为 ；第二位的 在经过NOT门后变为 ，再经过一个Hadamard门后变为 ，然后再经过量子黑盒 操作 ：

（1-2）式的推导中就用到了式（1-1）的结果，这也是我们为什么要先总结规律的原因。在得到（1-2）式的结果后，我们观察第一个量子位，

若 或 ，即 为常数函数时，则第一个量子位为：

若 或 ，即 为对称函数时，则第一个量子位为：

最后，再将第一个量子位经过Hadamard门，则可得到结果：

若 为常数函数，则第一个量子位输出为

若 为对称函数，则第一个量子位输出为

我们仅需要对第一个量子位进行一次测量，就可知道函数 的类型。可看到，该量子算法将经典中需要两步完成的事情简化为了一步。

2. Deutsch问题的推广

Deutsch问题的推广是1992年首次被Deutsch和Josza提出的Deutsch-Josza问题^[4]。实际上就是将Deutsch问题的二位输入推广到了 位输入，其问题本质上是一样的：

有函数 ，输入 位二进制 （即 只能取0或1，用数学语言可表述为 ），

若对所有的输入 ， 都是0或1，则称 是常数函数

若严格对一半的输入 ， 是0；而对另一半， 是1，则称 是对称函数

问题仍然是确定函数 的类型。（这里假设 只有这两种类型，不存在两种都不是的情况）

在经典计算中，有 位输入，每一位都可取0和1，故所有的输入情况为 种。要确定其为常数函数，最坏需要 次（比如前 次输出均为0，则还要算一次才能肯定其是否为常数函数。当然，这里说的是最坏的情况，要是运气好，计算第一次为0，第二次为1，则可直接确定其为对称函数）；同理，要确定其为平衡函数，最坏也需要 次。

而在量子计算中，只需要运算量子黑盒一次，就可以对函数 的类型做出肯定的判断。与引入Deutsch问题的算法时一样，我们先引入一个等式，再将其在算法中加以运用：

其中， 代表Hadamard门操作； ； 与 一样，也是 位二进制数态；指数上的乘积定义为： 。

对于（2-1）式，并没有严格的数学证明，而是经验总结，我们可以取 为1和2，即输入为1位和2位时来进行一个验证。

验证：

时，由于 ， ，因此可将其合并写成：

时，

可将其合并写为： ，其中 。通过简单的验证，可证明等式（2-1）的成立。

该问题的量子算法分为如下步骤：

（1）制备输入态

输入 位 和1位 ，然后将Hadamard门作用在上面，即： ，这里用到了等式（2-1），由于 的每一位均为零，故等式（2-1）中的 ，因此 .

（2）将 作为黑盒的输入态，利用式（1-1），可得到黑盒的输出态：

（3）将黑盒输出的前 个量子位再作用以Hadamard门，运用等式（2-1）可得：

对于中括号里面的式子 ，可以根据函数 的类型来分情况讨论：

情况1: 是常数函数时，该式为：

该式同样是经验总结，可以简单的通过 和 来进行验证：

时，由于 是常数函数，故 也为常数，可将其提出，则和式变为了 ，下面列出 ， 及 的全部结果：

可看到：

时，

时，

因此，总结写为：

同理， 时，和式可写为： ，同样列出 ， 及 的全部结果：

可以看到，只有 时，和式结果才不为零，而为 ，因此，同样可以将和式总结写为： .

这个结果告诉我们，如果 是常数函数，则其输出得到量子态 的概率为1.

情况2: 是对称函数时，对于量子态 ，这个和式 ，根据对称函数的性质，其值应为0。

这个结果告诉我们，如果 是对称函数，则其输出量子态 的概率为0.

（4）对前 位量子位进行测量，基于上面的讨论，如果测的量子态 的概率为1，则 是常数函数；如果测得的量子态 的概率为0，则 是对称函数。

3. Grover搜索算法

Grover搜索算法是用来处理大数据问题，是指从一个大的随机数据库中寻找一个特定数据的操作。在经典上，这也是一个可解问题^[5]，例如假设共有 条数据，则对于找到一个特定数据，其最多的查询次数也不过是 ，而其平均查询次数为： ；而在量子上，可将其查询次数降低为 次。在 较小的时候，量子算法的优越性体现的不明显；而当其很大时，量子算法的优越性就体现出来了。

3.1 数学描述

假设随机数据库集合为 ，我们要寻找的特殊数据为 ，则Grover算法分为以下几步：

1、初始化

将量子态初始化为：

2、一次迭代

定义算符 ， ，将 作用在 上为一次迭代。为方便描述，将 写为： ，显然其中 ， 。将算符 和 分别作用在 、 上的结果为：

，

由于 ，故 ，因此：

同理： ，这里值得注意的是，由于 ，故 ，而是 ，因此： ，因此一次迭代作用在 、 上所得到的结果为：

，

则总体来看，一次迭代作用在 上所得到的结果为：

同时将 类似写为： ，则一次迭代后的量子态的系数与初始态之间的关系可用一矩阵表示：

3、n次迭代

根据上面描述，一次迭代后，量子态之间的系数可用一矩阵联系，则 次迭代后的系数也可类似表示为：

通过计算，当 时，可将 、 写为： ，因此 次迭代后的量子态可写为： 。此时，按照量子力学的概率诠释，最终得到我们想要寻找的数据 的概率为： ，显然当 时，找到 的概率最大，但由于迭代次数 为整数，因此对其取整即可，即 。

实际上整个算法过程相当于通过一次又一次的迭代对初始态 中的目标态 的概率幅进行放大，使得到其的概率达到最大。

3.2 图解Grover算法

下面根据形象的图画来理解Grover算法。根据算符 的定义，并由于初始态 都是正交归一的，故可将 维的Hilbert空间划分为目标态 和与其垂直的态 ，则通过一个二维图：

由图易知： ，值得注意的有两点，一是这里的 并不只是一个矢量，而是 个态中所有与 垂直的集合，相当于一个“超平面“；而是这里的 就代表 ，后面对这两者不再作区分。

下面再来看算符 对一个任意态 的作用： ，因为 是归一化的态矢，类似于单位矢量，因此可将 写为 ，代表态矢 沿 的平行分量，而 本身也可以写为沿 的平行分量 和垂直于其的垂直分量 ，因此： ，在一个二维平面上可表示为：

下面看算符 作用在任意矢量 上的一次迭代过程：

通过上图可以看到，一次迭代过程相当于将态矢 旋转了 角度，若设 与 的夹角为 ，则有角度关系： ，故一次迭代过程相当于将态矢 旋转了 角度。

若迭代 次，则相当于旋转 角度，并且将初始任意态 取为 ，读者可以自己画着试试，此时迭代 次后， 将旋转到与 成 角的位置，若想最大概率的得到目标态 ，考虑极限情况，即迭代 次后， 旋转到了 ，此时与 成 角，亦即 。根据最开始 的定义，是 与 的夹角，因此可将 写为 量子5函数5算法5常数5迭代