Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A Transformation Based Algorithm for Ternary Reversible Logic Synthesis using Universally Controlled Ternary Gates

Marek A. Perkowski, Eric Curtis

Published Jan 1, 2004• 24 citations
OpenAlex

Abstract

In this paper a synthesis algorithm for reversible ternary logic cascades is presented. The algorithm can find a solution for any reversible ternary function with n inputs and n outputs utilizing ternary inverter gates and the new (quantum realizable) UCTG gates which are a powerful generalization of ternary Toffoli gates and Generalized Ternary Gates [4]. The algorithm is an extension of the algorithm presented by Dueck, Maslov, and Miller in [3]. A unique feature of this algorithm is that it utilizes no extra wires to generate the outputs. A basic compaction algorithm is defined to improve the results of the basic algorithm. This paper also provides the groundwork for transforming any n*n Toffoli based binary synthesis algorithm into a ternary synthesis algorithm using the new UCTG gates.

Related papers

Synthesis of ternary non-reversible logic circuits

Xiaoyu Li, Guowu Yang, Desheng Zheng

Reversible quantum circuits are a necessary subclass of quantum computation and its realization is required for any quantum computer to be universal. This paper investigates how to synthesis of arbitrary ternary non-reversible logic circuits by adding inputs with constant value and garbage outputs. Group theory has been also used to solve the synthesis of reversible logic circuits. Our algorithm uses the SNT (ternary Swap gate, ternary NOT gate, ternary Toffoli gate) library, by reducing the ternary non-reversible logic circuit synthesis problem to group theory representation. The main result shows the relationship of ternary non-reversible logic circuits and the reversible circuits. The realization approach is constructive and can be further used to develop software for synthesis of arbitrary d-level circuits. This result is significantly different from the binary non-reversible logic circuits.

IEEE Congress on Evolutionary Computation (CEC)•Jul 1, 2010•1 citation

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

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

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 30, 2006•379 citations

Logic Synthesis of Ternary Quantum Circuits with Minimal Qutrits

Xiaoyu Li, Guowu Yang, Desheng Zheng

Abstract — This paper investigates a universal approach of synthesizing arbitrary ternary logic circuits in quantum computation based on the truth table technology. It takes into account of the relationship of classical logic and quantum logic circuits. By adding inputs with constant value and garbage outputs, the classical non-reversible logic can be transformed into reversible logic. Combined with group theory, it provides an algorithm using the ternary Swap gate, ternary NOT gate and ternary Toffoli gate library. Simultaneously, the main result shows that the numbers of qutrits we use are minimal compared to other methods. We also illustrate with two examples to test our approach. Index Terms — ternary quantum computation, reversible logic, circuit synthesis, group theory I.

Journal of Computers•Jul 17, 2013•17 citations

Synthesis of Reversible Circuits from a Subset of Muthukrishnan-Stroud Quantum Realizable Multi-Valued Gates

Marek A. Perkowski, Nicholas Denler, Bruce Yen +1 more

We present a new type of quantum realizable reversible cascade. Next we present a new algorithm to synthesize arbitrary single-output ternary functions using these reversible cascades. The cascades use “Generalized Multi-Valued Gates” introduced here, which extend the concept of Generalized Ternary Gates introduced previously. While there were 216 GTGs, a total of 12 ternary gates of the new type are sufficient to realize arbitrary ternary functions. (The count can be further reduced to 5 gates, three 2-qubit and two 1-qubit). Such gates are realizable in quantum ion trap devices. For some functions, the algorithm requires fewer gates than results previously published [1, 5, 8, 14]. In addition, the algorithm also does conversion from arbitrary ternary logic to reversible logic at the cost of relatively small garbage. The algorithm is implemented here in ternary logic, but generalization to arbitrary radix is both straightforward and sees a reduction in growth of cost as the radix is increased.

•Jan 1, 2004•26 citations

Synthesis of reversible logic functions using ternary Max-Min algebra

Musharrat Khan, Jacqueline E. Rice

