Chinese Journal of Quantum Electronics, Volume. 41, Issue 4, 565(2024)

Research progress in reversible circuit synthesis and optimization

WU Xian... FENG Shiguang* and LI Lyuzhou |Show fewer author(s)
Author Affiliations
  • School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510006, China
  • show less
    References(49)

    [1] Chong F T, Franklin D, Martonosi M. Programming languages and compiler design for realistic quantum hardware[J]. Nature, 549, 180-187(2017).

    [2] Beckman D, Chari A N, Devabhaktuni S et al. Efficient networks for quantum factoring[J]. Physical Review A, 54, 1034-1063(1996).

    [3] Markov I L, Saeedi M. Constant-optimized quantum circuits for modular multiplication and exponentiation[J]. Quantum Information & Computation, 12, 361-394(2012).

    [4] Niemann P, Basu S, Chakrabarti A et al. Synthesis of quantum circuits for dedicated physical machine descriptions[C], 248-264(2015).

    [5] Nielsen M A, Chuang I L[M]. Quantum Computation and Quantum Information(2010).

    [6] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring[C], 124-134(2002).

    [7] Abdessaied N, Drechsler R[M]. Reversible and Quantum Circuits(2016).

    [8] Zulehner A, Wille R[M]. Introducing Design Automation for Quantum Computing(2020).

    [9] Patel K N, Markov I L, Hayes J P. Optimal synthesis of linear reversible circuits[J]. Quantum Information & Computation, 8, 282-294(2008).

    [10] 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, 22, 710-722(2003).

    [11] 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, 2, 11(2021).

    [13] Zakablukov D V. On asymptotic gate complexity and depth of reversible circuits without additional memory[J]. Journal of Computer and System Sciences, 84, 132-143(2017).

    [14] Jiang J Q, Sun X M, Teng S H et al. Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis[C], 213-229(2020).

    [15] McColl W F, Patterson M S. The depth of all Boolean functions[J]. SIAM Journal on Computing, 6, 373-380(1977).

    [16] Aaronson S, Gottesman D. Improved simulation of stabilizer circuits[J]. Physical Review A, 70, 052328(2004).

    [17] Dawson C M, Nielsen M A. The Solovay-Kitaev algorithm[J]. Quantum Information & Computation, 6, 81-95(2006).

    [18] Desoete B, De Vos A. A reversible carry-look-ahead adder using control gates[J]. Integration, 33, 89-104(2002).

    [19] Barenco A, Bennett C H, Cleve R et al. Elementary gates for quantum computation[J]. Physical Review A, 52, 3457-3467(1995).

    [21] 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, 2, 3102422(2021).

    [22] Cole R, Ost K, Schirra S. Edge-coloring bipartite multigraphs in O(E logD) time[J]. Combinatorica, 21, 5-12(2001).

    [23] Botea A, Kishimoto A, Marinescu R. On the complexity of quantum circuit compilation[J]. Proceedings of the International Symposium on Combinatorial Search, 9, 138-142(2018).

    [24] Moore C, Nilsson M. Parallel quantum computation and quantum codes[J]. SIAM Journal on Computing, 31, 799-815(2001).

    [25] Meuli G, Soeken M, De Micheli G. SAT-based {CNOT, T} quantum circuit synthesis[C], 175-188(2018).

    [26] Maslov D, Young C, Miller D M et al. Quantum circuit simplification using templates[C], 1208-1213(2005).

    [27] Kreppel F, Melzer C, Olvera Millán D et al. Quantum circuit compiler for a shuttling-based trapped-ion quantum computer[J]. Quantum, 7, 1176(2023).

    [28] 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, 33, 1476-1489(2014).

    [29] 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, 6, 13(2010).

    [30] Abdessaied N, Soeken M, Thomsen M K et al. Upper bounds for reversible circuits based on Young subgroups[J]. Information Processing Letters, 114, 282-286(2014).

    [31] Calderbank A R, Rains E M, Shor P M et al. Quantum error correction via codes over GF(4)[J]. IEEE Transactions on Information Theory, 44, 1369-1387(1998).

    [32] Da Silva A J, Park D K. Linear-depth quantum circuits for multiqubit controlled gates[J]. Physical Review A, 106, 042602(2022).

    [33] Naderpour F, Vafaei A. Reversible multipliers: Decreasing the depth of the circuit[C], 306-310(2008).

    [34] Abdessaied N, Wille R, Soeken M et al. Reducing the depth of quantum circuits using additional circuit lines[C], 221-233(2013).

    [35] Arabzadeh M, Saheb Zamani M, Sedighi M et al. Depth-optimized reversible circuit synthesis[J]. Quantum information processing, 12, 1677-1699(2013).

    [36] Wille R, Drechsler R. BDD-based synthesis of reversible logic for large functions[C], 270-275(2009).

    [37] Bravyi S, Kitaev A. Universal quantum computation with ideal Clifford gates and noisy ancillas[J]. Physical Review A, 71, 022316(2005).

    [38] Amy M, Mosca M. T-count optimization and Reed⁃Muller codes[J]. IEEE Transactions on Information Theory, 65, 4771-4784(2019).

    [39] Shi Y N, Leung N, Gokhale P et al. Optimized compilation of aggregated instructions for realistic quantum computers[C], 1031-1044(2019).

    [40] Maslov D, Zindorf B. Depth optimization of CZ, CNOT, and Clifford circuits[J]. IEEE Transactions on Quantum Engineering, 3, 2500408(2022).

    [41] Li G S, Ding Y F, Xie Y. Tackling the qubit mapping problem for NISQ-era quantum devices[C], 1001-1014(2019).

    [42] Herr D, Nori F, Devitt S J. Optimization of lattice surgery is NP-hard[J]. NPJ Quantum Information, 3, 35(2017).

    [44] Zhang C, Hayes A B, Qiu L F et al. Time-optimal qubit mapping[C], 360-374(2021).

    [45] Kusyk J, Saeed S M, Uyar M U. Survey on quantum circuit compilation for noisy intermediate-scale quantum computers: Artificial intelligence to heuristics[J]. IEEE Transactions on Quantum Engineering, 2, 2501616(2021).

    [46] Nash B, Gheorghiu V, Mosca M. Quantum circuit optimizations for NISQ architectures[J]. Quantum Science and Technology, 5, 025010(2020).

    [47] Kissinger A, van de Griend A M. CNOT circuit extraction for topologically-constrained quantum memories[J]. Quantum Information and Computation, 20, 581-596(2020).

    [48] Bluvstein D, Levine H, Semeghini G et al. A quantum processor based on coherent transport of entangled atom arrays[J]. Nature, 604, 451-456(2022).

    [49] Patel T, Silver D, Tiwari D. Geyser: A compilation framework for quantum computing with neutral atoms[C], 383-395(2022).

    Tools

    Get Citation

    Copy Citation Text

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

    Download Citation

    EndNote(RIS)BibTexPlain Text
    Save article for my favorites
    Paper Information

    Category:

    Received: Mar. 8, 2024

    Accepted: --

    Published Online: Jan. 8, 2025

    The Author Email: FENG Shiguang (fengshg3@mail.sysu.edu.cn)

    DOI:10.3969/j.issn.1007-5461.2024.04.001

    Topics