Exact Synthesis of Ternary Reversible Functions using Ternary Toffoli Gates

Realization of logic functions using ternary reversible logic is known to require lesser number of lines as compared to conventional binary reversible logic. This aspect of ternary reversible logic has motivated researchers to explore various synthesis approaches in the past. Existing synthesis methods require additional lines (called ancilla lines) for synthesis, which is expensive from the quantum implementation point of view. There is no reported work for ternary reversible logic synthesis that require the minimum possible number of gates and also lines. This class of synthesis methods is called exact synthesis. In this paper two exact synthesis methods for ternary reversible logic have been proposed for the first time, one based on boolean satisfiability (SAT) and the other based on level-constrained heuristic search technique. A permutation representing a reversible ternary truth table is given as input, and a reversible circuit consisting of generalized ternary Toffoli gates that implements the permutation is obtained as output. Experimental studies have been carried out on various randomly generated ternary reversible functions.