- Overview
- Function representations
- Gate libraries
- Embedding
- Synthesis algorithms for reversible functions
- Synthesis algorithms for nonreversible functions
We classify reversible synthesis algorithms using 4 levels of categorization:
- Reversibility of the input: we distinguish between nonreversible and reversible functions. Embedding is not part of this categorization and need to be applied as a preprocess if needed. Columns in the overview figure refer to this level.
- Manipulation of the input: if the synthesis algorithm modifies the input during execution or emphasizes on the underlying function of the input rather than its structure, we refer to the synthesis approaches as functional synthesis, otherwise as structural synthesis. Functional synthesis algorithms guarantee optimum lines during synthesis and may also allow optimum number of gates. Rows in the overview figure refer to this level.
- Algorithm: For each category several algorithms may be proposed which differ in their conceptual methodology. Items in boxes refer to this level.
- Implementation: Each algorithm can be implemented in several different ways using several different data structures for the input representation. This level is not visible in the overview figure but discussed in the following text.
Example: The original transformation-based synthesis algorithm from D.M. Miller, D. Maslov and G.W. Dueck [DAC 40, 2003, 318-323.] starts from a reversible input function (1) and it is functional (2). Obviously, it falls in the category of transformation-based synthesis algorithms (3) and the specific works marks one of many implementations in this category (4).
We differentiate representations based on whether they are used to represent irreversible or reversible functions. Of course, irreversible functions include the reversible ones, but the function representation is not capturing this in the sense that it does not allow for dedicated treatment. Instead, function representations for reversible functions naturally reflect the reversibility of the function.
A truth table for a single Boolean function over n variables can be considered as a bitstring of size 2n, in which each bit represents the truth value for an assignment. The input assignments are lexicographically ordered from 0...0 to 1...1.
A binary decision diagram (BDD) is based on Shannon's expansion. Nodes represent functions and are labeled with a variable. Two children represent the negative and positive children of the node's function with resect to the node's variable. Reduction rules can compress the size of the BDD: a node can be skipped if both children are the same and if two nodes represent the same function only one needs to be kept. If co-factors are applied in the same order on each path and if reductions are applied as long as possible, one reaches a canonical representation, i.e., for any given function from each starting point the same representation is finally reached.
With n truth tables for Boolean functions over n variables one can represent a reversible function. In such a setting, it is easier to consider the mapping of input to output patterns. Only if all output patterns occur, the truth tables represent a reversible function.
A reversible function always implements a bijective mapping between input and output binary signals. That means a reversible function is an permutation of its inputs. It is known that any permutation can be decomposed into a product of cycles. Any permutation can be represent uniquely, up to the order, as product of disjoint cycles. Two cycles are called disjoint if they have no common members. Additionally any permutation cycle of length at least 4 can be written as a product of 3-cycle and 2-cycles. For example function f=[1,0,3,2,6,4,5,7] can be written in cycle form as (0,1)(2,3)(4,6,5).
| NOT | CNOT | Toffoli |
|---|---|---|
 |
 |
 |
The NCT library consists of the three gates NOT, CNOT, and Toffoli. The Toffoli gate is a double-controlled NOT gate. These gates are universal in a sense, that every Boolean function can be realized if an arbitrary number of variables (lines) is permitted. Given n variables, the NCT gate library can realize all permutations over n ≤ 3 variables and all even permutations over n > 3 variables.
| MCT |
|---|
 |
The MCT library consist of NOT, CNOT, Toffoli, and multi-controlled NOT gates. An MCT gate with n variables has (n-1) controls and one target. Each of the control line values pass through the gate unaltered while the target line value is inverted if all the control lines are set to 1.
| MPMCT |
|---|
 |
The MPMCT library is more general than the MCT library. The controls of the MPMCT gates cannot only have positive polarity but also negative polarity. In this case, the target line value is inverted if all the positive control lines are set to 1 and all the negative control lines are set to 0.
| Single-target-gate |
|---|
 |
