可逆电路综合与优化的若干研究进展

doi:10.3969/j.issn.1007-5461.2024.04.001

摘要/Abstract

摘要： 量子计算是一种新型计算模式, 遵循量子力学规律对信息进行处理, 其应用涵盖密码学、组合优化和量子模拟等多个领域。量子计算强大算力的发挥有赖于量子算法, 而量子算法的运行首先需要编译为量子电路。可逆电路是一类重要的量子电路, 可逆电路的综合与优化是量子编译的主要研究内容之一。本文对可逆电路综合与优化中的一些重要工作进行总结, 首先介绍线性可逆电路的综合与优化, 对CNOT门数量与电路深度两个方面优化的结果进行讨论；然后介绍一般性可逆电路的规模和深度优化, 对当前算法所能达到的上下界情况进行了分析总结；最后对可逆电路综合与优化的相关延伸拓展进行探讨。

关键词: 量子计算, 量子电路, 电路综合与优化, 可逆电路, 线性可逆电路

Abstract: Quantum computing is a new type of computing mode that follows the laws of quantum mechanics to process information, its application covers multiple fields such as cryptography, combinatorial optimization, and quantum simulation. The power of quantum computing relies on quantum algorithms, while the quantum algorithms must first be compiled into quantum circuits to execute. Reversible circuit is an important type of quantum circuits, and the synthesis and optimization of reversible circuits is one of the main research topics in quantum compilation. Some important progress in the synthesis and optimization of reversible circuits are summarized. Firstly, the synthesis and optimization of linear reversible circuits is introduced, and the optimization results in terms of the number of controlled-NOT (CNOT) gates and the depth of circuits are discussed. Then, the size and depth optimization of general reversible circuits are introduced, the upper and lower bounds that the current algorithms can achieve are analyzed. Finally, the extensions of reversible circuit synthesis and optimization are discussed.

Key words: quantum computing, quantum circuit, circuit synthesis and optimization, reversible circuit; linear reversible circuit

中图分类号:

TP385

吴限, 冯世光, 李绿周. 可逆电路综合与优化的若干研究进展[J]. 量子电子学报, 2024, 41(4): 565-577.

WU Xian, FENG Shiguang, LI Lyuzhou. Research progress in reversible circuit synthesis and optimization[J]. Chinese Journal of Quantum Electronics, 2024, 41(4): 565-577.

参考文献

