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

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

Marek A. Perkowski, Nicholas Denler, Bruce Yen, Paweł Kerntopf

Published Jan 1, 2004• 26 citations
OpenAlex

Abstract

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.

Related papers

Optimized design of the universal ternary gates for quantum/reversible computing

V. G. Deĭbuk, Iryna Turchenko, Vladyslav Shults

Multiple-valued logic is a promising choice for future computer technologies, which provides a set of advantages comparing to binary circuits. In this paper, we have developed a genetic algorithm-based synthesis of ternary reversible circuits using Muthukrishnan-Stroud gates. The method for chromosomes coding, as well as a reasonable choice of algorithm parameters, allowed obtaining circuits for ternary Toffoli and modified Fredkin gates, which are better than other published methods in terms of quantum cost, delay times and amount of input ancillary and output garbage qutrits.

IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS)•Sep 1, 2015•3 citations

New design of reversible/quantum devices for ternary arithmetic

Zhengbing Hu, V. G. Deĭbuk

Multiple-valued logic is a promising choice for future computer technologies, which provides a set of advantages comparing to binary circuits. We have developed an adaptive genetic algorithm for ternary reversible circuits using Muthukrishnan-Stroud gates. The method for chromosomes coding, as well as a reasonable choice of algorithm parameters, allowed obtaining circuits for ternary arithmetic devices, which are better than other known methods in terms of quantum cost, delay time and amount of input ancillary and output garbage qutrits. Based on our realization of ternary parallel full-adder we synthesized reversible ternary parallel adder/subtractor, which has better parameters over the previously reported devices.

IEEE International Conference on Data Stream Mining & Processing (DSMP)•Aug 1, 2016•2 citations

Genetic Synthesis of New Reversible/Quantum Ternary Comparator

V. G. Deĭbuk, Andrij V. Biloshytskyi

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.

Advances in Electrical and Computer Engineering•Jan 1, 2015•12 citations

Genetic algorithm based synthesis of multi-output ternary functions using quantum cascade of generalized ternary gates

Mozammel H. A. Khan, Marek A. Perkowski

Ternary quantum circuits have recently been introduced to help reduce the size of multi-valued logic for multi-level quantum computing systems. However, synthesizing these quantum circuits is not easy. We describe a new genetic algorithm based synthesizer for ternary quantum circuits. Our results show some of the synthesized circuits use fewer gates than previously published methods.

IEEE Congress on Evolutionary Computation (CEC)•Feb 22, 2005•41 citations

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

Design of Reversible/Quantum Ternary Comparator Circuits

Mozammel H. A. Khan

Abstract—Multiple-valued quantum circuits are promising choices for future quantum computing technology, since the multiple-valued quantum system is more compact than the corresponding binary quantum system. Grover’s quantum search algorithm requires a sub-circuit called oracle, which takes a set of inputs and gives an output stating whether a given search condition on the inputs is satisfied or not. Equality, less-than, and greater-than comparisons are widely used as search conditions. In this paper, we show design of quantum ternary equality, less-than, and greater-than comparators on the top of ion-trap realizable 1-qutrit gates and 2-qutrit Muthukrishnan-Stroud gates. Index Terms—Multiple-valued logic, quantum logic, reversible logic, ternary comparators, ternary logic I.

Engineering letters•Jan 1, 2008•19 citations
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.
Multiple-valued logic is a promising choice for future computer technologies, which provides a set of advantages comparing to binary circuits. In this paper, we have developed a genetic algorithm-based synthesis of ternary reversible circuits using Muthukrishnan-Stroud gates. The method for chromosomes coding, as well as a reasonable choice of algorithm parameters, allowed obtaining circuits for ternary Toffoli and modified Fredkin gates, which are better than other published methods in terms of quantum cost, delay times and amount of input ancillary and output garbage qutrits.
Multiple-valued logic is a promising choice for future computer technologies, which provides a set of advantages comparing to binary circuits. We have developed an adaptive genetic algorithm for ternary reversible circuits using Muthukrishnan-Stroud gates. The method for chromosomes coding, as well as a reasonable choice of algorithm parameters, allowed obtaining circuits for ternary arithmetic devices, which are better than other known methods in terms of quantum cost, delay time and amount of input ancillary and output garbage qutrits. Based on our realization of ternary parallel full-adder we synthesized reversible ternary parallel adder/subtractor, which has better parameters over the previously reported devices.
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 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.
Abstract—Multiple-valued quantum circuits are promising choices for future quantum computing technology, since the multiple-valued quantum system is more compact than the corresponding binary quantum system. Grover’s quantum search algorithm requires a sub-circuit called oracle, which takes a set of inputs and gives an output stating whether a given search condition on the inputs is satisfied or not. Equality, less-than, and greater-than comparisons are widely used as search conditions. In this paper, we show design of quantum ternary equality, less-than, and greater-than comparators on the top of ion-trap realizable 1-qutrit gates and 2-qutrit Muthukrishnan-Stroud gates. Index Terms—Multiple-valued logic, quantum logic, reversible logic, ternary comparators, ternary logic I.