摘要
量子计算凭借其叠加性和纠缠性,具有强大的并行计算能力。然而,目前的量子计算机不能在保证大规模量子比特处于稳定叠加态的同时,进行干涉、纠缠等量子操作。因此,当前研究和推动量子计算的有效途径是使用经典计算机模拟量子计算。Grover量子搜索算法针对无序数据库搜索问题设计,将搜索的时间复杂度加速至开平方级,能加速机器学习中的主成分分析。因此,研究和模拟Grover算法,可以促进量子计算与机器学习结合领域的发展,为Grover量子搜索算法的应用以及量子机器学习在“嵩山”超级计算机系统中的模拟奠定基础。通过研究Grover量子搜索算法,模拟出了算法的量子线路。使用Toffoli量子门优化该量子线路,在减少了两个辅助量子比特的同时,提出了Grover算法的通用量子线路。实验基于“嵩山”超级计算机系统的CPU+DCU异构体系,使用了MPI多进程+HIP多线程的两级并行策略。通过调整辅助比特在量子线路中的位置,减少了MPI进程间的通信;使用分片的方式传输数据依赖的量子态。对比串行版本,并行化的模拟算法取得了最高560.33倍的加速,首次实现了31qubits规模的Grover量子搜索算法。
With its superposition and entanglement properties,quantum computing has a powerful parallel computing capacity.However,current quantum computers cannot ensure stable superposition states of large-scale qubits while performing quantum operations such as interference and entanglement.Therefore,the current approach to promote quantum computing is to simulate quantum computing using classical computers.The Grover quantum search algorithm is designed for the problem of searching unsorted databases,reducing the time complexity to square root level,and accelerating principal component analysis in machine learning.Therefore,studying and simulating the Grover algorithm can promote the development of quantum computing combined with machine learning and lay the foundation for its application as well as the simulation of Grover quantum search algorithm in the“Songshan”supercomputer system.By studying the Grover quantum search algorithm,the quantum circuit of the algorithm is simulated.The Toffoli quantum gate is used to optimize the quantum circuit,proposing a universal quantum circuit for the Grover algorithm while reducing two auxiliary qubits.The experiment is based on the CPU+DCU heterogeneous system of the“Song-shan”supercomputer system,using a two-level parallel strategy of MPI multiprocessing and HIP multithreading.By adjusting the position of the auxiliary qubits in the quantum circuit,the communication between MPI processes is reduced,and the data-depen-dent quantum states are transmitted using a fragmentation method.Compared to the serial version,the parallelized simulation algorithm achieves a maximum speedup of 560.33 times,realizing for the first time the Grover quantum search algorithm with a scale of 31 qubits.
作者
杜帅岐
刘晓楠
廉德萌
刘正煜
DU Shuaiqi;LIU Xiaonan;LIAN Demeng;LIU Zhengyu(National Supercomputing Centerin Zhengzhou,Zhengzhou 450001,China;School of Computer and Artificial Intelligence,Zhengzhou University,Zhengzhou 450001,China)
出处
《计算机科学》
CSCD
北大核心
2024年第9期96-102,共7页
Computer Science
基金
国家自然科学基金(61972413,61701539)。
关键词
GROVER量子搜索算法
异构体系
MPI
HIP
分片传输
Grover’s quantum search algorithm
Heterogeneous architecture
MPI
HIP
Fragment-based transmission
