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

Generating the group of reversible logic gates

Alexis De Vos, Birger Raa, Leo Storme

Published Aug 7, 2002• 81 citations
Publisher

Abstract

Reversible logic plays a fundamental role both in ultra-low power electronics and in quantum computing. It is therefore important to have an insight into the structure of the group formed by the reversible logic gates and their cascading into reversible circuits. Such insight is gained from constructing chains of maximal subgroups. The subgroup of control gates plays a prominent role, as it is a Sylow 2-subgroup.

DOI
10.1088/0305-4470/35/33/307

Related papers

r-Universal reversible logic gates

Alexis De Vos, Leo Storme

Reversible logic plays a fundamental role both in ultra-low power electronics and in quantum computing. It is therefore important to know which reversible logic gates can be used as building block for the reversible implementation of an arbitrary boolean function and which cannot.

Journal of Physics A Mathematical and General•May 19, 2004•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

Reversible computing

Alexis De Vos, Yvan Van Rentergem

Reversible logic gates of a certain logic width w form a group (isomorphic to the symmetric group of order (2 w )!). Study of the subgroups of this group both teaches us a lot about properties of reversible gates and guides us to synthesize particular circuits. After design, circuits are implemented in prototype silicon chips.

ACM International Conference on Computing Frontiers (CF)•May 4, 2005•29 citations

On synthesis of 3 × 3 reversible logic functions

Ming Gu, Guowu Yang, Xiaoyu Song B +1 more

Reversible logic plays an important role in quantum computing. This article presents some novel results on synthesis of 3 × 3 reversible Boolean gates. We derive the relationship between reversible 3 × 3 gates and corresponding symmetric groups. By introducing a set of universal libraries, we show how to use group theory to synthesize any 3 × 3 reversible gate.

International Journal of Computer Mathematics•Feb 22, 2005•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

Group theoretical aspects of reversible logic gates

Leo Storme, Alexis De Vos, Gerald H. Jacobs

Logic gates with three input bits and three output bits have a privileged position within fundamental computer science: they are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. Such computers can, in principle, operate without heat production. As there exist as many as 8! = 40,320 different 3-bit reversible truth tables, the question arises as to which ones to choose as building blocks. Because these gates form a group with respect to the operation "cascading" , we can apply group theoretical tools, in order to make such a choice.

JUCS - Journal of Universal Computer Science•Jan 1, 1999•69 citations
Reversible logic plays a fundamental role both in ultra-low power electronics and in quantum computing. It is therefore important to have an insight into the structure of the group formed by the reversible logic gates and their cascading into reversible circuits. Such insight is gained from constructing chains of maximal subgroups. The subgroup of control gates plays a prominent role, as it is a Sylow 2-subgroup.
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.
Logic gates with three input bits and three output bits have a privileged position within fundamental computer science: they are a sufficient building block for constructing arbitrary reversible boolean networks and therefore are the key to reversible digital computers. Such computers can, in principle, operate without heat production. As there exist as many as 8! = 40,320 different 3-bit reversible truth tables, the question arises as to which ones to choose as building blocks. Because these gates form a group with respect to the operation "cascading" , we can apply group theoretical tools, in order to make such a choice.