Ternary reversible circuits are normally realized as Toffoli cascades using ternary Galois field sum of products (TGFSOP) expressions. In this work we propose a new method for realization of ternary reversible circuits using ternary Max-Min expressions. The proposed method uses ternary multiple-controlled unary gates to map Max-Min expression into reversible circuit. We also present techniques for realizations of multiple-controlled unary gates using M-S gates at the quantum level. Preliminary results show that the proposed method produces better results than TGFSOP-based method in terms of both quantum cost and ancilla inputs.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•7 citations

Exact Synthesis of Ternary Reversible Functions Using Ternary Toffoli Gates

Abhoy Kole, P. Mercy Nesa Rani, Kamalika Datta +2 more

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2017•10 citations
In this paper a synthesis algorithm for reversible ternary logic cascades is presented. The algorithm can find a solution for any reversible ternary function with n inputs and n outputs utilizing ternary inverter gates and the new (quantum realizable) UCTG gates which are a powerful generalization of ternary Toffoli gates and Generalized Ternary Gates [4]. The algorithm is an extension of the algorithm presented by Dueck, Maslov, and Miller in [3]. A unique feature of this algorithm is that it utilizes no extra wires to generate the outputs. A basic compaction algorithm is defined to improve the results of the basic algorithm. This paper also provides the groundwork for transforming any n*n Toffoli based binary synthesis algorithm into a ternary synthesis algorithm using the new UCTG gates.
Reversible quantum circuits are a necessary subclass of quantum computation and its realization is required for any quantum computer to be universal. This paper investigates how to synthesis of arbitrary ternary non-reversible logic circuits by adding inputs with constant value and garbage outputs. Group theory has been also used to solve the synthesis of reversible logic circuits. Our algorithm uses the SNT (ternary Swap gate, ternary NOT gate, ternary Toffoli gate) library, by reducing the ternary non-reversible logic circuit synthesis problem to group theory representation. The main result shows the relationship of ternary non-reversible logic circuits and the reversible circuits. The realization approach is constructive and can be further used to develop software for synthesis of arbitrary d-level circuits. This result is significantly different from the binary non-reversible logic circuits.
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
Abstract — This paper investigates a universal approach of synthesizing arbitrary ternary logic circuits in quantum computation based on the truth table technology. It takes into account of the relationship of classical logic and quantum logic circuits. By adding inputs with constant value and garbage outputs, the classical non-reversible logic can be transformed into reversible logic. Combined with group theory, it provides an algorithm using the ternary Swap gate, ternary NOT gate and ternary Toffoli gate library. Simultaneously, the main result shows that the numbers of qutrits we use are minimal compared to other methods. We also illustrate with two examples to test our approach. Index Terms — ternary quantum computation, reversible logic, circuit synthesis, group theory I.
We present a new type of quantum realizable reversible cascade. Next we present a new algorithm to synthesize arbitrary single-output ternary functions using these reversible cascades. The cascades use “Generalized Multi-Valued Gates” introduced here, which extend the concept of Generalized Ternary Gates introduced previously. While there were 216 GTGs, a total of 12 ternary gates of the new type are sufficient to realize arbitrary ternary functions. (The count can be further reduced to 5 gates, three 2-qubit and two 1-qubit). Such gates are realizable in quantum ion trap devices. For some functions, the algorithm requires fewer gates than results previously published [1, 5, 8, 14]. In addition, the algorithm also does conversion from arbitrary ternary logic to reversible logic at the cost of relatively small garbage. The algorithm is implemented here in ternary logic, but generalization to arbitrary radix is both straightforward and sees a reduction in growth of cost as the radix is increased.
Ternary reversible circuits are normally realized as Toffoli cascades using ternary Galois field sum of products (TGFSOP) expressions. In this work we propose a new method for realization of ternary reversible circuits using ternary Max-Min expressions. The proposed method uses ternary multiple-controlled unary gates to map Max-Min expression into reversible circuit. We also present techniques for realizations of multiple-controlled unary gates using M-S gates at the quantum level. Preliminary results show that the proposed method produces better results than TGFSOP-based method in terms of both quantum cost and ancilla inputs.
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.