© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal 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

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

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

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 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•40 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

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

Marek A. Perkowski, Eric Curtis

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.

•Jan 1, 2004•24 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.

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.

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.

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.

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.