While the role of ternary reversible and quantum computation has been growing, synthesis methodologies for such logic, have been addressed in only a few works. A reversible ternary logic function can be expressed as minterms by using projection operators. In this paper, a novel realization of the projection operators using a minimum number of permutative ternary Muthukrishnan-Stroud (M-S) gates is presented. Next, an efficient method for logic simplification for ternary reversible logic is proposed. This method along with the new construction of projection operators yields significantly lower gate cost of approximately 31% less than that obtained by earlier methodologies, for the synthesis of ternary benchmark circuits.
While the role of ternary reversible and quantum computation has been growing, synthesis methodologies for such logic, have been addressed in only a few works. A reversible ternary logic function can be expressed as minterms by using projection operators. In this paper, a novel realization of the projection operators using a minimum number of permutative ternary Muthukrishnan-Stroud (M-S) gates is presented. Next, an efficient method for logic simplification for ternary reversible logic is proposed. This method along with the new construction of projection operators yields significantly lower gate cost of approximately 31% less than that obtained by earlier methodologies, for the synthesis of ternary benchmark circuits.
Quantum computation relies on exploiting quantum mechanical phenomena, and has received significant attention in recent years. Higher-dimensional quantum systems increase the density of encoded information per computing element (e.g., qutrit for three-level system), resulting in less resource overhead. For instance, 63% reduction in the number of qutrits is possible for ternary quantum systems as compared to the corresponding binary systems. The proposed work exploits this fact to synthesize ternary reversible circuits employing a cycle-based technique. The method starts from the ternary reversible specification of a given function in the form of a permutation. The permutation cycles are factored into simpler three-cycles and two-cycles, which are then mapped to ternary reversible gates. Different gate libraries are used to synthesize three-cycles and two-cycles, respectively. A gate decomposition approach is also proposed to synthesize a quantum gate netlist in terms of elementary ternary quantum gates, viz. Muthukrishnan–Stroud gate and shift gate. Synthesis results on benchmark functions indicate that the proposed method results in 27% and 6% improvements in quantum cost and gate count, respectively, over existing works in the literature.
Methods of quantum/reversible logic synthesis are based on the use of the binary nature of quantum computing. However, multiple-valued logic is a promising choice for future quantum computer technology due to a number of advantages over binary circuits. In this paper we have developed a synthesis of ternary reversible circuits based on Muthukrishnan-Stroud gates using a genetic algorithm. The method of coding chromosome is presented, and well-grounded choice of algorithm parameters allowed obtaining better circuit schemes of one- and n-qutrit ternary comparators compared with other methods. These parameters are quantum cost of received reversible devices, delay time and number of constant input (ancilla) lines. Proposed implementation of the genetic algorithm has led to reducing of the device delay time and the number of ancilla qutrits to 1 and 2n-1 for one- and n-qutrits full comparators, respectively. For designing of n-qutrit comparator we have introduced a complementary device which compares output functions of 1-qutrit comparators.
Reversible ternary circuit design is now being taken into consideration for its application within the quantum computer and other technologies associated with the nanotechnology domain, in addition to the advantages of the ternary logic application as opposed to binary logic. Multiplier circuit is one of the most important computing circuit in the ALU. Therefore, the circuit optimization for the multiplication will lead to efficient processor. In this paper, the reversible circuit for multiplication of two unsigned two-digit ternary numbers has been proposed. To construct reversible ternary multiplier, a new component termed TPPG with the quantum cost of 13 for partial product generation was proposed. In addition, we have introduced four new blocks of reversible ternary adder with the quantum cost of 11, 10, 7, 5 and one constant input, which can be used in the proposed multiplier circuit. We attempted to optimize the design of the circuits in terms of quantum cost, a number of primitive gates, constant inputs, and garbage outputs as far as possible. To realize all proposed circuits, one-qutrit shift gates and two-qutrit Muthukrishnan-Stroud gates were used.
Abstract Quantum computation which relies on exploiting quantum mechanical phenomena, has received significant attention in recent years. Higher dimensional quantum systems increase the density of encoded information per computing element (e.g. qutrit for the 3-level system), resulting in less resource overhead. Recently, there have been several works in the synthesis of ternary reversible functions, most of which are not scalable. Therefore, this study proposes a scalable approach for the synthesis of ternary logic functions using Max-Min algebra. In this approach, from a ternary truth table, Max-Min expressions are first generated with the help of ternary Max-Min algebra. Then, the expressions are minimized using Boolean simplification rules. After that, the minimized expressions are mapped to ternary reversible gates. We have also proposed a decomposition structure to map the ternary reversible gates into ternary elementary gates. Experimental evaluation shows that the proposed synthesis approach is more scalable as compared to existing synthesis approaches. Keywords: Ternary reversible circuit, quantum computing, qutrit, reversible literals, non-reversible literals Cite this Article P. Mercy Nesa Rani, Leniency Marbaniang, Majid Haghparast, Kamalika Datta. An Improved Ternary Logic Synthesis Approach Using Ternary Max-Min Algebra. Journal of Advanced Database Management & Systems. 2019; 6(2): 40–47p.
The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers for the last two decades due to increasing interest in quantum computing. Although lot of works have been done on the synthesis of binary reversible circuits, very less works have been reported on the synthesis of ternary reversible circuits. Ternary circuits have lower cost of implementation as compared to their binary counterparts. However, the synthesis approaches that exist for ternary reversible circuits either use too many circuit lines (qutrits) or too many gates. Only one prior work has discussed the problem of generating cost-optimal ternary reversible circuits, but for a very restrictive gate library, which limits the approach to a specific subset of ternary reversible functions and often the solution becomes sub-optimal due to the imposed restrictions. The present paper overcomes that restriction, and uses multiple control ternary Toffoli gates with all possible ternary target operations as the gate library. This gate library is functionally complete and can be used to synthesize any arbitrary function. The proposed SAT-based synthesis approach provides low cost solutions in terms of the number of gates for any arbitrary ternary reversible function. Experimental results on various randomly generated permutations as well as standard ternary benchmarks establish this claim. The results can be used as template for other synthesis approaches by observing how far they deviate from the optimal solutions.
Typical methods of quantum/reversible synthesis are based on using the binary character of quantum computing.However, multi-valued logic is a promising choice for future computer technologies, given a set of advantages when comparing to binary circuits.In this work, we have developed a genetic algorithm-based synthesis of ternary reversible circuits using Muthukrishnan-Stroud gates.The method for chromosomes coding that we present, as well as a judicious choice of algorithm parameters, allowed obtaining circuits for half-adder and full adder which are better than other published methods in terms of cost, delay times and amount of input ancillary bits.A structure of the circuits is analyzed in details, based on their decomposition.