# Reversible Circuit Synthesis Time Reduction Based on Subtree-Circuit Mapping
1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (A.A.); [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; [EMAIL_ADDRESS] (B.A.) 1 Faculty of Engineering and Information Technology, Information and Computer Science Department,  
An-Najah National University, PO Box 7, Nablus, Palestine; ahmedawad@najah. be built using reversible gates. Reversible logic computations can be easily applied to the field of quantum computing due to its natural reversibility in computations [2]. In this way, low power design requirements for VLSI chips are achieved [34]. Restrictions on the structure of the reversible circuits cause the process of its synthesis to differ significantly from synthesis using traditional irreversible gates. Mainly, fan out and feedback are not allowed; in addition, the input and output bits must be the same, and additional input and output lines might therefore be required to achieve reversibility of computation. Additional inputs are known as constant lines, whereas additional outputs are known as garbage lines [5]. Reversible circuit synthesis has been proposed using numerous algorithms and techniques, each of which improves the synthesis process in terms of speed and optimization [5]. The Boolean function and its companion truth table were the basis for set of these works in the process of synthesizing reversible circuits. However, the Binary Decision Diagram (BDD) forms the basis for other works, in which a reduction in both the time of the synthesis process and the size of the generated reversible circuit is obtained. These works emphasize the BDD size reduction in order to minimize the reversible circuit size, and they were based on the direct mapping between BDD nodes and the corresponding reversible gates in the process of reversible circuit synthesis. Due to the sequential process of this kind of mapping, the one-to-one mapping process consumes some time [6]. In this work, which is an extension of the work presented in [7], we deeply investigate and work on all details related to the idea proposed in the mentioned work as well as implementing the subtree-based mapping of BDD nodes to reversible gates, minimizing the synthesis time of reversible circuits, instead of using nodal-based mapping. Our contributions can be summarized as follows: (1) Pre-prepared and well-studied combinations of all possible subtrees were created to form a look-up table that maps each possible subtree with its corresponding reversible gates. (2) Suitable hash keys were developed for all investigated possible subtrees in order to make the retrieval time of the corresponding reversible gates constant during the traversal time of a given BDD.