Given n variables, a single-target gate (ST) has a control function c instead of control variables. The control function is a Boolean function with (n-1) inputs and one output. The target line is inverted if and only if c evaluates to true. All other variables remain unchanged. The target line cannot be in the support of c.
Most of the practical relevant functions are irreversible, but most of the existing reversible synthesis algorithms require a reversible function as input in some representation. Embedding is a technique that refers to algorithms that extend irreversible functions by additional inputs and outputs such that they are reversible, but under some given projection equal the initial irreversible function. A projection assigns some input variables to constants and discards some output variables. Every irreversible n-input/m-output function can be embedded by a reversibe function over n+m variables, however, often better embeddings are possible. In order to compute the optimum number of variables in a reversible embedding one needs to count the occurrance of the most frequent output pattern. It has been shown that finding an optimum embedding is coNP-hard. Both truth table based embedding algorithms and symbolic embedding alrogithms that work on the BDD representation of the function have been presented.
Exact synthesis algorithms guarantee minimality in number of gates (time) and number of lines (space).
Given a truth table of a Boolean function f, the decision problem “Does there exist a reversible circuit with k gates that represents f?” is translated into a SAT problem. A circuit can be extracted from a satisfying assignment to the problem. Asking the question, starting from k being 0 and incrementing it until the problem is satisfiable, gives the gate-optimum circuit.
Input representations: truth table
Gate libraries: MCT, MPMCT
Implementations: RevKit (command: exs --mode 1), RevKit (command: exs --mode 0)
References:
-
This paper presented exact synthesis algorithms that find the MCT circuit with the minimal number of gates for a given reversible function. The introduced algorithms formulate the synthesis problem as a sequence of decision problems. The decision problems are encoded as Boolean satisfiability (SAT) or SAT modulo theory (SMT) instances.
-
This paper uses BDDs to encode the decision problem. Consequently, it allows to represent all solutions to the problem and not just only a single one. The best solution can be selected with respect to some secondary cost criteria.
-
This paper extended the scope of exact synthesis algorithms by considering MPMCT gates in the synthesis problem.
Due to the use of a precomputed database of all gate-optimal 4-input reversible circuits up to 8 or 9 gates, generated by exhaustive calculations, it is possible to develop a tool for gate-optimal synthesis of any 4- variable reversible function (4-input gate-optimal circuits require at most 15 gates). In a similar way a tool for reducing quantum cost of 4-input reversible circuits can be developed. Such tools has been implemented and also used for constructing provably gate-optimal reversible circuits of any number of inputs by extrapolating properties of 3-input and 4-input optimal circuits.
Input representations: truth table
Gate libraries: MCT, MPMCT
References:
-
This paper presents an algorithm that generates a library of optimal realizations for small NCT reversible circuits. This library is used afterwards to synthesize optimal circuits for all 3-bit reversible functions, and millions of 4-bit circuits.
-
This paper presented the first tool capable of synthesizing a gate-optimal reversible circuit for any of the 16! reversible functions of 4 variables. The main idea behind this tool is to use hash tables to store a compact representation of the reversible functions for the optimal circuits up to 9 gates which fit into the resources available in nowadays computers. Then, by exhaustive combining the information about the circuits up to n gates, one can construct the optimal circuit for the function requiring up to 2n gates.
-
In this paper by exhaustive calculations of gate-optimal reversible circuits for all 16! reversible functions of 4 variables (lasting approximately for 13 days) it was possible to establish that there are only 144 4-bit functions requiring 15 gates in their optimal circuits and that there exists none requiring 16 or more gates.
-
The above two papers presented an approach to reducing quantum cost in reversible circuits which is similar to the one in [O. Golubitsky and D. Maslov, DAC 47, 2010]. However, it was based on finding all circuits implementing a given 4*4 reversible function with a specified value of gate count. Quantum cost of the constructed circuits for the set of reversible benchmarks was on average over 50% lower than the quantum cost of the circuits previously published in the literature. The approach is general enough to allow for quantum cost reduction in reversible circuits built from any reversible gate library.
-
This paper presents a method for constructing 4-input reversible MPMCT circuits with reduced quantum cost.
-
This paper presents an improvement over M. Szyprowski and P. Kerntopf [RM 9, 2011] with respect to synthesizing 4-input reversible circuits with reduced quantum cost.
-
The above four papers present the first approaches to constructing sequences of reversible functions of any number of variables for which gate-optimal circuits without additional lines have been found. The main result consists in proving their gate-minimality. Constructing the sequences was done by extrapolating circuits selected from the database as in M. Szyprowski and P. Kerntopf [RM 9, 2011, IEEE-NANO 11, 2011].
Functional heuristic synthesis algorithms guarantee minimality in number of lines (space).
Starting from a reversible function, transformation-based synthesis applies gates and adjusts the function representation accordingly in a way that each gate application gets the function closer to the identity function. If the identity function has been reached, all applied gates make up for the circuit that realizes the initial function.
Input representations: truth table, RCBDD
Gate libraries: MCT, MPMCT (only negative controls), MCT+F
Implementations: RevKit (command: tbs), RevKit (command: tbs -b and tbs -s)
References:
-
This paper first introduced the transformation based synthesis algorithm. It descibes first the basic unidirectional version but also the bidirectional variant which often results in circuits of smaller size.
-
This paper extends the transformation based synthesis algorithm by applying a heuristic approach to optimize the generated circuits. The major enhancement to the basic algorithm is using a template simplification tool, a tool which allows further reduction of the networks produced by the synthesis algorithm. A templates is a circuit of gates that realizes the identity function.
-
This paper presents a new variant of the transformation based synthesis that uses not only MCT gates but also Fredkin gates for generating reversible circuits.
-
This paper presents a solution to the scalability limitation of the transformation based reversible logic synthesis algorithm for constructing ancilla-free reversible circuits. The introduced algorithm used Quantum Multiple-valued Decision Diagrams (QMDDs) to represent reversible functions which enables the automatic synthesis of large functions with the minimal number of circuit lines.
-
This paper presents an extension to the transformation based synthesis algorithm that exploits Fredkin gates. By employing a look-ahead technique, more Fredkin gates can be added to the circuit overall leading in smaller gate count.
-
This paper presents a symbolic variant of the transformation based synthesis approach for reversible logic. The approach allows the realization of larger reversible functions without additional ancilla lines. It exploits a property considering the ordering in which assignments need to be considered for adjustment. Both a BDD and a SAT based implementation of the symbolic synthesis algorithm have been presented.
Every reversible function can be written in the form of disjoint cycles. For every cycle one can create a circuit that represents the cycle. By concatenating all cascades for each cycle, a reversible circuit can be created.
Input representations: truth table, permutation, cycles
Gate libraries: MCT, MPMCT
References:
-
The above papers introduces algorithm of synthesis that can be used for reversible circuits using MCT gate library. In the papers the method of mapping 2 and 3 cycles into sequence of MCT gates is presented.
-
This paper extends previous works and allows cycle based synthesis using Toffoli gates with positive and negative controls.
In decomposition-based synthesis the reversible function is iteratively decomposed into simpler functions based on the Young subgroup decomposition: Given a line i, every reversible function f can be decomposed into three functions f = g1 ○ f' ○ g2, where g1 and g2 can be realized with a single-target gate on line i and f' is a reversible function that does not change in line i. Based on this decomposition, synthesis algorithms determine the gates for g1 and g2 and then recur on f'.
Input representations: truth table, RCBDD
Gate libraries: STG
Implementations: RevKit (command: dbs), RevKit (command: dbs -s)
References:
-
This paper introduced the theoretical background for decomposition-based synthesis and proved the main decomposition rule explained above. The proofs involve Young subgroups, however, the synthesis algorithm derived from it, is quite straightforward. It computes new truth tables for each single-target gate in the circuit in a way that the propery of the decomposition is uphold.
-
This paper proposes a symbolic variant of the truth table based variant introduced by De Vos and Van Rentergem. It works on the binary decision diagram representation of the reversible function. The paper also introduces how simple algebraric operations can be performed on the BDD representation of reversible functions, e.g., gate composition or reversibility checking.
Synthesis in these category synthesize a circuit based on a metaheuristic such as genetic algorithms, genetic programming, ant colony optimization, or particle swarm optimization.
Input representation: truth table
Gate libraries: MCT, MCT+P (in principle, any functionally complete set of gates may be used)
References:
-
This paper gives a detailed description of a method to design reversible circuits using genetic programming. The method does not require a supporting database of circuits: circuits are evolved from scratch. Reported circuits are among the best in the prevailing literature.
-
This paper introduces a variation of a genetic algorithm, where the length of the chromosomes is adaptive. The method also uses a database as in Golubitsky-Maslov IEEE Tr. Comp. 61 (see enumerative synthesis). Reported circuits are among the best in the prevailing literature.
-
This paper introduces a hybrid combination of genetic algorithms and particle swarm optimization for the synthesis of reversible circuits.
Greedy synthesis is similar to transformation-based synthesis. At each step it applies a set of gates to the current function to be synthesized and chooses the gate that brings the function closest to the identity function.
Input representation: BDD
Gate libraries: arbitrary
References:
-
P. Kerntopf: A new heuristic algorithm for reversible logic synthesis, in: DAC 41, 2004, 834-837.
This paper proposes an incremental approach to reversible logic synthesis using shared binary decision diagrams (SBDD) for the representation of reversible functions and for measuring their complexity.
Structural algorithms do neither guarantee optimality for number of gates nor for number of lines.
An ESOP expression of a function f is an exclusive sum of products. Given an ESOP expression of a function, it can easily be translated into a cascade of Toffoli gates by adding one additional circuit line to store the result. This line is initialized with 0 and for each product term in the ESOP expression a MPMCT gate is added with controls according to the produc term and a target on the additional line. If MCT circuits are targeted, negative controls can be realized using NOT gates. In this case, the aim is to minimize the number of NOT gates.
Gate libraries: MCT, MPMCT
Implementations: RevKit (command: esopbs)
References:
-
This paper introduces the idea of ESOP-based reversible logic synthesis.
-
This paper shows how evolutionary algorithms may be used to obtain reversivle circuits based on structural techniques used for irreversible design.
In hierarchical synthesis the function is represented in a structural way, e.g., using a logic network. Then, small subparts of the structure are considered functionally, embedded into reversible functions and synthesized using functional algorithms. The resulting reversible circuits are combined with respect to the structural representation of the function. This combination of subcircuits leads to an additional number of lines, which are essentially required to store intermediate computation steps.
Input representation: BDD, AIG
Gate libraries: imposed by the underlying functional synthesis algorithm
Implementations: RevKit (command: hdbs), RevKit (command: cbs)
References:
-
This paper first introduced the ideas of hierarchical synthesis based on binary decision diagrams. Several node configurations are considered (e.g., nodes having constant inputs, nodes having complemented edges, and nodes that are shared to multiple parents). For each configuation the optimum circuit realization is precomputed using SAT-based synthesis techniques.
-
This paper considers Biconditional Binary Decision Diagrams (BBDDs) instead of BDDs as structural representation for the input function.
-
Instead of precomputing optimum circuits for each BDD node, this paper suggests to precompute optimum circuits for certain selected subgraphs in the BDD. These subgraphs are determined in the input BDD using subgraph isomorphism.
-
This paper considers Kronecker-functional Decision Diagrams (KFDDs) instead of BDDs as structural representation for the input function. It found that in particular the positive Davio decomposition is advantageous for reversible circuits.
-
The paper introduces design of reversible circuits based on Functional Decision Diagrams. It is shown that realizations with lower quantum cost or less ancilla lines are obtained as compared with other DD-based methods.
-
This paper applies hierarchical synthesis to a higher level compared to decision diagrams. The irreversible input function is represented as an And-inverter graph (AIG). Subgraphs in the AIG are determined, which are then optimally embeded and synthesized using symbolic functional heuristic algorithms.
Building block synthesis relies on existing realizations of frequently used functions/operations as well as a higher level description of the functionality to be synthesized, e.g., in terms of hardware description languages (HDLs). It represents a complementary approach to the synthesis approaches reviewed above: The function to be synthesized is described in HDL terms, while existing building blocks are employed to create the corresponding netlists. Main challenges remain the composition of the respectively described data and control flow.
Input representation: SyReC description
Gate libraries: MCT, MPMCT
References:
-
This paper presents one of the first proposals of a HDL for reversible logic and a corresponding synthesis approach. It extends the reversible software language Janus by dedicated constructs usually needed in hardware design as well as a corresponding synthesis scheme. For the first time, this allowed the automatic synthesis of complex functionality provided in a higher level of abstraction.
-
This paper introduced optimizations of the SyReC-based synthesis scheme. It particularly incorporated the concept of reversible undo which led to circuit that require a significantly smaller number of required circuit lines. Moreover, the resulting circuits are purely reversible and do not include (arbitrarily assigned) garbage outputs anymore.
-
This paper presents the findings proposed before in a more comprehensive fashion, including a grammar of the proposed SyReC language as well as detailed description of the synthesis for the data and control flow.