量子计算模拟及优化方法综述

doi:10.19678/j.issn.1000-3428.0061787

摘要/Abstract

摘要： 在处理某些大规模并行问题时，量子计算因量子位独特的叠加态和纠缠态特性，相比经典计算机在并行处理方面具有更明显的优势。现阶段，物理量子比特计算机受限于可扩展性、相干时间和量子门操作精度，在经典计算机上开展量子计算模拟成为研究量子优越性和量子算法的有效途径。然而，随着量子比特数的增加，模拟所需的计算机资源呈指数增长。因此，研究大规模量子计算模拟在保证计算准确度、精度及效率的情况下减少模拟所需资源具有重要意义。从量子比特、量子门、量子线路、量子操作系统等方面展开，阐述量子计算的基本原理和背景知识。同时总结基于经典计算机的量子计算模拟基本方法，分析不同方法的设计思路和优缺点，列举目前常见的量子计算模拟器。在此基础上，针对量子计算模拟的通信开销问题，从节点拆分和通信优化2个方面出发，讨论基于超级计算机集群的量子计算模拟优化方法。

关键词: 量子计算, 量子线路, 概率幅模拟, 量子计算模拟器, 超级计算机

Abstract: Through superposition and entanglement, a quantum computing displays significant advantages over classical computers in dealing with problems that require large-scale parallel processing capabilities.At present, a physical quantum computer is limited in scalability, coherence time, and precision of quantum gate operations, so it is feasible to simulate quantum computing on a classical computer for studying quantum advantage and quantum algorithms.However, the computer resources required for quantum computing simulation grow exponentially with the number of qubits.Therefore, it is of great importance to study how to reduce the resources required for large-scale simulation with ensured computational accuracy, precision and efficiency.This paper describes the basic principles and background knowledge of quantum computing, including qubits, quantum gates, quantum circuits and quantum operating systems.Meanwhile, this paper summarizes the classical computer-based methods for simulating quantum computing, and analyzes their design ideas, advantages and disadvantages.Some commonly used simulators are also listed.On this basis, this paper discusses the communication overhead problem of quantum computing simulation, and presents some supercomputer-based methods for optimizing quantum computing simulation from the two aspects of node analysis and communication optimization.

Key words: quantum computing, quantum circuit, amplitude simulation, quantum computing simulator, supercomputer

中图分类号:

TP391

喻志超, 李扬中, 刘磊, 冯圣中. 量子计算模拟及优化方法综述[J]. 计算机工程, 2022, 48(1): 1-11.

YU Zhichao, LI Yangzhong, LIU Lei, FENG Shengzhong. Survey of Quantum Computing Simulation and Optimization Methods[J]. Computer Engineering, 2022, 48(1): 1-11.

http://www.ecice06.com/CN/Y2022/V48/I1/1

图/表 10

20220108120549

20220108120554

20220108120558

20220108120751

20220108120755

20220108120759

20220108120803

20220108120808

20220108120811

20220108120815

参考文献

