量子计算 [4] -- 算法设计 & Grover搜索算法

因为量子计算的并行性,  搜索问题,  比如说数据库搜索, 最短路径问题, 加密问题, 图形着色问题等,  都被视为可以做到量子加速.

然而在实际上,  设计一个可以解决问题的量子算法是困难的.  比如说数据库搜索问题里,  常用电子线路储存数据,  当量子线路对数据库历遍时,  实际上也是等于用电子计算机历遍了一次数据库.  当然解决办法就是使用量子位储存数据,  n个量子位可以最多储存 2^n 个数据 [实际上使用相位可以理论上储存无穷个数据].

如此可见达到量子加速的搜索算法需要满足几点:  搜索黑盒允许量子操作,  并且量子黑盒里的复杂度小于或差不多等于电子黑盒的复杂度,  电子计算不存在更快速的算法.  满足以上几点才可以说量子算法可能达到加速效果.  但不止如此,  下面通过一个简单的图形着色问题来了解一下最著名的量子搜索算法 -- Grover算法.

注:  以下算法全部是python+nyasQuantumCalculate,  关于库可以见结语

图形着色问题

给出一个已知的图(Graph),  也就是已知的顶点(Vertex)和连接顶点的边(Edge),  对每个顶点打上标签 [也就是着色],  寻找一个可能着色使得每条边上的顶点都不是相同颜色.

由问题描述可以知道,  只有不存在自环的无向图才是图形着色问题的讨论范围.  并且常用索引表示顶点,  列表表示边.  比如:  以下表示了一个图:

并且简单推导可以知道这个图至少需要4种颜色来着色,  使用2bits可以对4种颜色编码,  并且把全部顶点颜色编码为一个列表,  则下面是一个可用的着色方案:

设计算法

量子计算可用看作可逆逻辑计算的拓展,  而可逆逻辑计算则通过X, CNOT和CCNOT还原传统电子计算逻辑.   加法器示例

首先需要解决的问题是如何判断颜色相等.  不难知道这个方法需要输入两个寄存器表示两个颜色,  和一个标记位用来获取结果.  如果两个寄存器状态相同则翻转标记位的状态.  XOR门是一个很好的判断两bits是否相同的门,  而可控过程是非常好的多位AND门,  细节可以参考代码备注.  正所谓自己动手才是学编程的正确姿势,  下面代码可以自己试着验证运行一下.

有了检验一条边的顶点颜色是否相等的方法后,  对整个图的每条边进行历遍,  当全部边的顶点颜色都不相同时,  则表明是一个可用的着色方案.

需要注意的是,  尽管Reset可以快速地重置量子位,  但是在程序结束前的Reset是没有意义的.  实际上量子计算机的重置是通过升温或激光等方法使量子退相干,  这个过程会损失大部分数据,  所以不可以通过简单Reset去重置tmpQubits.

可以留意到,  上面的方法没有使用到量子特性 [比如说相位, 叠加, 干涉等],  所以这个算法是完全电子逻辑的.  实际上把 `from nyasQuantumCalculate import *` 改为 `from nyasQuantumCalculate.RevCal import *` 从量子计算模拟切换为可逆电子计算模拟,  上面的方法依然是正确的 [除了变量类型标注].

Grover搜索算法

Grover算法是通用的搜索算法,  通用的意思是,  搜索过程与具体问题无关,  只要满足:  每次执行某个黑盒所有正确答案的相位都被翻转,  Grover算法就搜索出黑盒里的"正确"答案.

Grover算法需要反复计算某个过程,  每迭代一次(某种程度内),  测量得到正确答案就会增长.  单次迭代包含两步:   1)  应用黑盒;  2) 应用Grover扩散算子(Grover diffusion operator).  黑盒把正确答案的相位进行翻转,  Grover算子把正确答案的出现概率增大,  并减少错误答案的出现概率.

Grover算子表示为

其中 W 为 Hadamard变换(Hadamard Transform),  Hadamard变换的逆为它自身,  并且忽略全局相位的影响,  则Grover算子为  .  关于Grover算子的细节就留到附章讨论,  这里先着重实现算法.

如果把系统状态表示为正确答案和错误答案的叠加态,  其中Good是正确答案,  Bad是错误答案,  则任意一个系统状态都处于在  空间里的单位圆上.  设系统的均匀叠加态  与  之间的夹角为θ,  不难知道有以下关系:  , 其中M为全部正确答案的数量,  N为全部可能答案的数量.  那么Grover算法的单次迭代实际上是把系统状态在  空间里逆时针旋转θ.  如下图

当系统状态与的夹角越靠近 π/2,  测量结果越可能得出正确答案.  不难看到如果迭代次数过多让系统状态接近的话,  正确答案的概率会变小.  所以最佳迭代次数为 ,  其中[]为四舍五入,  sin^-1为方sin函数 [arcsin].

搜索问题答案

在Grover算法里,  黑盒是需要翻转正确答案的相位,  也就是相位黑盒,  但这里设计的验证着色方案是否有效的算法是翻转标记位的状态,  也就是标记黑盒.  可以使用"相位反冲"的技巧把标记黑盒转为相位黑盒.  有关量子黑盒

已知问题里有5个顶点,  又需要2bits表示颜色,  也就是需要总共10个量子位来表示全部着色方案.  全部可能方案的数量为 2^10 = 1024 个,  而正确方案的数量为 2 * 4! = 48 个,  至于总共数量怎么出来就不是量子计算的讨论范围了.  包装Grover搜索算法:

可以注意到Grover搜索算法并不能保证运行完后以100%概率测得正确方案,  进行测量后还需要对结果进行检查,  如果不正确则重复运行算法.  测量后,  量子位坍缩到测量结果里而损失其它信息,  这时候可以使用另一个量子位与寄存器运行GraphColoring检查寄存器是否处于正确的方案里.  综上,  搜索图形着色方案的主体程序为:

加上输出:

如果还是在意结果是否正确,  可以在最下面加一段代码验证:

其中answer包含全部正确方案.

经过上面的例子可以看出,  Grover搜索算法并不能以概率1给出正确答案.  并且有一个比较严苛的条件就是需要知道正确答案的总数M才能以最少运行次数实现算法.  实际操作里,  如果不知道正确答案的总数,  可以让 j 为一个较小的数字开始,  比如说3,  每次获得错误结果就增大 j. 直到获得正确结果.

在使用nyasQuantumCalculate的时候,  可以把 Options.autoNormalize 设为 False 以加快运行速度.  这个选项是在每个位门作用之后把系统归一化,  设置为False后每个位门的计算误差会逐渐累积下来 [每次大约10^-17],  在误差过大的时候可能会导致一部分逻辑出错,  这时候可以调整 Utils 里的 delta 以允许更大的误差 [默认10^-8,  调整需要直接修改库].

老推销员继续推自己的库: [github.com/nyasyamorina/nyasQuantumCalculate]

瑟图群: [274767696]