Complete synthesis of identity templates for quantum and reversible logic MCT circuits using SAT-solvers and proposal of suboptimality witness notion

• Autorzy: Jagielski Adam

Identyfikatory

DOI

10.24425/ijet.2024.149602

• Języki publikacji: EN

Abstrakty

EN

In this study, we introduce a procedural generation technique for Identity Templates applicable to quantum and reversible logic circuits. These templates are recognized for their significant role in enhancing the efficiency of quantum and reversible logic optimization. Our approach enables the exhaustive synthesis of all potential templates up to a specified size. Leveraging the power of SAT-solver technology, we have verified the comprehensiveness of our template collections by confirming the full exploration of the search space. Additionally, we propose an innovative concept of Suboptimality Witnesses, which we anticipate will be instrumental in streamlining the search process in formal methods, akin to SAT-solvers, for the synthesis of reversible logic circuits.

Słowa kluczowe

EN

quantum computing; circuit synthesis; cryptography; satisfiability problem; reversible logic

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 3
• Strony: 727--732
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Jagielski Adam

• Military University of Technology in Warsaw

• https://orcid.org/https%3A//orcid.org/0000-0002-1343-7522

Bibliografia

• [1] R. Landauer, “Irreversibility and heat generation in the computing process,” vol. 5, no. 3, pp. 183-191, 1961. [Online]. Available: http://ieeexplore.ieee.org/document/5392446/
• [2] K. A. McKay, L. Bassham, M. S. Turan, and N. Mouha, “Report on lightweight cryptography,” p. NIST IR 8114, 2017. [Online]. Available: https://nvlpubs.nist.gov/nistpubs/ir/2017/NIST.IR.8114.pdf
• [3] M. S. Turan, “Status report on the final round of the NIST lightweight cryptography standardization process,” p. NIST IR 8454, 2023. [Online]. Available: https://nvlpubs.nist.gov/nistpubs/ir/2023/NIST.IR.8454.pdf
• [4] G. W. Dueck, D. M. Miller, and D. Maslov, “Templates for toffoli network synthesis,” 2003.
• [5] D. Miller, D. Maslov, and G. Dueck, “A transformation based algorithm for reversible logic synthesis,” 2003, pp. 318-323.
• [6] D. Maslov, G. Dueck, and D. Miller, “Simplification of toffoli networks via templates,” 2003, pp. 53-58.
• [7] D. Maslov, C. Young, D. Miller, and G. Dueck, “Quantum circuit simplification using templates,” in Design, Automation and Test in Europe. IEEE, 2005, pp. 1208-1213. [Online]. Available: http://ieeexplore.ieee.org/document/1395758/
• [8] D. Maslov, G. Dueck, and D. Miller, “Toffoli network synthesis with templates,” vol. 24, pp. 807-817, 2005.
• [9] D. Maslov, D. M. Miller, and G. W. Dueck, “Techniques for the synthesis of reversible toffoli networks,” 2006. [Online]. Available: http://arxiv.org/abs/quant-ph/0607166
• [10] R. Wille and R. Drechsler, Towards a Design Flow for Reversible Logic. Springer Netherlands, 2010. [Online]. Available: http://link.springer.com/10.1007/978-90-481-9579-4
• [11] A. Jagielski, “Optimal SAT solver synthesis of quantum circuits representing cryptographic nonlinear functions,” vol. 69, no. 3, pp. 261-267, 2023. [Online]. Available: https://journals.pan.pl/dlibra/publication/144359/edition/127355/content

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).