This paper presents a new algorithm MP (multiple pass) to synthesize large reversible binary circuits without ancilla bits. The well-known MMD algorithm for synthesis of reversible circuits requires to store a truth table (or a Reed-Muller - RM transform) as a 2n vector to represent a reversible function of n variables. This representation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the reversible circuit to be designed. This allows for synthesis of large scale reversible circuits (30-bits), which is not possible with any existing algorithm. In addition, our unique multi-pass approach where the circuit is synthesized with various, yet specific, minterm orders yields quasi-optimal solution. The algorithm returns a description of the quasi-optimal circuit with respect to gate count or to its 'quantum cost'. Although the synthesis process in MP is relatively slower, the solution is found in real-time for smaller circuits of 8 bits or less.
This paper presents a new algorithm MP (multiple pass) to synthesize large reversible binary circuits without ancilla bits. The well-known MMD algorithm for synthesis of reversible circuits requires to store a truth table (or a Reed-Muller - RM transform) as a 2n vector to represent a reversible function of n variables. This representation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the reversible circuit to be designed. This allows for synthesis of large scale reversible circuits (30-bits), which is not possible with any existing algorithm. In addition, our unique multi-pass approach where the circuit is synthesized with various, yet specific, minterm orders yields quasi-optimal solution. The algorithm returns a description of the quasi-optimal circuit with respect to gate count or to its 'quantum cost'. Although the synthesis process in MP is relatively slower, the solution is found in real-time for smaller circuits of 8 bits or less.
This paper presents a new algorithm MP(multiple pass) to synthesize large reversible binary circuits without ancilla bits. The MMD algorithm requires to store a truth table (or a Reed-Muller -RM transform) as a 2^n vector for a reversible function of n variables. This representation prohibits synthesis of large functions. However, in MP we do not store such an exponentially growing data structure. The values of minterms are calculated in MP dynamically, one-by-one, from a set of logic equations that specify the reversible circuit to be designed. This allows for synthesis of large scale reversible circuits (30-bits), which is not possible with existing algorithms. In addition, our unique multipass approach where the circuit is synthesized with various, yet specific, minterm orders yields optimal solution. The algorithm returns a description of the optimal circuit with respect to gate count or quantum cost. Although the synthesis process is relatively slower, the solution is found in real-time for smaller circuits of 8 bits or less
Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.
An r-valued m-variable reversible logic function maps each of the rm input patters to a unique output pattern. The synthesis problem is to realize a reversible function by a cascade of primitive reversible gates. In this paper, we present a simple heuristic algorithm that exploits the bidirectional synthesis possibility inherent in the reversibility of the specification. The primitive reversible gates considered here are MVL extensions of the well-known binary Toffoli gates. We analyze the structure of the gates that we use and show how these gates can be easily simulated in a quantum technology. We present exhaustive results for the 9! 2-variable 3-valued reversible functions comparing the results of our algorithm to optimal results found by breadth-first search. We also show results for specific ternary examples including showing how the presented technique can be applied to the synthesis of a 3-input, 3-valued adder which is not itself a reversible problem. When the circuit for the full adder is synthesized, we use it as an example of an approach to a circuit simplification, called the templates tool. Formalization and proper investigation of the templates simplification tool proposed in this paper is still under investigation.
Reversible circuits are an emerging technology where all computations are performed in an invertible manner. Motivated by their promising applications, e.g. in the domain of quantum computation or in the low-power design, the synthesis of such circuits has been intensely studied. However, how to automatically realize reversible circuits with the minimal number of lines for large functions is an open research problem. In this paper, we propose a new synthesis approach which relies on concepts that are complementary to existing ones. While “conventional” function representations have been applied for synthesis so far (such as truth tables, ESOPs, BDDs), we exploit Quantum Multiple-valued Decision Diagrams (QMDDs) for this purpose. An algorithm is presented that performs transformations on this data-structure eventually leading to the desired circuit. Experimental results show the novelty of the proposed approach through enabling automatic synthesis of large reversible functions with the minimal number of circuit lines. Furthermore, the quantum cost of the resulting circuits is reduced by 50% on average compared to an existing state-of-the-art synthesis method.
This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.