Research progress in reversible circuit synthesis and optimization

doi:10.3969/j.issn.1007-5461.2024.04.001

Abstract

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

CLC Number:

TP385

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.

References

[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.