基于“嵩山”超级计算机系统下HHL算法的模拟实现

量子计算是一种遵循量子力学规律来调控量子信息单元进行计算的新型计算模式,而量子算法由一系列量子门组合而成,其实现形式为量子线路。量子线路是对量子比特进行操作的线路,以量子比特为基本的存储单元,将量子逻辑门连接在一起来实现特定的计算功能。文中在“嵩山”超级计算机上利用MPI+OpenMP混合并行编程模型,实现了将大规模量子线路拆分到不同节点上进行构建,加快了线路的构建速度,并且在CPU集群系统上具有良好的可拓展性。针对节点间通信问题,设计了序列化和反序列化函数,以保证节点间数据的传输,并且根据各节点所分配任务量间存在的指数级差异,设计了一种拆分任务量、各节点轮循处理的优化方式,实现了节点间的负载均衡。最后在超级计算机CPU集群上成功实现了大规模的量子相位估计线路的构造,相较于单节点取得了8.63的加速比,并通过HHL算法验证了所设计的并行相位估计子模块的正确性,为大规模HHL算法在超算平台上的实现提供了参考。     

基于Grover算法的图着色问题求解

Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法，可用于解决图着色、最短路径排序等问题，也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一，文中首先将图着色问题转化为数学上的无向图；然后采用布尔表达式将其转换为布尔可满足性问题，介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程；最后在IBMQ云平台上，对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性，在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中，分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题，拓展了该算法在此问题领域上的实验规模，且改进了现有实验的量子线路，使量子位成本更低，结果的成功率更高，展示了Grover算法在大型搜索问题中显著的加速效果。