Chinese Journal of Quantum Electronics, Volume. 41, Issue 4, 565(2024)
Research progress in reversible circuit synthesis and optimization
[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).
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
Category:
Received: Mar. 8, 2024
Accepted: --
Published Online: Jan. 8, 2025
The Author Email: FENG Shiguang (fengshg3@mail.sysu.edu.cn)