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

The decomposition of an arbitrary reversible logic circuit

Alexis De Vos, Yvan Van Rentergem, Koen De Keyser

Published Apr 19, 2006• 7 citations
Publisher

Abstract

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.

DOI
10.1088/0305-4470/39/18/017

Related papers

Implementing an arbitrary reversible logic gate

Yvan Van Rentergem, Alexis De Vos, Leo Storme

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.

Journal of Physics A Mathematical and General•Apr 6, 2005•28 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

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

From group theory to reversible computers

Alexis De Vos, Yvan Van Rentergem

Reversible logic circuits of certain logic width form a group, isomorphic to a symmetric group. Its Young Subgroups allow systematic synthesis of an arbitrary reversible circuit. We can choose either a left coset, right coset, or double coset approach. The tools are beneficial to both classical and quantum computers.

International journal of unconventional computing•Jan 1, 2006•11 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

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 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 (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 (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.
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.
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.