量子计算系统软件研究综述
作者:
作者简介:

谢磊(1996-),男,博士生,主要研究领域为量子计算编译,错误减缓;翟季冬(1981-),男,博士,副教授,博士生导师,CCF高级会员,主要研究领域为高性能计算,编译优化,性能评测

通讯作者:

翟季冬,E-mail:zhaijidong@tsinghua.edu.cn

基金项目:

国家自然科学基金(62225206)


Survey on Quantum Computing System Software
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [81]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    量子计算理论上有望解决诸多经典难解问题, 近年来量子计算机的快速发展正推动这一理论进入实践. 然而, 当前硬件中繁多的错误会造成计算结果出错, 严重限制了量子计算机解决实际问题的能力. 量子计算系统软件位于应用与硬件之间, 充分挖掘系统软件在硬件错误减缓方面的潜力, 对于近期实现有实用价值的量子计算而言至关重要. 由此, 近期涌现了一批量子计算系统软件研究工作. 将这些工作归纳入编译器、运行时系统和调试器3个范畴, 通过对它们的分析总结, 梳理量子计算系统软件的研究现状, 揭示其在硬件错误减缓方面的重要作用. 并对未来的研究方向进行展望.

    Abstract:

    Quantum computing is expected to solve many typical and difficult problems in theory. The rapid development of quantum computers in recent years is pushing the theory into practice. However, numerous errors in current hardware can cause incorrect computational results, which severely limit the ability of quantum computers to solve practical problems. Quantum computing system software lies between applications and hardware. In addition, tapping the full potential of the system software in mitigating hardware errors is crucial to realizing practical quantum computing in the near future. As a result, many research works on quantum computing system software have recently emerged. This study classifies them into three categories: compilers, runtime systems, and debuggers. Through an in-depth analysis of these works, the study sorts out the research status of quantum computing system software and reveals their important roles in mitigating hardware errors. This study also looks forward to future research directions.

    参考文献
    [1] Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997, 26(5): 1484–1509. [doi: 10.1137/S0097539795293172]
    [2] Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Biswas R, Boixo S, Brandao FGSL, Buell DA, Burkett B, Chen Y, Chen ZJ, Chiaro B, Collins R, Courtney W, Dunsworth A, Farhi E, Foxen B, Fowler A, Gidney C, Giustina M, Graff R, Guerin K, Habegger S, Harrigan MP, Hartmann MJ, Ho A, Hoffmann M, Huang T, Humble TS, Isakov SV, Jeffrey E, Jiang Z, Kafri D, Kechedzhi K, Kelly J, Klimov PV, Knysh S, Korotkov A, Kostritsa F, Landhuis D, Lindmark M, Lucero E, Lyakh D, Mandrà S, McClean JR, McEwen M, Megrant A, Mi X, Michielsen K, Mohseni M, Mutus J, Naaman O, Neeley M, Neill C, Niu MY, Ostby E, Petukhov A, Platt JC, Quintana C, Rieffel EG, Roushan P, Rubin NC, Sank D, Satzinger KJ, Smelyanskiy V, Sung KJ, Trevithick MD, Vainsencher A, Villalonga B, White T, Yao ZJ, Yeh P, Zalcman A, Neven H, Martinis JM. Quantum supremacy using a programmable superconducting processor. Nature, 2019, 574(7779): 505–510. [doi: 10.1038/s41586-019-1666-5]
    [3] IBM. IBM quantum. 2022. https://quantum-computing.ibm.com
    [4] Preskill J. Quantum computing in the NISQ era and beyond. Quantum, 2018, 2: 79. [doi: 10.22331/q-2018-08-06-79]
    [5] Nielsen MA, Chuang IL. Quantum Computation and Quantum Information: 10th Anniversary Edition. New York: Cambridge University Press, 2010.
    [6] Huang HL, Wu DC, Fan DJ, Zhu XB. Superconducting quantum computing: A review. Science China Information Sciences, 2020, 63(8): 180501. [doi: 10.1007/s11432-020-2881-9]
    [7] Bruzewicz CD, Chiaverini J, McConnell R, Sage JM. Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 2019, 6(2): 021314. [doi: 10.1063/1.5088164]
    [8] O’Brien JL. Optical quantum computing. Science, 2007, 318(5856): 1567–1570. [doi: 10.1126/science.1142892]
    [9] Jazaeri F, Beckers A, Tajalli A, Sallese JM. A review on quantum computing: From qubits to front-end electronics and cryogenic MOSFET physics. In: Proc. of the 26th Int’l Conf. on Mixed Design of Integrated Circuits and Systems. Rzeszow: IEEE, 2019. 15–25.
    [10] Barends R, Kelly J, Megrant A, Sank D, Jeffrey E, Chen Y, Yin Y, Chiaro B, Mutus J, Neill C, O’Malley P, Roushan P, Wenner J, White TC, Cleland AN, Martinis JM. Coherent Josephson Qubit suitable for scalable quantum integrated circuits. Physical Review Letters, 2013, 111(8): 080502. [doi: 10.1103/PhysRevLett.111.080502]
    [11] Murali P, Linke NM, Martonosi M, Abhari AJ, Nguyen NH, Alderete CH. Full-stack, real-system quantum computer studies: Architectural comparisons and design insights. In: Proc. of the 46th Int’l Symp. on Computer Architecture. Phoenix: Association for Computing Machinery, 2019. 527–540.
    [12] Kwon S, Tomonaga A, Lakshmi Bhai G, Devitt SJ, Tsai JS. Gate-based superconducting quantum computing. Journal of Applied Physics, 2021, 129(4): 041102. [doi: 10.1063/5.0029735]
    [13] Sarovar M, Proctor T, Rudinger K, Young K, Nielsen E, Blume-Kohout R. Detecting crosstalk errors in quantum information processors. Quantum, 2020, 4: 321. [doi: 10.22331/q-2020-09-11-321]
    [14] Xie L, Zhai JD, Zheng WM. Mitigating crosstalk in quantum computers through commutativity-based instruction reordering. In: Proc. of the 58th ACM/IEEE Design Automation Conf. San Francisco: IEEE, 2021. 445–450.
    [15] Aliferis P, Gottesman D, Preskill J. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Information & Computation, 2006, 6(2): 97–165.
    [16] Google. Google devices. 2022. https://quantumai.google/cirq/google/devices
    [17] Rigetti. Rigetti quantum computing platform. 2021. https://qcs.rigetti.com/qpus
    [18] Wright K, Beck KM, Debnath S, Amini JM, Nam Y, Grzesiak N, Chen JS, Pisenti NC, Chmielewski M, Collins C, Hudek KM, Mizrahi J, Wong-Campos JD, Allen S, Apisdorf J, Solomon P, Williams M, Ducore AM, Blinov A, Kreikemeier SM, Chaplin V, Keesan M, Monroe C, Kim J. Benchmarking an 11-qubit quantum computer. Nature Communications, 2019, 10(1): 5464. [doi: 10.1038/s41467-019-13534-2]
    [19] IonQ. Best practices for using IonQ hardware. 2022. https://ionq.com/best-practices
    [20] Shende VV, Markov IL, Bullock SS. Minimal universal two-qubit controlled-NOT-based circuits. Physical Review A, 2004, 69(6): 062321. [doi: 10.1103/PhysRevA.69.062321]
    [21] Barenco A, Bennett CH, Cleve R, DiVincenzo DP, Margolus N, Shor P, Sleator T, Smolin JA, Weinfurter H. Elementary gates for quantum computation. Physical Review A, 1995, 52(5): 3457–3467. [doi: 10.1103/PhysRevA.52.3457]
    [22] Vartiainen JJ, Möttönen M, Salomaa MM. Efficient decomposition of quantum gates. Physical Review Letters, 2004, 92(17): 177902. [doi: 10.1103/PhysRevLett.92.177902]
    [23] Möttönen M, Vartiainen JJ, Bergholm V, Salomaa MM. Quantum circuits for general multiqubit gates. Physical Review Letters, 2004, 93(13): 130502. [doi: 10.1103/PhysRevLett.93.130502]
    [24] Möttönen M, Vartiainen JJ. Decompositions of general quantum gates. In: Shannon S, ed. Trends in Quantum Computing Research. New York: Nova Science Publishers, 2006.
    [25] Shende VV, Bullock SS, Markov IL. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(6): 1000–1010. [doi: 10.1109/TCAD.2005.855930]
    [26] Drury B, Love P. Constructive quantum Shannon decomposition from Cartan involutions. Journal of Physics A: Mathematical and Theoretical, 2008, 41(39): 395305. [doi: 10.1088/1751-8113/41/39/395305]
    [27] Qiskit Developers. Qiskit: An open-source framework for quantum computing. 2022. https://qiskit.org
    [28] Cirq Developers. Cirq. 2022. https://quantumai.google/cirq
    [29] Rigetti Quilc Developers. Rigetti qulic. 2022. https://docs.rigetti.com/qcs
    [30] Jones T, Benjamin SC. Robust quantum compilation and circuit optimisation via energy minimisation. Quantum, 2022, 6: 628. [doi: 10.22331/q-2022-01-24-628]
    [31] Davis MG, Smith E, Tudor A, Sen K, Siddiqi I, Iancu C. Heuristics for quantum compiling with a continuous gate set. arXiv:1912.02727, 2019.
    [32] Lao LL, Murali P, Martonosi M, Browne D. Designing calibration and expressivity-efficient instruction sets for quantum computing. In: Proc. of the 48th ACM/IEEE Annual Int’l Symp. on Computer Architecture. Valencia: IEEE, 2021. 846–859.
    [33] Szyprowski M, Kerntopf P. Low quantum cost realization of generalized Peres and Toffoli gates with multiple-control signals. In: Proc. of the 13th IEEE Int’l Conf. on Nanotechnology. Beijing: IEEE, 2013. 802–807.
    [34] Abdollahi A, Saeedi M, Pedram M. Reversible logic synthesis by quantum rotation gates. Quantum Information and Computation, 2013, 13(9–10): 771–792.
    [35] Amy M, Maslov D, Mosca M. Polynomial-time T-depth optimization of Clifford+T circuits via matroid partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2014, 33(10): 1476–1489. [doi: 10.1109/TCAD.2014.2341953]
    [36] Maslov D. Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Physical Review A, 2016, 93(2): 022311. [doi: 10.1103/PhysRevA.93.022311]
    [37] He Y, Luo MX, Zhang E, Wang HK, Wang XF. Decompositions of n-qubit Toffoli gates with linear circuit complexity. International Journal of Theoretical Physics, 2017, 56(7): 2350–2361. [doi: 10.1007/s10773-017-3389-4]
    [38] Siraichi MY, dos Santos VF, Collange C, Pereira FMQ. Qubit allocation. In: Proc. of the 2018 Int’l Symp. on Code Generation and Optimization. New York: Association for Computing Machinery, 2018. 113–125.
    [39] Booth KEC, Do M, Beck JC, Rieffel E, Venturelli D, Frank J. Comparing and integrating constraint programming and temporal planning for quantum circuit compilation. In: Proc. of the 28th Int’l Conf. on Automated Planning and Scheduling. Delft: AAAI Press, 2018. 366–374.
    [40] Bhattacharjee D, Saki AA, Alam M, Chattopadhyay A, Ghosh S. MUQUT: Multi-constraint quantum circuit mapping on NISQ computers: Invited paper. In: Proc. of the 2019 IEEE/ACM Int’l Conf. on Computer-aided Design. Westminster: IEEE, 2019. 1–7.
    [41] Murali P, Baker JM, Javadi-Abhari A, Chong FT, Martonosi M. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In: Proc. of the 24th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Providence: Association for Computing Machinery, 2019. 1015–1029.
    [42] Guerreschi GG, Park J. Two-step approach to scheduling quantum circuits. Quantum Science and Technology, 2018, 3(4): 045003. [doi: 10.1088/2058-9565/aacf0b]
    [43] Li GS, Ding YF, Xie Y. Tackling the qubit mapping problem for NISQ-Era quantum devices. In: Proc. of the 24th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Providence: Association for Computing Machinery, 2019. 1001–1014.
    [44] Zulehner A, Paler A, Wille R. An efficient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(7): 1226–1236. [doi: 10.1109/TCAD.2018.2846658]
    [45] Tannu SS, Qureshi MK. Not all qubits are created equal: A case for variability-aware policies for NISQ-Era quantum computers. In: Proc. of the 24th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Providence: Association for Computing Machinery, 2019. 987–999.
    [46] Ash-Saki A, Alam M, Ghosh S. QURE: Qubit re-allocation in noisy intermediate-scale quantum computers. In: Proc. of the 56th ACM/IEEE Design Automation Conf. Las Vegas: IEEE, 2019. 1–6.
    [47] 窦星磊, 刘磊, 陈岳涛. 面向超导量子计算机的程序映射技术研究. 计算机研究与发展, 2021, 58(9): 1856–1874 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2021.20210314]
    Dou XL, Liu L, Chen YT. An investigation into quantum program mapping on superconducting quantum computers. Journal of Computer Research and Development, 2021, 58(9): 1856–1874 (in Chinese with English abstract). [doi: 10.7544/issn1000-1239.2021.20210314]
    [48] Vatan F, Williams C. Optimal quantum circuits for general two-qubit gates. Physical Review A, 2004, 69(3): 032315. [doi: 10.1103/PhysRevA.69.032315]
    [49] Shi YN, Leung N, Gokhale P, Rossi Z, Schuster DI, Hoffmann H, Chong FT. Optimized compilation of aggregated instructions for realistic quantum computers. In: Proc. of the 24th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Providence: Association for Computing Machinery, 2019. 1031–1044.
    [50] Murali P, Mckay DC, Martonosi M, Javadi-Abhari A. Software mitigation of crosstalk on noisy intermediate-scale quantum computers. In: Proc. of the 25th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Lausanne: Association for Computing Machinery, 2020. 1001–1016.
    [51] Ding YS, Gokhale P, Lin SF, Rines R, Propson T, Chong FT. Systematic crosstalk mitigation for superconducting qubits via frequency-aware compilation. In: Proc. of the 53rd Annual IEEE/ACM Int’l Symp. on Microarchitecture. Athens: IEEE, 2020. 201–214.
    [52] Tannu SS, Qureshi M. Ensemble of diverse mappings: Improving reliability of quantum computers by orchestrating dissimilar mistakes. In: Proc. of the 52nd Annual IEEE/ACM Int’l Symp. on Microarchitecture. Columbus: Association for Computing Machinery, 2019. 253–265.
    [53] Tannu SS, Qureshi MK. Mitigating measurement errors in quantum computers by exploiting state-dependent bias. In: Proc. of the 52nd Annual IEEE/ACM Int’l Symp. on Microarchitecture. Columbus: Association for Computing Machinery, 2019. 279–290.
    [54] Qiskit. Measurement error mitigation. 2022. https://learn.qiskit.org/course/quantum-hardware/measurement-error-mitigation
    [55] Zlokapa A, Gheorghiu A. A deep learning model for noise prediction on near-term quantum devices. arXiv:2005.10811, 2020.
    [56] Patel T, Tiwari D. Qraft: Reverse your quantum circuit and know the correct program output. In: Proc. of the 26th ACM Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2021. 443–455.
    [57] Czarnik P, Arrasmith A, Coles PJ, Cincio L. Error mitigation with Clifford quantum-circuit data. Quantum, 2021, 5: 592. [doi: 10.22331/q-2021-11-26-592]
    [58] Li Y, Benjamin SC. Efficient variational quantum simulator incorporating active error minimization. Physical Review X, 2017, 7(2): 021050. [doi: 10.1103/PhysRevX.7.021050]
    [59] Temme K, Bravyi S, Gambetta JM. Error mitigation for short-depth quantum circuits. Physical Review Letters, 2017, 119(18): 180509. [doi: 10.1103/PhysRevLett.119.180509]
    [60] Kandala A, Temme K, Córcoles AD, Mezzacapo A, Chow JM, Gambetta JM. Error mitigation extends the computational reach of a noisy quantum processor. Nature, 2019, 567(7749): 491–495. [doi: 10.1038/s41586-019-1040-7]
    [61] Endo S, Benjamin SC, Li Y. Practical quantum error mitigation for near-future applications. Physical Review X, 2018, 8(3): 031027. [doi: 10.1103/PhysRevX.8.031027]
    [62] Peng TY, Harrow AW, Ozols M, Wu XD. Simulating large quantum circuits on a small quantum computer. Physical Review Letters, 2020, 125(15): 150504. [doi: 10.1103/PhysRevLett.125.150504]
    [63] Tang W, Tomesh T, Suchara M, Larson J, Martonosi M. CutQC: Using small Quantum computers for large quantum circuit evaluations. In: Proc. of the 26th ACM Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2021. 473–486.
    [64] Huang YP, Martonosi M. Statistical assertions for validating patterns and finding bugs in quantum programs. In: Proc. of the 46th Annual Int’l Symp. on Computer Architecture. Phoenix: IEEE, 2019. 541–553.
    [65] Li GS, Zhou L, Yu NK, Ding YF, Ying MS, Xie Y. Projection-based runtime assertions for testing and debugging Quantum programs. Proceedings of the ACM on Programming Languages, 2020, 4(OOPSLA): 150. [doi: 10.1145/3428218] (查阅所有网上资料, 请联系作者核对期号信息)
    [66] Liu J, Zhou HY. Systematic approaches for precise and approximate quantum state runtime assertion. In: Proc. of the 2021 IEEE Int’l Symp. on High-performance Computer Architecture. Seoul: IEEE, 2021. 179–193.
    [67] Liu J, Byrd GT, Zhou HY. Quantum circuits for dynamic runtime assertions in quantum computation. In: Proc. of the 25th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Lausanne: Association for Computing Machinery, 2020. 1017–1030.
    [68] Paradis A, Bichsel B, Steffen S, Vechev M. Unqomp: Synthesizing uncomputation in quantum circuits. In: Proc. of the 42nd ACM SIGPLAN Int’l Conf. on Programming Language Design and Implementation. New York: Association for Computing Machinery, 2021. 222–236.
    [69] Ding YS, Wu XC, Holmes A, Wiseth A, Franklin D, Martonosi M, Chong FT. SQUARE: Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation. In: Proc. of the 47th ACM/IEEE Annual Int’l Symp. on Computer Architecture. Valencia: IEEE, 2020. 570–583.
    [70] Dobšíček M, Johansson G, Shumeiko V, Wendin G. Arbitrary accuracy iterative quantum phase estimation algorithm using a single ancillary qubit: A two-qubit benchmark. Physical Review A, 2007, 76(3): 030306. [doi: 10.1103/PhysRevA.76.030306]
    [71] Steane AM. Error correcting codes in quantum theory. Physical Review Letters, 1996, 77(5): 793–797. [doi: 10.1103/PhysRevLett.77.793]
    [72] Paetznick A, Svore KM. Repeat-until-success: Non-deterministic decomposition of single-qubit unitaries. Quantum Information & Computation, 2014, 14(15–16): 1277–1301.
    [73] Fu X, Yu JT, Su X, Jiang HR, Wu H, Cheng FC, Deng X, Zhang JR, Jin L, Yang YH, Xu L, Hu CC, Huang AQ, Huang GY, Qiang XG, Deng MT, Xu P, Xu WX, Liu WW, Zhang Y, Deng YX, Wu JJ, Feng Y. Quingo: A programming framework for heterogeneous quantum-classical computing with NISQ features. ACM Transactions on Quantum Computing, 2021, 2(4): 19. [doi: 10.1145/3483528]
    [74] Ittah D, Häner T, Kliuchnikov V, Hoefler T. QIRO: A static single assignment-based quantum program representation for optimization. ACM Transactions on Quantum Computing, 2022, 3(3): 14. [doi: 10.1145/3491247]
    [75] Cross A, Javadi-Abhari A, Alexander T, De Beaudrap N, Bishop LS, Heidel S, Ryan CA, Sivarajah P, Smolin J, Gambetta JM, Johnson BR. OpenQASM 3: A broader and deeper quantum assembly language. ACM Transactions on Quantum Computing, 2022, 3(3): 12. [doi: 10.1145/3505636]
    [76] Córcoles AD, Takita M, Inoue K, Lekuch S, Minev ZK, Chow JM, Gambetta JM. Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits. Physical Review Letters, 2021, 127(10): 100501. [doi: 10.1103/PhysRevLett.127.100501]
    [77] Pino JM, Dreiling JM, Figgatt C, Gaebler JP, Moses SA, Allman MS, Baldwin CH, Foss-Feig M, Hayes D, Mayer K, Ryan-Anderson C, Neyenhuis B. Demonstration of the trapped-ion quantum CCD computer architecture. Nature, 2020, 592(7853): 209–213. [doi: 10.1038/s41586-021-03318-4]
    [78] Botelho L, Glos A, Kundu A, Miszczak JA, Salehi Ö, Zimborás Z. Error mitigation for variational quantum algorithms through mid-circuit measurements. Physical Review A, 2022, 105(2): 022441. [doi: 10.1103/PhysRevA.105.022441]
    [79] Cincio L, Rudinger K, Sarovar M, Coles PJ. Machine learning of noise-resilient quantum circuits. PRX Quantum, 2021, 2(1): 010324. [doi: 10.1103/PRXQuantum.2.010324]
    [80] Fösel T, Tighineanu P, Weiss T, Marquardt F. Reinforcement learning with neural networks for quantum feedback. Physical Review X, 2018, 8(3): 031084. [doi: 10.1103/PhysRevX.8.031084]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

谢磊,翟季冬.量子计算系统软件研究综述.软件学报,2024,35(1):1-18

复制
分享
文章指标
  • 点击次数:1841
  • 下载次数: 5364
  • HTML阅读次数: 2948
  • 引用次数: 0
历史
  • 收稿日期:2022-04-08
  • 最后修改日期:2022-09-17
  • 在线发布日期: 2023-07-05
  • 出版日期: 2024-01-06
文章二维码
您是第20381073位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号