[1] GROVER L K.A fast quantum mechanical algorithm for database search[C]//Proceedings of the 28th Annual ACM Symposium on Theory of Computing.New York, USA:ACM Press, 1996:212-219.
[2] BABBUSH R, MCCLEAN J, WECKER D, et al.Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation[J].Physical Review A, 2015, 91(2):1-18.
[3] BAUER B, WECKER D, MILLIS A J, et al.Hybrid quantum-classical approach to correlated materials[J].Physical Review X, 2016, 6(3):1-11.
[4] BIAMONTE J, WITTEK P, PANCOTTI N, et al.Quantum machine learning[J].Nature, 2017, 549(7671):195-202.
[5] DOU X L, LIU L.A new qubits mapping mechanism for multi-programming quantum computing[C]//Proceedings of International Conference on Parallel Architectures and Compilation Techniques.New York, USA:ACM Press, 2020:349-350.
[6] LIU L, DOU X L.QuCloud:a new qubit mapping mechanism for multi-programming quantum computing in cloud environment[C]//Proceedings of International Symposium on High Performance Computer Architecture.Washington D.C., USA:IEEE Press, 2021:167-178.
[7] PRESKILL J.Quantum computing in the NISQ era and beyond[J].Quantum, 2018, 2:79.
[8] LI G S, DING Y, XIE Y.Tackling the qubit mapping problem for NISQ-era quantum devices[C]//Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems.New York, USA:ACM Press, 2019:1001-1014.
[9] ARUTE F, ARYA K, BABBUSH R, et al.Quantum supremacy using a programmable superconducting processor[J].Nature, 2019, 574(7779):505-510.
[10] HUANG C J, ZHANG F, NEWMAN M, et al.Classical simulation of quantum supremacy circuits[EB/OL].(2020-05-14)[2021-03-10].https://arxiv.org/pdf/2005.06787v1.pdf.
[11] CHEN Z Y, ZHOU Q, XUE C, et al.64-qubit quantum circuit simulation[J].Science Bulletin, 2018, 63(15):964-971.
[12] ATAIDES J P B, TUCKETT D K, BARTLETT S D, et al.The XZZX surface code[J].Nature Communications, 2021, 12(1):1-12.
[13] ALMUDEVER C G, LAO L, FU X, et al.The engineering challenges in quantum computing[C]//Proceedings of DATE Conference.Washington D.C., USA:IEEE Press, 2017:836-845.
[14] 孙晓明.量子计算若干前沿问题综述[J].中国科学:信息科学, 2016, 46(8):982-1002. SUN X M.A survey on quantum computing[J].SCIENTIA SINICA Informationis, 2016, 46(8):982-1002.(in Chinese)
[15] 范桁.量子计算与量子模拟[J].物理学报, 2019, 67(12):1-10. FAN H.Quantum computation and quantum simulation[J].Acta Physicas Sinica, 2019, 67(12):1-10.(in Chinese)
[16] STEIGER D S, HANER T, TROYER M.ProjectQ:an open source software framework for quantum computing[J].Quantum, 2018, 2:49.
[17] SMELYANSKIY M, SAWAYA N P D, ASPURU G A.qHiPSTER:the quantum high performance software testing environment[EB/OL].(2016-05-12)[2021-03-10].https://www.researchgate.net/profile/Nicolas-Sawaya/publication/301856456_qHiPSTER_The_Quantum_High_Performance_Software_Testing_Environment/links/5834993808aef19cb81f8d85/qHiPSTER-The-Quantum-High-Performance-Software-Testing-Environment.pdf.
[18] JONES T, BROWN A, BUSH I, et al.QuEST and high performance simulation of quantum computers[J].Scientific Reports, 2019, 9(1):1-11.
[19] NIELSEN M A, CHUANG I.Quantum computation and quantum information[M].Cambridge, UK:Cambridge University Press, 2002.
[20] BOIXO S, ISAKOV S V, SMELYANSKIY V N, et al.Characterizing quantum supremacy in near-term devices[J].Nature Physics, 2018, 14(6):595-600.
[21] BREMNER M J, JOZSA R, SHEPHERD D J.Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy[J].Proceedings of the Royal Society A:Mathematical, Physical and Engineering Sciences, 2011, 467(2126):459-472.
[22] AARONSON S, ARKHIPOV A.The computational complexity of linear optics[C]//Proceedings of the 43rd Annual ACM Symposium on Theory of Computing.New York, USA:ACM Press, 2011:333-342.
[23] WU B J, CHENG B, JIA F, et al.Speedup in classical simulation of Gaussian Boson sampling[J].Science Bulletin, 2020, 65(10):832-841.
[24] BOULAND 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.
[25] ZLOKAPA A, BOIXO S, LIDAR D.Boundaries of quantum supremacy via random circuit sampling[EB/OL].(2020-05-05)[2021-03-10].http://arxiv.org/pdf/2005.02464.pdf.
[26] CORRIGAN G H, WU D J, BONEH D.Quantum operating systems[C]//Proceedings of the 16th Workshop on Hot Topics in Operating Systems.New York, USA:ACM Press, 2017:76-81.
[27] AARONSON S, CHEN L J.Complexity-theoretic foundations of quantum supremacy experiments[C]//Proceedings of the 32nd Computational Complexity Conference.New York, USA:ACM Press, 2017:1-67.
[28] FEYNMAN R P.Simulating physics with computers[J].International Journal of Theoretical Physics, 1982, 21:467-488.
[29] WU X C, DI S, DASGUPTA E M, et al.Full-state quantum circuit simulation by using data compression[C]//Proceedings of 2019 International Conference for High Performance Computing, Networking, Storage and Analysis.Washington D.C., USA:IEEE Press, 2019:1-24.
[30] RAEDT H, JIN F, WILLSCH D, et al.Massively parallel quantum computer simulator, eleven years later[J].Computer Physics Communications, 2019, 237:47-61.
[31] MCCASKEY A, DUMITRESCU E, CHEN M, et al.Validating quantum-classical programming models with tensor network simulations[J].PLoS One, 2018, 13(12):1-10.
[32] GUO C, ZHAO Y W, HUANG H L.Verifying random quantum circuits with arbitrary geometry using tensor network states algorithm[J].Physical Review Letters, 2021, 126(7):1-9.
[33] PEDNAULT E, GUNNELS J A, NANNICINI G, et al.Pareto-efficient quantum circuit simulation using tensor contraction deferral[EB/OL].(2017-10-16)[2021-03-10].https://arxiv.org/pdf/1710.05867v4.pdf.
[34] BOIXO S, ISAKOV S V, SMELYANSKIY V N, et al.Simulation of low-depth quantum circuits as complex undirected graphical models[EB/OL].(2017-12-14)[2021-03-10].https://arxiv.org/pdf/1712.05384.pdf.
[35] CHEN J X, ZHANG F, HUANG C P, et al.Classical simulation of intermediate-size quantum circuits[EB/OL].(2018-05-03)[2021-03-10].https://arxiv.org/pdf/1805. 01450v2.pdf.
[36] PAN F, ZHANG P.Simulating the Sycamore quantum supremacy circuits[EB/OL].(2021-03-04)[2021-03-10].https://arxiv.org/pdf/2103.03074v1.pdf.
[37] WU X Y, XU Y L, YU Y F, et al.Fault-tolerantly implementing dense rotation operations based on non-stabilizer states[J].Acta Physica Sinica, 2014, 63(22):1-7.
[38] PROCTOR T J, CARIGNAN D A, RUDINGER K, et al.Direct randomized benchmarking for multiqubit devices[J].Physical Review Letters, 2019, 123(3):1-10.
[39] BLUME K R, GAMBLE J K, NIELSEN E, et al.Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography[J].Nature Communications, 2017, 8(1):1-13.
[40] WANG Z, CHEN Y, SONG Z, et al.Scalable evaluation of quantum-circuit error loss using Clifford sampling[J].Physical Review Letters, 2021, 126(8):1-10.
[41] AARONSON S, GOTTESMAN D.Improved simulation of stabilizer circuits[J].Physical Review A, 2004, 70(5):1-8.
[42] BRAVYI S, GOSSET D.Improved classical simulation of quantum circuits dominated by Clifford gates[J].Physical Review Letters, 2016, 116(25):1-10.
[43] BU K, KOH D E.Efficient classical simulation of Clifford circuits with nonstabilizer input states[J].Physical Review Letters, 2019, 123(17):1-9.
[44] HE X Y, GUAN Z J, DING F.The mapping and optimization method of quantum circuits for Clifford+T gate[J].Journal of Applied Mathematics and Physics, 2019, 7(11):2796-2810.
[45] GAO X, DUAN L M.Efficient classical simulation of noisy quantum computation[EB/OL].(2018-10-07)[2021-03-10].https://arxiv.org/pdf/1810.03176.pdf.
[46] CHEN Y T, COLLIN F, ROBERT M P.Low-rank density-matrix evolution for noisy quantum circuits[J].npj Quantum Information, 2021, 7(1):1-12.
[47] CROSS A.The IBM Q experience and QISKit open-source quantum computing software[C]//Proceedings of 2018 APS March Meeting.Los Angeles, USA:American Physical Society, 2018:1-10.
[48] WILLE R, METER R, NAVEH Y.IBM's Qiskit tool chain:working with and developing for real quantum computers[C]//Proceedings of 2019 Design, Automation & Test in Europe Conference & Exhibition.Washington D.C., USA:IEEE Press, 2019:1234-1240.
[49] SICILIA M A, SANCHEZ A S, MORA C M, et al.On the source code structure of quantum code:insights from Q# and QDK[C]//Proceedings of International Conference on the Quality of Information and Communications Technology.Berlin, Germany:Springer, 2020:292-299.
[50] HUAWEI.QC research[EB/OL].[2021-03-10].https://hiq.huaweicloud.com/en.
[51] GOOGLE.Cirq[EB/OL].[2021-03-10].https://quantumai.google/cirq.
[52] ORIGIN QUANTUM.QPanda[EB/OL].[2021-03-10].http://www.originqc.com.cn/QPanda/download.html.
[53] GUERRESCHI G G, HOGABOAM J, BARUFFA F, et al.Intel quantum simulator:a cloud-ready high-performance simulator of quantum circuits[J].Quantum Science and Technology, 2020, 5(3):1-10.
[54] BAIDU.量桨:量子机器学习工具集[EB/OL].[2021-03-10].https://qml.baidu.com.
[55] MARKOV I L, SHI Y Y.Simulating quantum computation by contracting tensor networks[J].SIAM Journal on Computing, 2008, 38(3):963-981.
[56] TANG W, TOMESH T, SUCHARA M, et al.CutQC:using small quantum computers for large quantum circuit evaluations[C]//Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems.New York, USA:ACM Press, 2021:473-486.
[57] LI R L, WU B J, YING M S, et al.Quantum supremacy circuit simulation on Sunway TaihuLight[J].IEEE Transactions on Parallel and Distributed Systems, 2019, 31(4):805-816.
[58] TABAKIN F, BRUNO J D.QCMPI:a parallel environment for quantum computing[J].Computer Physics Communications, 2009, 180(6):948-964.
[59] ZHANG P, YUAN J B, LU X W.Quantum computer simulation on multi-GPU incorporating data locality[C]//Proceedings of International Conference on Algorithms and Architectures for Parallel Processing.Berlin, Germany:Springer, 2015:241-256.

选择文件类型/文献管理软件名称

选择包含的内容