Fast-USYN: Fast Synthesis from Unitary Matrices to High-quality Quantum Circuits
Author:
Affiliation:

Clc Number:

TP311

  • Article
  • | |
  • Metrics
  • |
  • Reference [42]
  • |
  • Related
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Current quantum programs are generally represented by quantum circuits, including various quantum gates. If the program contains gates that are directly represented as unitary matrices, these gates need to be transformed into quantum circuits composed of basic gates. This step is called quantum circuit synthesis. However, current synthesis methods may generate circuits with thousands of gates. The quality of these quantum circuits is low and they are very likely to output incorrect results when deployed to real noisy quantum hardware. When the number of qubits is increased to 8 while ensuring a small number of gates, the quantum circuit synthesis takes weeks or even months. This study proposes a quantum circuit synthesis method, realizing the fast synthesis from unitary matrices to high-quality quantum circuits. Firstly, an iterative method is introduced to approximate the target unitary matrix by inserting circuit modules. During the iteration, a look-ahead strategy with a reward mechanism is proposed to reduce redundant quantum gates. In the acceleration process of quantum circuit synthesis, the study proposes a pruning method to reduce the space of candidate circuit modules. The method first describes the closure of each candidate circuit module to characterize the representation space of the circuit, and then prunes based on the overlap rate of the representation spaces of the modules, thus constructing a small and high-quality candidate set. Furthermore, to reduce the overhead of searching for optimal gate parameters, this study packs the selected candidates with the target unitary into a uniform circuit so that we can quickly obtain the approximation distance by calculating its expectation on the ground state. Experiments show that, compared with the current optimal quantum circuit synthesis methods QuCT and QFAST, this study reduces the number of gates to 37.0%–62.5%, and achieve a 3.7–20.6 times acceleration in the 5 to 8 qubit quantum circuit synthesis.

    Reference
    [1] Yuan C, Carbin M. Tower: Data structures in quantum superposition. Proc. of the ACM on Programming Languages, 2022, 6(OOPSLA2): 134.
    [2] 陈昭昀. 量子程序语言QPanda的设计及应用研究 [博士学位论文]. 合肥: 中国科学技术大学, 2021. [doi: 10.27517/d.cnki.gzkju.2021.002170]
    Chen ZY. Design and application of quantum programming language QPanda [Ph.D. Thesis]. Hefei: University of Science and Technology of China, 2021 (in Chinese with English abstract). [doi: 10.27517/d.cnki.gzkju.2021.002170]
    [3] Younis E, Sen K, Yelick K, Iancu C. QFAST: Conflating search and numerical optimization for scalable quantum circuit synthesis. In: Proc. of the 2021 IEEE Int’l Conf. on Quantum Computing and Engineering. Broomfield: IEEE, 2021. 232–243. [doi: 10.1109/QCE52317.2021.00041]
    [4] 李晖, 韩子傲, 卢凯, 刘述娟, 鞠明媚. 改进量子位初始映射的综合SWAP优化策略. 计算机工程与应用, 2024, 60(14): 66–73.
    Li H, Han ZA, Lu K, Liu SJ, Ju MM. Comprehensive SWAP optimization strategy for improving initial qubit mapping. Computer Engineering and Applications, 2024, 60(14): 66–73 (in Chinese with English abstract).
    [5] Wu TA, Jiang YJ, Fang SY. A robust quantum layout synthesis algorithm with a qubit mapping checker. In: Proc. of the 2022 IEEE/ACM Int’l Conf. on Computer Aided Design. San Diego: IEEE, 2022. 1–9.
    [6] Christensen M, Tzimpragos G, Kringen H, Volk J, Sherwood T, Hardekopf B. PyLSE: A pulse-transfer level language for superconductor electronics. In: Proc. of the 43rd ACM SIGPLAN Int’l Conf. on Programming Language Design and Implementation. San Diego: ACM, 2022. 671–686. [doi: 10.1145/3519939.3523438]
    [7] Gulwani S, Polozov O, Singh R. Program synthesis. Foundations and Trends? in Programming Languages, 2017, 4(1–2): 1–119.
    [8] Wang CL, Cheung A, Bodik R. Synthesizing highly expressive SQL queries from input-output examples. In: Proc. of the 38th ACM SIGPLAN Conf. on Programming Language Design and Implementation. Barcelona: ACM, 2017. 452–466. [doi: 10.1145/3062341.3062365]
    [9] 张健, 李弋, 彭鑫, 赵文耘. 正反例归纳合成SQL查询程序. 软件学报, 2023, 34(9): 4132–4152. http://www.jos.org.cn/1000-9825/6646.htm
    Zhang J, Li Y, Peng X, Zhao WY. Inductive SQL synthesis with positive and negative tuples. Ruan Jian Xue Bao/Journal of Software, 2023, 34(9): 4132–4152 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6646.htm
    [10] Feser JK, Chaudhuri S, Dillig I. Synthesizing data structure transformations from input-output examples. ACM SIGPLAN Notices, 2015, 50(6): 229–239.
    [11] Kang CG, Oh H. Modular component-based quantum circuit synthesis. Proc. of the ACM on Programming Languages, 2023, 7(OOPSLA1): 87.
    [12] 张鑫. 量子编程与线路优化的研究与实现 [硕士学位论文]. 重庆: 重庆大学, 2019. [doi: 10.27670/d.cnki.gcqdu.2019.002616]
    Zhang X. Research and implementation of quantum programming and circuit optimization [MS. Thesis]. Chongqing: Chongqing University, 2019 (in Chinese with English abstract). [doi: 10.27670/d.cnki.gcqdu.2019.002616]
    [13] 谢磊, 翟季冬. 量子计算系统软件研究综述. 软件学报, 2024, 35(1): 1–18. http://www.jos.org.cn/1000-9825/6908.htm
    Xie L, Zhai JD. Survey on quantum computing system software. Ruan Jian Xue Bao/Journal of Software, 2024, 35(1): 1–18 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6908.htm
    [14] Jang E, Choi S, Ro WW. Quixote: Improving fidelity of quantum program by independent execution of controlled gates. In: Proc. of the 60th ACM/IEEE Design Automation Conf. San Francisco: IEEE, 2023. 1–6. [doi: 10.1109/DAC56929.2023.10247757]
    [15] Aleksandrowicz G, Alexander T, Barkoutsos P, et al. Qiskit: An open-source framework for quantum computing. 2019. https://zenodo.org/records/2562111
    [16] Omole V, Tyagi A, Carey C, Hanus A, Hancock A, Garcia A, Shedenhelm J, Cowen J. Cirq: A Python framework for creating, editing, and invoking quantum circuits. 2020. https://sdmay20-08.sd.ece.iastate.edu/docs/Design-Document-v2.pdf
    [17] Iten R, Colbeck R, Kukuljan I, Home J, Christandl M. Quantum circuits for isometries. Physical Review A, 2016, 93(3): 032318.
    [18] Shende VV, Bullock SS, Markov IL. Synthesis of quantum logic circuits. In: Proc. of the 2005 Asia and South Pacific Design Automation Conf. Shanghai: IEEE, 2005. 272–275. [doi: 10.1109/ASPDAC.2005.1466172]
    [19] Tan SW, Lang CL, Xiang L, Wang SD, Jia XH, Tan ZQ. QuCT: A framework for analyzing quantum circuit by extracting contextual and topological features. In: Proc. of the 56th IEEE/ACM Int’l Symp. on Microarchitecture. Toronto: IEEE, 2023. 494–508.
    [20] Paradis A, Dekoninck J, Bichsel B, Vechev M. Synthetiq: Fast and versatile quantum circuit synthesis. Proc. of the ACM on Programming Languages, 2024, 8(OOPSLA1): 96.
    [21] Davis MG, Smith E, Tudor A, Sen K, Siddiqi I, Iancu C. Towards optimal topology aware quantum circuit synthesis. In: Proc. of the 2020 IEEE Int’l Conf. on Quantum Computing and Engineering. Denver: IEEE, 2020. 223–234. [doi: 10.1109/QCE49297.2020.00036]
    [22] Sutton BD. Computing the complete CS decomposition. Numerical Algorithms, 2009, 50(1): 33–65.
    [23] Dawson CM, Nielsen MA. The Solovay-Kitaev algorithm. Quantum Information & Computation, 2006, 6(1): 81–95.
    [24] Jiang M. Channel-state duality. Physical Review A, 2013, 87(2): 022310.
    [25] Schutski R, Lykov D, Oseledets I. Adaptive algorithm for quantum circuit simulation. Physical Review A, 2020, 101(4): 042335.
    [26] Bocharov A, Roetteler M, Svore KM. Efficient synthesis of universal repeat-until-success quantum circuits. Physical Review Letters, 2015, 114(8): 080502.
    [27] Soeken M, Miller DM, Drechsler R. Quantum circuits employing roots of the pauli matrices. Physical Review A, 2013, 88(4): 042322.
    [28] Malvetti E, Iten R, Colbeck R. Quantum circuits for sparse isometries. Quantum, 2021, 5: 412.
    [29] Peham T, Burgholzer L, Wille R. Equivalence checking paradigms in quantum circuit design: A case study. In: Proc. of the 59th ACM/IEEE Design Automation Conf. San Francisco: ACM, 2022. 517–522. [doi: 10.1145/3489517.3530480]
    [30] Li ZK, Peng JJ, Mei YX, Lin SN, Wu Y, Padon O, Jia ZH. Quarl: A learning-based quantum circuit optimizer. Proc. of the ACM on Programming Languages, 2024, 8(OOPSLA1): 114.
    [31] 窦星磊, 刘磊, 陈岳涛. 面向超导量子计算机的程序映射技术研究. 计算机研究与发展, 2021, 58(9): 1856–1874.
    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).
    [32] Das P, Tannu S, Dangwal S, Qureshi M. ADAPT: Mitigating idling errors in qubits via adaptive dynamical decoupling. In: Proc. of the 54th Annual IEEE/ACM Int’l Symp. on Microarchitecture. ACM, 2021. 950–962. [doi: 10.1145/3466752.3480059]
    [33] Xie L, Zhai JD, Zhang ZX, Allcock J, Zhang SY, Zheng YC. Suppressing ZZ crosstalk of quantum computers through pulse and scheduling co-optimization. In: Proc. of the 27th ACM Int’l Conf. on Architectural Support for Programming Languages and Operating Systems. Lausanne: ACM, 2022. 499–513. [doi: 10.1145/3503222.3507761]
    [34] Bichsel B, Baader M, Gehr T, Vechev M. Silq: A high-level quantum language with safe uncomputation and intuitive semantics. In: Proc. of the 41st ACM SIGPLAN Conf. on Programming Language Design and Implementation. London: ACM, 2020. 286–300. [doi: 10.1145/3385412.3386007]
    [35] Xu A, Molavi A, Pick L, Tannu S, Albarghouthi A. Synthesizing quantum-circuit optimizers. Proc. of the ACM on Programming Languages, 2023, 7(PLDI): 140.
    [36] Zhou L, Yu NK, Ying MS. An applied quantum Hoare logic. In: Proc. of the 40th ACM SIGPLAN Conf. on Programming Language Design and Implementation. Phoenix: ACM, 2019. 1149–1162. [doi: 10.1145/3314221.3314584]
    Related
    Cited by
Get Citation

谭思危,卢丽强,郎聪亮,陈明帅,尹建伟. Fast-USYN: 从酉矩阵到高质量量子电路的快速合成.软件学报,2025,36(8):3431-3443

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 21,2024
  • Revised:October 14,2024
  • Online: December 10,2024
You are the first2049855Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063