# Reversible Circuit Synthesis Time Reduction Based on Subtree-Circuit Mapping
## 2 Related Work  
The creation of algorithms that are capable of producing smaller circuits has been the dominant goal of the literature in this field in recent years. We can easily find papers related to the optimization of the process of reversible circuit synthesis. Synthesis time reduction appears as a secondary goal. Some works have used heuristic algorithms to try to find the best possible solution. For example, the work presented in [8] introduces a synthesis algorithm that uses Covering Set Partitions (CSP),with no garbage bits. Their work is based on mathematical properties of binary numbers, partially ordered sets and covering graph theory to construct input vectors that are guaranteed to converge. The CSP algorithm can be used to synthesize functions of a large number of variables (up to 30 bits) within a reasonable amount of time. As a continuation of [8], the authors of [9] compared meta-heuristic algorithms on top of CSP algorithms. Restricted truth tables orders were explored by meta-heuristic algorithms. Genetic and Tabu searches were compared in the work, which also showed that both approaches outperform the typical random search. Quantum cost was used to compare algorithms, which was represented by the number of logical gates. The authors of the work published in [3] tried to minimize the search space size of the solutions representing feasible reversible circuits by selectively generating permutations for a binary function representing some reversible circuit. Moreover, an Adaptive Genetic Algorithm (AGA) for synthesizing reversible circuits was proposed. The proposed algorithm is fed with a reversible specification of a given circuit and then produces a cascade of Toffoli gates. Several benchmark circuits were tested, and the experimental results showed that the proposed evolutionary algorithm enables optimal or near-optimal solutions with lesser gate counts. Many recent works have used BDD to synthesize reversible circuits. BDD is a compact data structure that replaces truth tables in the process of building a reversible circuit. Converting binary functions to BDDs before building circuits opens the possibility of using new optimization techniques. The work presented in [10] is related to the description and evaluation of how optimization techniques for decision diagrams can be exploited for the BDD-based synthesis of reversible and quantum logic. The authors of the work considered shared nodes, complement edges and ordering strategies and presented the gate cascades needed to support these methods. The effect of these techniques on the circuit sizes has been evaluated. The authors found that the BDD optimizations also led to improvements in the circuit sizes. The effect of intermediate representations on different graph-based methods, such as BDD, inverter graphs and majority inverter graphs, in terms of their usability in making efficient circuit realizations is presented in the work of [11]. Three representations for huge binary functions were compared in this work, and the authors found that BDD is better for small functions due to the compact circuits it generates compared with the other two representations, which showed better improvements in cost compared with BDD with a cost reduction reaching 39% on average. However, effective BDD reordering is not considered in this work. In the work presented in [12], the impact of different BDD reordering algorithms on the quantum cost of the synthesized reversible circuits was evaluated. This includes greedy, dynamic programming and meta-heuristic based reordering algorithms (Genetic and Simulated Annealing). The experimental results showed that meta-heuristic algorithms present a great deal of evidence for reducing the cost of a synthesized circuit, due to their effective exploration/exploitation in finding the near-optimal BDD size, which was found to be small-sized circuits. The work conducted in [6] is related to the huge BDD sizes generated from complicated Boolean functions (more than 100 variables).