[1] Chong F T, Franklin D, Martonosi M. Programming languages and compiler design for realistic quantum hardware[J]. Nature, 2017, 549(7671): 180-187.
[2] Beckman D, Chari A N, Devabhaktuni S, et al. Efficient networks for quantum factoring[J]. Physical Review A, 1996, 54(2):1034.
[3] Markov I L, Saeedi M. Constant-optimized quantum circuits for modular multiplication and exponentiation[J].Quantum Information & Computation, 2012, 12(5-6):361-394.
[4] Niemann P, Basu S, Chakrabarti A, et al. Synthesis of quantum circuits for dedicated physical machine descriptions[C]. International Conference on Reversible Computation. Grenoble, France, 2015: 248-264.
[5] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition[M]. Cambridge: Cambridge University Press, 2010.
[6] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]. Proceedings 35th annual symposium on foundations of computer science. IEEE, 1994: 124-134.
[7] Abdessaied N, Drechsler R. Reversible and quantum circuits: Optimization and complexity analysis[M]. Cham: Springer International Publishing, 2016.
[8] Zulehner A, Wille R. Introducing design automation for quantum computing: volume 11[M]. Springer, 2020.
[9] Gambetta J M, Chow J M, Steffen M. Building logical qubits in a superconducting quantum computing system[J]. npj quantum information, 2017, 3(1):2.
[10] Abobeih M, Wang Y, Randall J, et al. Fault-tolerant operation of a logical qubit in a diamond quantum processor[J]. Nature, 2022, 606(7916): 884-889.
[11] Dawson C M, Nielsen M A. The Solovay-Kitaev algorithm[J]. Quantum Information and Computation, 2006, 6(1): 81-95.
[12] Zhang C, Hayes A B, Qiu L, et al. Time-optimal qubit mapping[C]. Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2021: 360-374.
[13] Desoete B, De Vos A. A reversible carry-look-ahead adder using control gates[J]. Integration, 2002, 33(1-2):89-104.
[14] Barenco A, Bennett C H, Cleve R, et al. Elementary gates for quantum computation[J]. Physical review A, 1995, 52(5):3457.
[15] Gao D, He X, Woodcock J, et al. Improving quantum circuits of Toffoli gates[OL]. https://meetings.ams.org/math/jmm2022/meetingapp.cgi/Paper/9514
[16] McColl W F, Patterson M S. The depth of all Boolean functions[J]. SIAM Journal on Computing, 1977, 6(2): 373-380.
[17] Gottesman D. Theory of fault-tolerant quantum computation[J]. Physical Review A, 1998, 57(1):127.
[18] De Brugière T G, Baboulin M, Valiron B, et al. Gaussian elimination versus greedy methods for the synthesis of linear reversible circuits[J]. ACM Transactions on Quantum Computing, 2021, 2(3):1-26.
[19] Patel K N, Markov I L, Hayes J P. Optimal synthesis of linear reversible circuits.[J]. Quantum Inf. Comput., 2008, 8(3):282-294.
[20] Jiang J, Sun X, Teng S H, et al. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis[C]. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2020: 213-229.
[21] Meuli G, Soeken M, Micheli G D. Sat-based {CNOT, T} quantum circuit synthesis[C]. International Conference on Reversible Computation. Leicester, UK. Springer, 2018: 175-188.
[22] Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for NISQ architectures[J]. Quantum Science and Technology, 2020, 5(2):025010.
[23] Kissinger A, MEIJER-VAN DE GRIEND A. Cnot circuit extraction for topologically-constrained quantum memories[J]. Quantum information & computation, 2020, 20(7-8): 581-596.
[24] Oore C, Nilsson M. Parallel quantum computation and quantum codes[J]. SIAM journal on computing, 2001, 31(3):799-815.
[25] De Brugière T G, Baboulin M, Valiron B, et al. Reducing the depth of linear reversible quantum circuits[J]. IEEE Transactions on Quantum Engineering, 2021, 2:1-22.
[26] Cole R, Ost K, Schirra S. Edge-coloring bipartite multigraphs in O (e logd) time[J]. Combinatorica, 2001, 21(1):5-12.
[27] Alon N. A simple algorithm for edge-coloring bipartite multigraphs[J]. Information Processing Letters, 2003, 85(6):301-302.
[28] Kutin S A, Moulton D P, Smithline L M. Computation at a distance[OL]. 2007, arXiv:quant-ph/0701194, https://arxiv.org/abs/quant-ph/0701194
[29] Maslov D, Young C, Miller D M, et al. Quantum circuit simplification using templates[C]. Design, Automation and Test in Europe. IEEE, 2005: 1208-1213.
[30] Bluvstein D, Levine H, Semeghini G, et al. A quantum processor based on coherent transport of entangled atom arrays[J]. Nature, 2022, 604 (7906):451-456.
[31] Kreppel F, Melzer C, Millán D O, et al. Quantum circuit compiler for a shuttling-based trapped-ion quantum computer[J]. Quantum, 2023, 7: 1176.
[32] Bandyopadhyay C, Wille R, Drechsler R, et al. Post synthesis-optimization of reversible circuit using template matching[C]. 2020 24th Inter- national Symposium on VLSI Design and Test (VDAT). IEEE, 2020: 1-4.
[33] Bravyi S, Kitaev A. Universal quantum computation with ideal Clifford gates and noisy ancillas[J]. Physical Review A, 2005, 71(2):022316.
[34] Amy M, Maslov D, Mosca M. Polynomial-time t-depth optimization of Clifford+ t circuits via matroid partitioning[J]. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 2014, 33(10):1476-1489.
[35] Datta K, Rathi G, Sengupta I, et al. Synthesis of reversible circuits using heuristic search method[C]. 2012 25th International Conference on VLSI Design. IEEE, 2012: 328-333.
[36] Shende V V, Prasad A K, Markov I L, et al. Synthesis of reversible logic circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6):710-722.
[37] Saeedi M, Zamani M S, Sedighi M, et al. Reversible circuit synthesis using a cycle-based approach[J]. ACM Journal on Emerging Technologies in Computing Systems (JETC), 2010, 6(4):1-26.
[38] Abdessaied N, Soeken M, Thomsen M K, et al. Upper bounds for reversible circuits based on Young subgroups[J]. Information Processing Letters, 2014, 114(6):282-286.
[39] Zakablukov D V. On asymptotic gate complexity and depth of reversible circuits without additional memory[J]. Journal of Computer and System Sciences, 2017, 84:132-143.
[40] Li L, Wu X. Asymptotically optimal synthesis of reversible circuits[OL]. 2023, arXiv:2302.06074, https://arxiv.org/abs/2302.06074
[41] Wille R, Drechsler R. BDD-based synthesis of reversible logic for large functions[C]. Proceedings of the 46th Annual Design Automation Conference. 2009: 270-275.
[42] Da Silva A J, Park D K. Linear-depth quantum circuits for multiqubit controlled gates[J]. Physical Review A, 2022, 106(4): 042602.
[43] Naderpour F, Vafaei A. Reversible multipliers: Decreasing the depth of the circuit[C]. 2008 International Conference on Electrical and Computer Engineering. IEEE, 2008: 306-310.
[44] Abdessaied N, Wille R, Soeken M, et al. Reducing the depth of quantum circuits using additional circuit lines[C]. Reversible Computation: 5th International Conference, RC 2013, Victoria, BC, Canada. Springer, 2013: 221-233.
[45] Arabzadeh M, Saheb Zamani M, Sedighi M, et al. Depth-optimized reversible circuit synthesis[J]. Quantum information processing, 2013, 12: 1677-1699.
[46] Patel T, Silver D, Tiwari D. Geyser: a compilation framework for quantum computing with neutral atoms[C]. Proceedings of the 49th Annual International Symposium on Computer Architecture. 2022: 383-395.
[47] Amy M, Azimzadeh P, Mosca M. On the controlled-not complexity of controlled-not–phase circuits[J]. Quantum Science and Technology, 2018, 4 (1):015002.
[48] Amy M, Mosca M. T-count optimization and Reed–Muller codes[J]. IEEE Transactions on Information Theory, 2019, 65(8):4771-4784.
[49] Shi Y, Leung N, Gokhale P, et al. Optimized compilation of aggregated instructions for realistic quantum computers[C]. Proceedings of the Twenty- Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 2019: 1031-1044.
[50] Maslov D, Zindorf B. Depth optimization of Cz, Cnot, and Clifford circuits[J]. IEEE Transactions on Quantum Engineering, 2022, 3:1-8.
[51] Li G, Ding Y, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C]. Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 2019: 1001-1014.
[52] Herr D, Nori F, Devitt S J. Optimization of lattice surgery is NP-hard[J]. Npj quantum information, 2017, 3(1):1-5.
[53] Childs A M, Schoute E, Unsal C M. Circuit transformations for quantum architectures[OL]. 2019, arXiv:1902.09102, https://arxiv.org/abs/1902.09102.
[54] Zhang C, Hayes A B, Qiu L, et al. Time-optimal qubit mapping[C]. Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2021: 360-374.
[55] Botea A, Kishimoto A, Marinescu R. On the complexity of quantum circuit compilation[C]. Proceedings of the International Symposium on Combinatorial Search: volume 9. 2018: 138-142 319.