Improving Qiskit strategies for circuit synthesis using the Reed-Muller spectrum

• Raphael B. F. Lima UFF
• Luis Antonio B. Kowada UFF
• Fábio G. dos Santos UFF

DOI: https://doi.org/10.5753/semish.2025.9256

Resumo

Reversible computing and quantum computing have gained increasing attention due to their potential to overcome some of the fundamental limitations of classical computing, particularly regarding energy efficiency and computational power. In this paper, we compare the synthesis process using the well-known Qiskit framework developed by IBM and an approach based on Reed-Muller spectra. We show that some approaches are efficient for small values and others are better for the general use case. The synthesis results are presented using four strategies: unitary matrices, linear function synthesis, permutation synthesis, and Reed-Muller spectra. Our analysis shows that, on average, our proposal surpasses the Qiskit synthesis algorithms when considering the gate count metric. Additionally, a post-synthesis evaluation is performed using our proposed method, which employs a Reed-Muller–based representation to assess its effectiveness.

Referências

Abbe, E., Shpilka, A., and Wigderson, A. (2015). Reed-muller codes for random erasures and errors. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, pages 297–306.

Abbe, E., Shpilka, A., and Ye, M. (2020). Reed–muller codes: Theory and algorithms. IEEE Transactions on Information Theory, 67(6):3251–3277.

Bandyopadhyay, C. and Rahaman, H. (2014). Synthesis of esop-based reversible logic using positive polarity reed-muller form. In Emerging Trends in Computing and Communication: ETCC 2014, March 22-23, 2014, pages 363–376. Springer.

Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., and Weinfurter, H. (1995). Elementary gates for quantum computation. Physical review A, 52(5):3457.

Benioff, P. (1980). The computer as a physical system: A microscopic quantum mechanical hamiltonian model of computers as represented by turing machines. Journal of statistical physics, 22:563–591.

Benioff, P. (1982a). Quantum mechanical hamiltonian models of turing machines. Journal of Statistical Physics, 29:515–546.

Benioff, P. (1982b). Quantum mechanical hamiltonian models of turing machines. Journal of Statistical Physics, 29:515–546.

Bernardino, R. and Kowada, L. (2025). Reversible circuit optimization using reed-muller spectrum and rules decomposition. In 2025 IEEE 16th Latin America Symposium on Circuits and Systems (LASCAS).

Dalcumune, E., Kowada, L. A. B., Ribeiro, A. C., Figueiredo, C. M. H., and Marquezino, F. L. (2021). A reversible circuit synthesis algorithm with progressive increase of controls in generalized toffoli gates. JUCS - Journal of Universal Computer Science, 27(6):544–563.

Falkowski, B. J. and Chang, C.-H. (1995). An exact minimizer of fixed polarity reedmuller expansions. International journal of electronics, 79(4):389–409.

Fredkin, E. and Toffoli, T. (1982). Conservative logic. International Journal of Theoretical Physics, 21(3):219–253.

Gottesman, D. (1998). The heisenberg representation of quantum computers. arXiv preprint quant-ph/9807006.

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219.

IBM (2017). Qiskit. Available at [link].

Kaufman, T., Lovett, S., and Porat, E. (2012). Weight distribution and list-decoding size of reed–muller codes. IEEE transactions on information theory, 58(5):2689–2696.

Knill, E. and Laflamme, R. (1997). Theory of quantum error-correcting codes. Physical Review A, 55(2):900.

Kutin, S. A., Moulton, D. P., and Smithline, L. M. (2007). Computation at a distance. arXiv preprint quant-ph/0701194.

Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3):183–191.

Maslov, D. and Dueck, G. W. (2003). Garbage in reversible design of multiple output functions. In 6th International Symposium on Representations and Methodology of Future Computing Technologies, pages 162–170.

Maslov, D., Dueck, G. W., and Miller, D. M. (2007). Techniques for the synthesis of reversible toffoli networks. ACM Transactions on Design Automation of Electronic Systems (TODAES), 12(4):42–es.

Nielsen, M. A. and Chuang, I. L. (2000). Quantum Computation and Quantum Information. Cambridge University Press, New York, NY, USA.

Patel, K. N., Markov, I. L., and Hayes, J. P. (2008). Optimal synthesis of linear reversible circuits. Quantum Inf. Comput., 8(3):282–294.

Porwik, P. (2002). Efficient calculation of the reed-muller form by means of the walsh transform. Int. J. Appl. Math. Comput. Sci, 12(4):571–579.

Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332.

Toffoli, T. (1980). Reversible computing. In de Bakker, J. and van Leeuwen, J., editors, Automata, Languages and Programming, page 632, New York. Springer. MIT Technical Memo No. MIT/LCS/TM-151, 1980 (unpublished).

Zakablukov, D. V. (2016). Application of permutation group theory in reversible logic synthesis. In Reversible Computation: 8th International Conference, RC 2016, Bologna, Italy, July 7-8, 2016, Proceedings 8, pages 223–238. Springer.