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.
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.
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.
Realization of logic functions using ternary reversible logic is known to requirelesser number of lines as compared to conventionalbinary 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 pointof view. There is no reported work for ternary reversible logic synthesisthat require the minimum possible number of gates and also lines. Thisclass 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 booleansatisfiability (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 ofgeneralized ternary Toffoli gates that implements the permutationis obtained as output. Experimental studies have been carried out on various randomly generatedternary reversible functions.
One of the main motivations for using ternary logic systems is the amount of information per circuit line is higher as compared to the corresponding binary logic representation, thereby leading to more compact circuit realizations. This is particularly attractive for quantum computing as qutrits are expensive resources and minimizing their number is one of the main objectives during synthesis. Therefore, ternary reversible logic synthesis has drawn significant attention among researchers. It deals with fundamental unit of information called qutrits that can exist in one of the three states |0>, |1> and |2>. Hence, the aim of this paper is to bridge the knowledge gap for the beginners in this domain than searching the entire space. Therefore, the present work discusses the basic concepts of ternary reversible logic and ternary reversible gates. The detailed discussion of the various ternary reversible logic synthesis will enable the beginners in this domain to understand the ternary reversible logic in a better way.
The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing (FTQC). The primary motivation of this work is to overcome the inherent disadvantages of existing synthesis techniques: approximate heuristic methods often miss optimal solutions, while pure exact computational methods suffer from combinatorial explosion on deep circuits. While the strict NCT library (NOT, CNOT, Toffoli) is often preferred due to the high cost of distilling non-Clifford states required for arbitrary gates, standard physical implementations frequently utilize the broader NCV library (NOT, CNOT, V, V-dagger), requiring the decomposition of Toffoli gates into five elementary operations. To bridge this gap, this paper presents a unified, highly scalable methodology for the optimal design of reversible circuits across both libraries. First, a Mixed-Integer Non-Linear Programming (MINLP) formulation, linearized for the high-performance IBM ILOG CPLEX solver, is introduced to automate the exact generation of globally optimal strict NCT topologies. Second, a systematic four-phase optimization framework is proposed to reduce NCV costs. By replacing Toffoli gates with specific NCV decompositions, permuting control lines to match subsequent linear gates, and applying exact local searches via an extended MINLP solver on bounded sliding windows, significant gate cancellations are achieved. Applying this methodology to prominent primitives (MIG, SAYEM, URG, TSG, and MKG), we match global NCT optimality constraints and achieve highly optimized NCV Quantum Costs of 7, 14, and 12 for the MIG, TSG, and MKG gates, respectively, establishing best-known upper bounds that significantly outperform heuristic literature benchmarks.
The synthesis and optimization of quantum circuits are essential for the construction of quantum computers. This paper proposes two methods to reduce the quantum cost of 3-bit reversible circuits. The first method utilizes basic building blocks of gate pairs using different Toffoli decompositions. These gate pairs are used to reconstruct the quantum circuits where further optimization rules will be applied to synthesize the optimized circuit. The second method suggests using a new universal library, which provides better quantum cost when compared with previous work in both cost015 and cost115 metrics; this proposed new universal library “Negative NCT” uses gates that operate on the target qubit only when the control qubit’s state is zero. A combination of the proposed basic building blocks of pairs of gates and the proposed Negative NCT library is used in this work for synthesis and optimization, where the Negative NCT library showed better quantum cost after optimization compared with the NCT library despite having the same circuit size. The reversible circuits over three bits form a permutation group of size 40,320 (23!), which is a subset of the symmetric group, where the NCT library is considered as the generators of the permutation group.
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.