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

Journal of Physics A Mathematical and General

Implementing an arbitrary reversible logic gate

Yvan Van Rentergem, Alexis De Vos, Leo Storme

Published Apr 6, 2005• 28 citations
Publisher

Abstract

The (2 w )! reversible logic gates of width w , i.e. reversible logic gates with w inputs and w outputs, together with the action of cascading, form a group R . We define a subgroup K , consisting of the SWITCHED gates. There are [(2 w −1 )!] 2 such gates. They partition the group R into 2 w −1 + 1 double cosets. This allows us to decompose an arbitrary reversible gate into the cascade of three gates: a SWITCHED gate, an upside-down simple control gate and a second SWITCHED gate. We present an algorithm to perform this factorization, and thus provide a method of implementing an arbitrary reversible gate into hardware. The algorithm can be used to automate the implementation of a reversible function in future (c-MOS) technologies, realizing low-cost computing.

DOI
10.1088/0305-4470/38/16/007

Related papers

The decomposition of an arbitrary reversible logic circuit

Alexis De Vos, Yvan Van Rentergem, Koen De Keyser

The (2 w )! reversible logic circuits of width w , i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group G , isomorphic to the symmetric group . We define two conjugate subgroups G 1 and G 2 . Together they partition the group G into 2 w −1 + 1 double cosets. These allow us to decompose an arbitrary member of G into a cascade of three simpler members. This decomposition is a far relative of the well-known LU decomposition of a square matrix.

Journal of Physics A Mathematical and General•Apr 19, 2006•7 citations

Six Synthesis Methods for Reversible Logic

Yvan Van Rentergem, Alexis De Vos, Koen De Keyser

The (2w)! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S2w. Therefore, we investigate the group Sn as well as one of its subgroups isomorphic to Sn/2 × Sn/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice.

Open Systems & Information Dynamics•Mar 1, 2007•5 citations

Using group theory in reversible computing

Yvan Van Rentergem, Alexis De Vos, K. de Keyser

The (2w)! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S2w. Therefore, we investigate the group Snas well as one of its subgroups isomorphic to Sn/2times Sn/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. Different choices of the coset space and different choices of the coset representatives lead to four different syntheses for implementing an arbitrary reversible logic operation into hardware. Comparison leads to a best choice: a single coset space, with representatives that are generalized TOFFOLI and FREDKIN gates.

IEEE Congress on Evolutionary Computation (CEC)•Sep 22, 2006•6 citations

Reversible logic

Alexis De Vos

Reversible logic circuits are beneficial to both classical and quantum computer design. Present-day logic building-blocks (like OR gates and NAND gates) are logically irreversible and therefore cannot be used for designing reversible computers. Thus reversible computation needs an appropriate design methodology. In contrast to conventional digital logic circuits, reversible logic circuits (of a same logic width w) form a mathematical group. The reversible circuits of width w form a group isomorphic to the symmetric group S_{2^w}. Its Young subgroups allow systematic and efficient synthesis of an arbitrary reversible circuit. We can choose either a left coset, a right coset, or a double coset approach. The optimal design is reminiscent of the so-called banyan networks of telecommunication. As an illustration, three experimental prototypes (in c-MOS chip technology) of reversible computing devices are presented. Special care has been taken to avoid as much as possible the appearance of garbage bits. The examples illustrate how, in a near future, reversible computers will outperform conventional computers, in terms of power dissipation and heat generation.

•Jan 1, 2009•0 citations

Realization and synthesis of reversible functions throng double-coset

Fu Chen, Guowu Yang, Xiaoyu Li

Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)•Dec 1, 2010•0 citations

Multiple-valued reversible logic circuits

Alexis De Vos, Yvan Van Rentergem

We consider the symmetric group S-n in the special case where n = pq (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S-pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup S-p(q), whereas the second one is an element of the dual Young subgroup S-p(q). This leads to synthesis methods for arbitrary multiple-valued reversible logic circuits of logic width w. These circuits indeed form a group isomorphic to Sr-w, where r is the radix of the multiple-valued logic. A particularly efficient decomposition is found by choosing p = r and thus q = r(w-1). As a result, an arbitrary reversible logic circuit of radix r and width w is decomposed into a cascade of 2w - 1 control gates, i.e. logic building blocks, which manipulate only one of the w dits.

•Jan 1, 2009•12 citations
The (2 w )! reversible logic gates of width w , i.e. reversible logic gates with w inputs and w outputs, together with the action of cascading, form a group R . We define a subgroup K , consisting of the SWITCHED gates. There are [(2 w −1 )!] 2 such gates. They partition the group R into 2 w −1 + 1 double cosets. This allows us to decompose an arbitrary reversible gate into the cascade of three gates: a SWITCHED gate, an upside-down simple control gate and a second SWITCHED gate. We present an algorithm to perform this factorization, and thus provide a method of implementing an arbitrary reversible gate into hardware. The algorithm can be used to automate the implementation of a reversible function in future (c-MOS) technologies, realizing low-cost computing.
The (2 w )! reversible logic circuits of width w , i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group G , isomorphic to the symmetric group . We define two conjugate subgroups G 1 and G 2 . Together they partition the group G into 2 w −1 + 1 double cosets. These allow us to decompose an arbitrary member of G into a cascade of three simpler members. This decomposition is a far relative of the well-known LU decomposition of a square matrix.
The (2w)! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S2w. Therefore, we investigate the group Sn as well as one of its subgroups isomorphic to Sn/2 × Sn/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice.
The (2w)! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S2w. Therefore, we investigate the group Snas well as one of its subgroups isomorphic to Sn/2times Sn/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. Different choices of the coset space and different choices of the coset representatives lead to four different syntheses for implementing an arbitrary reversible logic operation into hardware. Comparison leads to a best choice: a single coset space, with representatives that are generalized TOFFOLI and FREDKIN gates.
Reversible logic circuits are beneficial to both classical and quantum computer design. Present-day logic building-blocks (like OR gates and NAND gates) are logically irreversible and therefore cannot be used for designing reversible computers. Thus reversible computation needs an appropriate design methodology. In contrast to conventional digital logic circuits, reversible logic circuits (of a same logic width w) form a mathematical group. The reversible circuits of width w form a group isomorphic to the symmetric group S_{2^w}. Its Young subgroups allow systematic and efficient synthesis of an arbitrary reversible circuit. We can choose either a left coset, a right coset, or a double coset approach. The optimal design is reminiscent of the so-called banyan networks of telecommunication. As an illustration, three experimental prototypes (in c-MOS chip technology) of reversible computing devices are presented. Special care has been taken to avoid as much as possible the appearance of garbage bits. The examples illustrate how, in a near future, reversible computers will outperform conventional computers, in terms of power dissipation and heat generation.
Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.
We consider the symmetric group S-n in the special case where n = pq (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S-pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup S-p(q), whereas the second one is an element of the dual Young subgroup S-p(q). This leads to synthesis methods for arbitrary multiple-valued reversible logic circuits of logic width w. These circuits indeed form a group isomorphic to Sr-w, where r is the radix of the multiple-valued logic. A particularly efficient decomposition is found by choosing p = r and thus q = r(w-1). As a result, an arbitrary reversible logic circuit of radix r and width w is decomposed into a cascade of 2w - 1 control gates, i.e. logic building blocks, which manipulate only one of the w dits.