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

Networks for reversible logic

Alexis De Vos, Yvan Van Rentergem

Published Jan 1, 2008• 4 citations
OpenAlex

Abstract

If we like to make an arbitrary permutation of a large number (say n) objects, where n is a non-prime number (n = pq, with both p and q integer), it is advantageous to arrange the objects in a rectangular p×q matrix. Then the permutation can be performed in three steps: first one applies a permutation where all objects remain in the same row, then one applies a permutation where all objects remain in the same column, and finally one applies a second permutation where all objects remain in the same row. In telecommunication, this remarkable theorem is the basis of so-called Clos networks, where w communication wires have to be permuted, according to one of the w! possible permutations. In binary digital communication, w wires transport one of the 2w possible messages. Reversible computing consists of applying a permutation, not to the w wires but to the 2w possible messages. The Clos approach allows us to build reversible binary computers very efficiently. The approach is somewhat less efficient for multiple-valued reversible logic and, unfortunately, is not applicable at all for arbitrary quantum circuits.

Related papers

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

A Quantum Model of Computation

Phillip Kaye, Raymond Laflamme, Michele Mosca

In Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50

Oxford University Press eBooks•Nov 16, 2006•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

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

Young subgroups for reversible computers

Alexis De Vos, Yvan Van Rentergem

We consider the symmetric group $S_n$ in the special case where$n$ is composite: $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_q^p$. This leads to synthesis methods for arbitrary reversible logic circuits of logic width $w$. These circuits form a group isomorphic to $S$2w. A particularly efficient synthesis is found by choosing $p=2$ and thus $q=2$w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.

Advances in Mathematics of Communications•Jan 1, 2008•41 citations

Application of Permutation Group Theory in Reversible Logic Synthesis

Dmitry Vladimirovich Zakablukov

arXiv:1507.04309•Lecture notes in computer science•Jan 1, 2016•16 citations
If we like to make an arbitrary permutation of a large number (say n) objects, where n is a non-prime number (n = pq, with both p and q integer), it is advantageous to arrange the objects in a rectangular p×q matrix. Then the permutation can be performed in three steps: first one applies a permutation where all objects remain in the same row, then one applies a permutation where all objects remain in the same column, and finally one applies a second permutation where all objects remain in the same row. In telecommunication, this remarkable theorem is the basis of so-called Clos networks, where w communication wires have to be permuted, according to one of the w! possible permutations. In binary digital communication, w wires transport one of the 2w possible messages. Reversible computing consists of applying a permutation, not to the w wires but to the 2w possible messages. The Clos approach allows us to build reversible binary computers very efficiently. The approach is somewhat less efficient for multiple-valued reversible logic and, unfortunately, is not applicable at all for arbitrary quantum circuits.
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.
In Section 1.3, we introduced the circuit model of (classical) computation. We restricted attention to reversible circuits since they can simulate any non-reversible circuit with modest overhead. This model can be generalized to a model of quantum circuits. In the quantum circuit model, we have logical qubits carried along ‘wires’, and quantum gates that act on the qubits. A quantum gate acting on n qubits has the input qubits carried to it by n wires, and n other wires carry the output qubits away from the gate. A quantum circuit is often illustrated schematically by a circuit diagram as shown in Figure 4.1. The wires are shown as horizontal lines, and we imagine the qubits propagating along the wires from left to right in time. The gates are shown as rectangular blocks. For convenience, we will restrict attention to unitary quantum gates (which are also reversible). Recall from Section 3.5.3 that non-unitary (non-reversible) quantum operations can be simulated by unitary (reversible) quantum gates if we allow the possibility of adding an ancilla and of discarding some output qubits. A circuit diagram describing a superoperator being implemented using a unitary operator is illustrated in Figure 4.2. In the example of Figure 4.1, the 4-qubit state |ψi⟩= |0⟩⊗ |0⟩⊗ |0⟩⊗ |0⟩ enters the circuit at the left (recall we often write this state as |ψi⟩ = |0⟩|0⟩|0⟩|0⟩ or |ψi⟩ = |0000⟩.) These qubits are processed by the gates U1, U2, U3, and U4. At the output of the circuit we have the collective (possibly entangled) 4-qubit state |ψf⟩. A measurement is then made of the resulting state. The measurement will often be a simple qubit-by-qubit measurement in the computational basis, but in some cases may be a more general measurement of the joint state. A measurement of a single qubit in the computational basis is denoted on a circuit diagram by a small triangle, as shown in Figure 4.1 (there are other symbols used in the literature, but we adopt this one). The triangle symbol will be modified for cases in which there is a need to indicate different types of measurements.R50
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.
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.
We consider the symmetric group SnS_nSn​ in the special case wherennn is composite: n=pqn = pqn=pq (both ppp and qqq being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of SSS pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup SpqS_p^qSpq​, whereas the second one is an element of the dual Young subgroup SqpS_q^pSqp​. This leads to synthesis methods for arbitrary reversible logic circuits of logic width www. These circuits form a group isomorphic to $S$2w. A particularly efficient synthesis is found by choosing p=2p=2p=2 and thus q=2q=2q=2w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.