# Reversible Circuit Synthesis Time Reduction Based on Subtree-Circuit Mapping
## 3 Preliminaries and Basic Definitions  
The basic logical gates are not reversible by their nature (an exception is the case of a NOT gate). For example, considering AND and OR gates, it is impossible to determine the two input bits from the output one (in the case of AND, the output 0 comes from the inputs 00 or 10 or 01, while for OR, the output 1 comes from the input 11 or 10 and 01). However, the opposite is true with reversible gates: it is easy to determine the input bits from the output and vice versa because the mapping between the input and output vectors is always one-to-one. A reversible gate can be represented by a reversible function with \(n\)-bit data for both input and output, where \(n\)-bit data are a sequence of bits \(x_{1},x_{2},\ldots,x_{n}\) of length \(n\) in which the mapping is bijective function on the set \(\left(0,1\right)^{n}\) of \(n\)-bit data on itself [16]. The development of reversible gates and circuits started after [PERSON] proposed reversible logic gates in 1977, where a unique input/output association was preserved [17]. Several reversible gates have been proposed, such as NOT, Feynman, Toffoli, Fredkin and Swap gates. Of the previous circuits, the Toffoli gate became the most important of the reversible gates due to its simplicity of structure. Most of the related works depend on the Toffoli gate in their attempts to optimize reversible circuit synthesis. In this work--as before--we used this gate in our proposal and experiments. The Toffoli gate is a gate with a size of \(n\times n\), where the target line flips when all control lines are set to 1; otherwise, the target line signal remains the same. Figure 1 shows a block diagram and schematic representation of a \(3\times 3\) Toffoli gate [18] where \(A\) and \(B\) represent control lines and \(C\) represents the target line. Table 1 represents the truth table that reflects the implementation of theToffoli gate, where values of \(A\), \(B\) (control lines) and \(C\) (target line) are inputs while \(P\), \(Q\), and \(R\) are the outputs. The following provides a brief description of the basic terminology behind reversible circuit synthesis in addition to a formulation for its cost metrics [19]. A reversible \(n*n\) function \(f:B^{n}\to B^{n}\) is used such that \(B\in\{0,1\}\) is a bijective mapping of every \(n\)-bit input vector into an \(n\)-bit output vector and any input pattern maps to a unique output pattern. In other words, the output of a reversible function is a permutation of the set of inputs. Let \(g\) be a logic gate that realizes a Boolean function \(f\) with \(n\) inputs and \(k\) outputs. If the function \(f\) is reversible, such that \(n=k\) with bijective mapping between input and output vectors, the logic gate \(g\) is said to be reversible. Notice that additional inputs and/or outputs might be required to be added to make a function \(f\) reversible. A reversible circuit \(G=(g_{0},g_{1},\cdot,g_{d-1})\) is a cascade of reversible gates that realize some reversible function. An irreversible function can be embedded in a reversible circuit by adding constant inputs and garbage outputs, as shown in Figure 2, which represents a reversible full adder circuit to find the summation of three input bits \((x,y,C_{\text{in}})\) with the sum output \(sum\) and carry out \(C_{\text{out}}\). Notice that a constant input of 0 has been added with two garbage (\"don't care\") outputs. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multicolumn{3}{c}{**Input**} & \multicolumn{3}{c}{**Output**} \\ \hline A & B & C & P & Q & R \\ \hline
1 & 1 & 1 & 1 & 1 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Toffoli gate truth table. Figure 1: Toffoli gate: block and schematic representations where \(\oplus\) represents the target line and \(\bullet\) represents the control lines. Figure 2: A reversible full added circuit with one constant input and two garbage outputs. Synthesizing a reversible circuit forms the first step in the design of quantum circuit since the latter is inherently reversible.