Post-Synthesis Optimization of Reversible Circuits

• Edinelço Dalcumune UFVJM / UFRJ http://orcid.org/0000-0002-3999-6664
• Luis A. B. Kowada UFF https://orcid.org/0000-0002-7975-0060
• Celina M. H. de Figueiredo UFRJ https://orcid.org/0000-0002-6393-0876
• Franklin de L. Marquezino UFRJ https://orcid.org/0000-0001-9712-1930

DOI: https://doi.org/10.5753/etc.2021.16385

Resumo

One of the main motivations for reversible computing is that quantum computing has as one of its foundations the reversibility of all gates, that is, quantum computing circuit models are reversible. An important problem in reversible computing that has been intensively studied for the last decades is the synthesis of reversible circuits. The extended abstract considers optimization rules aiming to a new algorithm for post-synthesis optimization of reversible circuits composed of generalized Toffoli gates.

Palavras-chave: design of algorithms, reversible computing, circuit synthesis, post-synthesis optimization

Referências

A. A. A. de Almeida, G. W. Dueck, and A. C. R. da Silva. Reversible circuit optimization based on tabu search. In IEEE Int. Symp. on Mult-Valued Log., pages 103–108, 2018.

X. Cheng, Z. Guan, W. Wang, and L. Zhu. A simplification algorithm for reversible logic network of positive/negative control gates. In Int. Conf. on Fuzzy Syst. and Knowledge Discovery, pages 2442–2446, May 2012.

K. Datta, G. Rathi, R. Wille, I. Sengupta, H. Rahaman, and R. Drechsler. Exploiting negative control lines in the optimization of reversible circuits. In Gerhard W. Dueck and D. Michael Miller, editors, Reversible Computation, pages 209–220. Springer, 2013.

K. Datta, I. Sengupta, and H. Rahaman. A post-synthesis optimization technique for reversible circuits exploiting negative control lines. IEEE Trans. Comput., 64(4):1208–1214, 2015.

L. A. B. Kowada, R. Portugal, and C. M. H. de Figueiredo. Reversible Karatsuba’s algorithm. J. Univers. Comput. Sci., 12(5):499–511, jun 2006.

D. Maslov and G. W. Dueck. Level compaction in quantum circuits. In IEEE Int. Conf. on Evol. Comput., pages 2405–2409, 2006.

D. Maslov, G. W. Dueck, and D. M. Miller. Toffoli network synthesis with templates. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 24(6):807–817, 2005.

D. M. Miller, D. Maslov, and G. W. Dueck. A transformation based algorithm for reversible logic synthesis. In Ann. Design Aut. Conf., pages 318–323. ACM, 2003.

M. M. Rahman, M. Soeken, and G. W. Dueck. Dynamic template matching with mixed-polarity Toffoli gates. In IEEE Int. Symp. on Mult-Valued Log., pages 72–77, 2015.

Md Z. Rahman and J. E. Rice. Templates for positive and negative control Toffoli networks. In Shigeru Yamashita and Shinichi Minato, editors, Reversible Computation, pages 125–136. Springer, 2014.

M. Saeedi and I. L. Markov. Synthesis and optimization of reversible circuits - a survey. ACM Comput. Surv., 45(2):21:1–21:34, mar 2013.

M. Soeken and M. K. Thomsen. White dots do matter: Rewriting reversible logic circuits. In Gerhard W. Dueck and D. Michael Miller, editors, Reversible Computation, pages 196–208. Springer, 2013.

M. Soeken, R. Wille, G. W. Dueck, and R. Drechsler. Window optimization of reversible and quantum circuits. In IEEE Symp. on Design and Diag. of Elect. Circuits and Syst., pages 341–345, 2010.

R. Wille, M. Soeken, C. Otterstedt, and R. Drechsler. Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In Asia and South Pacific Design Aut. Conf., pages 145–150, 2013.

R. Wille, M. Soeken, N. Przigoda, and R. Drechsler. Exact synthesis of Toffoli gate circuits with negative control lines. In IEEE Int. Symp. on Mult-Valued Log., pages 69–74, May 2012.