计算机科学 ›› 2022, Vol. 49 ›› Issue (11A): 211200028-5.doi: 10.11896/jsjkx.211200028

• 交叉&应用 • 上一篇    下一篇

基于OpenMP并行模型下HHL算法的经典模拟实现

谢浩山, 刘晓楠, 赵晨言, 何明, 宋慧超   

  1. 数学工程与先进计算国家重点实验室(信息工程大学) 郑州 450000
  • 出版日期:2022-11-10 发布日期:2022-11-21
  • 通讯作者: 刘晓楠(prof.liu.xn@foxmail.com)
  • 作者简介:(15237933568@163.com)
  • 基金资助:
    国家自然科学基金(61972413,61701539)

Classical Simulation Realization of HHL Algorithm Based on OpenMP Parallel Model

XIE Hao-shan, LIU Xiao-nan, ZHAO Chen-yan, HE Ming, SONG Hui-chao   

  1. State Key Laboratory of Mathematical Engineering and Advanced Computing,Information Engineering University,Zhengzhou 450000,China
  • Online:2022-11-10 Published:2022-11-21
  • About author:XIE Hao-shan,born in 1998,postgra-duate.His main research interest is quantum computer.
    LIU Xiao-nan,born in 1977,Ph.D,associate professor,master supervisor,is a member of China Computer Federation.His main research interests include quantum computer and high-perfor-mance parallel computation.
  • Supported by:
    National Natural Science Foundation of China(61972413,61701539).

摘要: 量子计算天然的叠加性和纠缠性使其具有经典计算技术难以比拟的并行计算能力,基于量子计算强大的并行能力,某些已知的量子算法处理问题的速度要快于经典算法。然而现阶段由于量子计算机的研制还处于发展阶段,想要在量子计算机上进行算法实验的需求还不能被满足,因此可以在经典计算机上对量子算法进行经典模拟。HHL算法常用来解决线性系统的方程问题,其被广泛应用在数据处理、数值计算、最优化问题等领域。本文基于经典的计算机平台,通过高级编程语言C++对HHL算法进行模拟实现,并采用OpenMP并行编程模型对算法进行并行加速。实现了HHL算法模拟解决4×4,8×8,16×16矩阵的线性方程组,并且对算法进行了加速处理。

关键词: HHL算法, OpenMP, 并行加速, 经典模拟

Abstract: Due to its natural superposition and entanglement,quantum computing has parallel computing capability that is incomparable to classical computing technologies.Based on the powerful parallel capability of quantum computing,some known quantum algorithms are faster than classical algorithms in processing problems.However,at this stage,because quantum computers is still in the development stage,the demand for algorithm experiments on quantum computers cannot be met.Therefore,quantum algorithms can be classically simulated on classical computers.HHL algorithm is used to solve the equation problem of linear system and it is widely used in data processing,numerical calculation,optimization problem and other fields.Based on the classic computer platform,HHL algorithm is simulated with C++,and the parallel programming model of OpenMP is used to accele-rate the algorithm.Realizing the HHL algorithm simulation to solve the linear equations of 4×4,8×8,16×16 matrix and realize the acceleration of the algorithm.

Key words: HHL algorithm, OpenMP, Parallel acceleration, Classic simulation

中图分类号: 

  • TP385
[1]HARROW A W,HASSIDIM A,LlOYD S.Quantum Algorithm for Linear Systems of Equations[J].arXiv:103,150502,2009.
[2]CAI X D,WEEDBROOK C,SU Z E,et al.Experimental Quantum Computing to Solve Systems of Linear Equations[J].Physical Review Letters,2013,110(23):230501.
[3]DUTTAS,SUAU A,DUTTA S,et al.Quantum circuit design methodology for multiple linear regression[J].IET Quantum Communication,2020,1(2):55-61.
[4]CAO Y,DASKIN A,FRANKEL S,et al.Quantum circuit design for solving linear systems of equations[J].Molecular Phy-sics,2012,110(15/16):1675-1680.
[5]MIAO X.Universal construction of unitary transformation ofquantum computation with one- and two-body interactions[J/OL].https://arxiv.org/pdf/quant-ph/0003068.pdf.
[6]LIU X X.HUANG P F.OpenMP program for heterogeneoussystems is automatically generated[J].Journal of Information Engineering University,2012,13(4):489-495.
[7]ZHAO H,XU J G.Research on parallel ant colony algorithm based on OpenMP multi-core architecture[J].Microcomputers and Applications,2011,30(16):6-8,11.
[8]SUAU A.Working 4×4 HHL implementation Zenodo[EB/OL].https://doi.org/10.5281/zenodo.1480660.
[9]LIU X N,JING L N,WANG L X,et al.Large-scale quantum Fourier transform simulation based on Shenwei 26010 processor[J].Computer Science,2020,47(8):93-97.
[10]ZHANG P.Research on quantum computingSimulation method based on CPU+GPU heterogeneous cluster[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2016.
[11]YORAN N,SHORT A J.Efficient classical simulation of the approximate quantum Fourier transform[J].Physical Review A,2007,76(4):538-538.
[12]OULAND A,FEFFERMAN B,NIRKHE C,et al.On the complexity and verification of quantum random circuit sampling[J].Nature Physics,2019,15(2):159-163.
[13]CHEN Z Y,ZHOU Q,XUE C,et al.64-qubit quantum circuit simulation[J].Science Bulletin,2018.
[14]CHEN J,ZHANG F,HUANG C,et al.Classical Simulation of Intermediate-Size Quantum Circuits[J].arXiv:1805.01450,2018.
[15]WUJ,LIU Y,ZHANG B,et al.A benchmark test of boson sampling on Tianhe-2 supercomputer[J].National Science Review,2018,5(5):715-720.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!