Complexity Analysis for Garbage-Free Reversible Computation of Boolean Functions with Variable Ancilla
DOI:
https://doi.org/10.31272/jeasd.2923Keywords:
Embedding, Garbage-free, MPMCT, Optimization, Reversible Circuit Synthesis, Single-Target Gate, Trade-offAbstract
Reversible computation is a fundamental concept in quantum circuits and low-power design. As the demand for powerful and energy-efficient computing grows, novel design methods for reversible circuits become critical for achieving high performance with low power consumption. Current reversible circuit synthesis methodologies fall into two classes, each minimizing a different parameter in circuit complexity, but often result in relatively high values in another parameter. Post-synthesis optimizations moderate complexity parameters, basically by trading off between them. However, these optimizations depend on specific gate patterns and may not always meet design constraints effectively. This paper proposes a novel recursive decomposition scheme for large Boolean functions using a single-target gate model in reversible circuit synthesis. The proposed scheme systematically and efficiently manages the trade-off between reversible circuit complexity measures, offering gradually varying parameters at each level in the recursion. The scalability of the proposed approach is presented as a comprehensive complexity analysis for the mathematical model. Rather than providing a globally optimal solution, this approach offers a range of solutions, allowing designers to choose the most suitable option based on specific design constraints.
References
M. P. Frank and K. Shukla, “Quantum foundations of classical reversible computing,” Entropy, vol. 23, no. 6, Art. no. 701, Jun. 2021. doi: https://doi.org/10.3390/e23060701.
A. K. Rajput, S. Chouhan, and M. Pattanaik, “Low power Boolean logic circuits using reversible logic gates,” in Proc. International Conference on Advances in Computing, Communication and Control (ICAC3), Mumbai, India, Dec. 2019, pp. 1–6. doi: https://doi.org/10.1109/ICAC347590.2019.9036799.
Q.-B. Luo, X.-Y. Li, G.-W. Yang, and Q. Li, “Quantum reversible circuits for GF(2^8 )multiplication based on composite field arithmetic operations,” Quantum Information Processing, vol. 22, Art. no. 58, Jan. 2023. doi: https://doi.org/10.1007/s11128-022-03799-w.
Z. Al-Wardi, R. Wille, and R. Drechsler, “Towards VHDL-based design of reversible circuits,” in Proceedings of Reversible Computation: 9th International Conference, Kolkata, India, 2017, pp. 102-108, doi: https://doi.org/10.1007/978-3-319-59936-6_8
F. -J. Chao and Y. -C. Chen, "Decomposition Attack on Structural Logic Locking of Reversible Circuits," in Proc. 43rd International Conference on Computer Design (ICCD), Richardson, TX, USA, 2025, pp. 646-653, doi: https://doi.org/10.1109/ICCD65941.2025.00098.
Z. Al-Wardi, “Reducing reversible circuit line count using Boolean techniques,” in Proc. 3rd International Scientific Conference of Engineering Sciences (ISCES), Diyala, Iraq, May 2023, pp. 42–47. doi: https://doi.org/10.1109/ISCES58193.2023.10311466.
R. Wille, M. Haghparast, S. Adarsh, and M. Tanmay, “Towards HDL-based synthesis of reversible circuits with no additional lines,” in Proc. 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Westminster, CO, USA, Nov. 2019, pp. 1–7. doi: https://doi.org/10.1109/ICCAD45719.2019.8942156.
M. Miao, J. Tang, G. Hu and H. Zhang, “BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, Singapore, Jan. 2026, vol. 40, no. 2, pp. 863–872. doi: https://doi.org/10.1609/aaai.v40i2.37054.
H. Riener, R. Ehlers, B. d. O. Schmitt, and G. De Micheli, “Exact synthesis of ESOP forms,” in Advanced Boolean Techniques: Selected Papers from the 13th International Workshop on Boolean Problems, Switzerland: Springer, 2020, ch. 7, pp. 177–194. doi: https://doi.org/10.1007/978-3-030-20323-8_8.
A. Bernasconi, A. Berti, V. Ciriani, G. M. Del Corso, and I. Fulginiti, “XOR-AND-XOR logic forms for autosymmetric functions and applications to quantum computing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 42, no. 6, pp. 1861–1872, Jun. 2023. doi: https://doi.org/10.1109/TCAD.2022.3213214.
K. Datta, I. Sengupta, H. Rahaman, and R. Drechsler, “An evolutionary approach to reversible logic synthesis using output permutation,” in Proc. 8th International Design and Test Symposium (IDT), Marrakesh, Morocco, Dec. 2013, pp. 1–6. doi: https://doi.org/10.1109/IDT.2013.6727117.
D. M. Miller, D. Maslov, and G. W. Dueck, “A transformation based algorithm for reversible logic synthesis,” in Proc. 40th Annual Design Automation Conference (DAC), Anaheim, CA, USA, Jun. 2003, pp. 318–323, doi: https://doi.org/10.1145/775832.775915.
K.S. Fong and M. Motani, “SyREC: A Symbolic-Regression-Based Ensemble Combiner,” in Proc. 36th International Conference on Tools with Artificial Intelligence (ICTAI), Herndon, VA, USA, Oct. 2024, pp.774-781, doi: https://doi.org/10.1109/ICTAI62512.2024.00114.
A. Hawash, A. Awad, and B. Abdalhaq, “Reversible circuit synthesis time reduction based on subtree-circuit mapping,” Applied Sciences, vol. 10, no. 12, Art. no. 4147, Jun. 2020. doi: https://doi.org/10.3390/app10124147.
D. Bu, J. Deng, P. Tang, and S. Yang, “Reversible circuit synthesis method using sub-graphs of shared functional decision diagrams,” The Computer Journal, vol. 66, no. 10, pp. 2574–2592, Oct. 2023. doi: https://doi.org/10.1093/comjnl/bxac107.
H. Lee, K. C. Jeong, D. Han and P. Kim, “An algorithm for reversible logic circuit synthesis based on tensor decomposition,” ACM Transactions on Quantum Computing, vol. 5, no. 3, pp. 1–28, 2024, doi: https://doi.org/10.1145/3673242.
L. Chhangte and A. Chakrabarty, “Mapping quantum circuits in IBM Q devices using progressive qubit assignment for global ordering,” New Generation Computing, vol. 40, no. 1, pp. 311–338, Apr. 2022. doi: https://doi.org/10.1007/s00354-022-00163-5.
R. Rietsche, C. Dremel, S. Bosch, L. Steinacker, M. Meckel, and J.-M. Leimeister, “Quantum computing,” Electronic Markets, vol. 32, no. 4, pp. 2525–2536, Dec. 2022. doi: https://doi.org/10.1007/s12525-022-00570-y.
R. Wille, M. Soeken, D. M. Miller, and R. Drechsler, “Trading off circuit lines and gate costs in the synthesis of reversible logic,” Integration, the VLSI Journal, vol. 47, no. 2, pp. 284–294, Mar. 2014. doi: https://doi.org/10.1016/j.vlsi.2013.08.002.
N. Abdessaied, R. Wille, M. Soeken, and R. Drechsler, “Reducing the depth of quantum circuits using additional circuit lines,” in Reversible Computation: 5th International Conference, RC 2013, Victoria, BC, Canada, July 4–5, 2013, Proceedings, A. De Vos and R. Wille, Eds. Berlin, Germany: Springer, 2013, pp. 221–233. doi: https://doi.org/10.1007/978-3-642-38986-3_18.
R. Wille, M. Soeken, and R. Drechsler, “Reducing the number of lines in reversible circuits,” in Proc. 47th Design Automation Conference (DAC), Anaheim, CA, USA, Jun. 2010, pp. 647–652. doi: https://doi.org/10.1145/1837274.1837439.
S. S. Samrin, R. Patil, S. Itagi, S. C. Chetti, and A. Tasneem, “Design of logic gates using reversible gates with reduced quantum cost,” Global Transitions Proceedings, vol. 3, no. 1, pp. 136–141, Jun. 2022. doi: https://doi.org/10.1016/j.gltp.2022.04.011.
M. M. Rahman, M. Soeken, and G. W. Dueck, “Dynamic template matching with mixed-polarity Toffoli gates,” in Proc. 2015 IEEE 45th International Symposium on Multiple-Valued Logic (ISMVL), Waterloo, ON, Canada, May 2015, pp. 72–77. doi: https://doi.org/10.1109/ISMVL.2015.44.
N. Abdessaied, M. Soeken, and R. Drechsler, “Technology mapping for single target gate based circuits using Boolean functional decomposition,” in Proceedings of Reversible Computation: 7th International Conference, 2015, Grenoble, France, 2015, pp. 219–232. doi: https://doi.org/10.1007/978-3-319-20860-2_14.
M. Soeken, L. Tague, G. W. Dueck, and R. Drechsler, “Ancilla-free synthesis of large reversible functions using binary decision diagrams,” Journal of Symbolic Computation, vol. 73, pp. 1–26, Mar. 2016, doi: https://doi.org/10.1016/j.jsc.2015.03.002.
Y. Ding, X.-C. Wu, A. Holmes, A. Wiseth, D. Franklin, M. Martonosi, and F. T. Chong, “SQUARE: Strategic quantum ancilla reuse for modular quantum programs via cost-effective uncomputation,” in Proc. 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA), Valencia, Spain, May 2020, pp. 570–583, doi: https://doi.org/10.1109/ISCA45697.2020.00054.
Downloads
Key Dates
Received
Revised
Accepted
Published Online First
Published
Issue
Section
License
Copyright (c) 2026 Zaid Al-Wardi (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
