Group Theoretical Aspects of Reversible Logic Gates
Leo Storme
(Vakgroep zuivere wiskunde en computeralgebra,
Universiteit Gent, Belgium
Galglaan 2, B  9000 Gent
ls@cage.rug.ac.be)
Alexis De Vos
(Imec v.z.w.,
Universiteit Gent, Belgium
Sint Pietersnieuwstraat 41, B  9000 Gent
alex@elis.rug.ac.be)
Gerald Jacobs
(Vakgroep wiskundige natuurkunde en sterrenkunde,
Universiteit Gent, Belgium
Krijgslaan 281, B  9000 Gent
gerald.jacobs@rug.ac.be)
Abstract: 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 3bit 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.
Key Words: reversible computing, group theory, permutations
Category: B.6.1
1 Introduction
Conventional computers are built from basic building blocks, such as the
AND,
NAND,
OR,
NOR,
and XOR gates. See Table 1. Such tables are logically irreversible.
This means that, if we forget the value of the input (A, B), knowledge
of the output P is not sufficient to calculate backwards and to
recover the value of (A, B).
According to Landauer's principle [1] [2]
[14] [15] [18],
logic computations that are not reversible, necessarily generate heat,
i.e. kTlog(2), for every bit of information that is lost. Here k
is Boltzmann's constant and T the temperature. For T equal
room temperature, this package of heat is small, i.e. 2.9 x 10 ^{21}
joule, but nonnegligible. In order to produce zero heat, a computer is
only allowed to perform reversible computations. Such a logically reversible
computation can be `undone': the value of the output suffices to recover
what the value of the input `has been'. The hardware of such a reversible
computer cannot be constructed from the conventional gates of Table 1.
On the contrary, it consists exclusively
Page 307
Table 1: Classical truth tables: (a) AND , (b)
NAND
, (c) OR , (d) NOR , (e) XOR.
of logically reversible building blocks. The number of output bits of
a reversible logic gate necessarily equals its number of input bits. We
will call this number the `logic width' of the gate. Fredkin and Toffoli
[10] [19] have demonstrated that
three inputs and three outputs is necessary and sufficient in order to
construct a reversible implementation of an arbitrary boolean function
of a finite number of logic variables. Thus, from the fundamental point
of view, reversible logic gates with a width equal to three have a privileged
position.
The truth table of a logic gate of width w consists of 2^{w}
lines, each containing two wbit numbers: the wbit input
(A, B, C, ...) and the wbit output (P, Q, R, ...).
For convenience, all possible inputs, ranging from (0, 0, 0, ...) to (1,
1, 1, ...), are ordered arithmetically. Such a gate is reversible ifandonlyif
all 2^{w} output numbers form a permutation of the 2^{w}
input numbers. Hence, there exist exactly (2^{w} )! different
reversible gates of width w. In particular, there are 8! = 40,320
reversible gates with 3bit width.
The present paper investigates which of these 40,320 gates fulfil the
role of universal building block, and which fulfil this job more efficiently
than the others. In order to tackle the problem, we will successively study
the reversible gates with w = 1, w = 2, and w = 3.
2 Calculation with a single bit
There exist only four different truth tables with one bit input and one
bit output. Two of them are logically irreversible: the resetter (P
= 0) and the setter (P = 1). The two others are reversible: the
follower (P = A) and the inverter (P = NOT A).
If, for example, we have `forgotten' the value of A, knowledge of
the value of the inverter's output P suffices to recover it.
Note that among the 1bit reversible gates, the NOT gate is
a `generator'. This means we can make any reversible gate of width 1 by
combining a finite number of this particular gate. Indeed, a follower can
be fabricated by the sequence of two inverters. The opposite is not true:
one cannot fabricate an inverter by cascading followers.
Page 308
3 Calculation with two bits
There are 4^{4} = 256 different truth tables with two inputs (A,
B) and two outputs (P, Q). Among them, only 4! = 24 are reversible.
However, some of these twentyfour truth tables fall apart into two separate
1bit reversible tables. E.g. Table 2a decomposes into one follower Q
= A (Table 2b) and one inverter P = NOT B
(Table
2c). On the contrary, truth Table 3b is an example of a 2bit reversible
table that cannot be reduced to two separate 1bit reversible tables, and
therefore is called a true twobit reversible gate. Among the 24 reversible
2bit tables, only 16 are true 2bit tables.
Table 2: Falling apart of a truth table.
All reversible true 2bit gates can be fabricated from the same building
block, combined with an inverter before and/or an inverter after. Indeed,
Table 3b together with the inverter (Table 3a) forms a set of two building
blocks with which we can synthetize an arbitrary reversible 2bit gate.
Truth Table 3b is called the CONTROLLED NOT by Feynman [8]
[9]. Its logic operation looks like this:
where XOR is the abbreviation of the EXCLUSIVE OR function.
The gate is the reversible form of the classical (irreversible) XOR
gate. The latter is represented in Table 1e.
Figure 1 gives a representative example of a 2bit reversible gate,
realized by combining NOT and CONTROLLED NOT gates. Whereas
output Q simply equals input B,
output P can be described in three different ways:
P = NOT (A
XOR B) 
P = A XOR
(NOT B) 
P = (NOT A)
XOR B . 
Page 309
Table 3: Feynman's truth
tables: (a) NOT, (b) CONTROLLED NOT, (c) CONTROLLED CONTROLLED NOT.
These three boolean expressions are
identical, but lead to different physical realizations. We note, however,
that these implementations not only make use of the 1bit NOT function
and the 2bit CONTROLLED NOT function, but also of the 2bit exchanger,
i.e. the gate that interchanges two logic variables (realizing P = B
as well as Q = A). This is an example of a general property: the
EXCHANGER, the NOT, and the CONTROLLED NOT form a natural `generating set'
for the twentyfour 2bit reversible gates. More precisely, each reversible
2bit gate can be synthetized by taking one or zero CONTROLLED NOTs and
adding one or zero EXCHANGERs and one or zero NOTs to the left and to the
right of it. Note that neither the EXCHANGER nor the NOT is a true 2bit
gate, but the CONTROLLED NOT is one. See Table 4.
4 Calculation with
three bits
There exist 8^{8} = 16,777,216 different
truth tables with 3 inputs and 3 outputs. Among them, only 8! = 40,320
are reversible. However, 48 of these truth tables fall apart into three
separate 1bit reversible tables and another 288 fall apart into one 1bit
and one (true) 2bit reversible gate. Thus, among the 40,320 reversible
3bit gates, only 39,984 are true 3bit gates.
Two notorious examples are the Fredkin
gate [10] [19] and Feynman's
CONTROLLED
CONTROLLED NOT gate [8] [9].
The truth table of the latter is given in Table 3c. The former is shown
in Table 5a. Both have a particular property: each is a universal primitive.
This means that any boolean function of any finite number of logic input
variables can be implemented by combining a finite number of such building
blocks. The proof consists of two steps [19]: one
first proves that the building block suffices to implement the NAND
function (Table 1b), then one refers to the fact that the NAND
function is a universal primitive. The latter
Page 310
Figure 1: The synthesis of a 2bit reversible gate: (a) truth
table, (b) three different implementations combining NOTs and
CONTROLLED
NOT.
Table 4: The three generators of the 2bit
reversible gates: (a) EXCHANGER, (b) NOT, (c) CONTROLLED
NOT.
step is a wellknown theorem. The former step is demonstrated by introducing
a socalled preset: we keep one or two inputs fixed and look how the three
outputs are function of the remaining input(s). Among the 39,984 reversible
true 3bit gates, many have the universality property. It is clear, however,
that the number 39,984 is too large to allow `manual' inspection. We have
to recur to computeralgebra software specially dedicated to group theory,
such as GAP [11] [17]
and Magma [3] [12]. In
the present study, we have chosen the GAP approach, because of
GAP's
builtin commands DoubleCoset and DoubleCosets.
Page 311
Table 5: Truth tables: (a) Fredkin's conservative gate,
(b) a `pseudoinverting' gate.
5 Groups and subgroups
Because of the universality property of some of the 3bit reversible gates,
we now continue the w = 3 case in more detail.
When a reversible 3bit gate x is cascaded by a reversible 3bit
gate y (i.e. when the P output of gate x is connected
to the A input of y, etc.), then a new reversible 3bit gate
is formed, denoted xy. The 40,320 reversible truth tables of width
3 therefore form a group [16], say R, which
is isomorphic to the symmetric group S_{8} . The identity
element of the group is the 3bit follower (P = A, Q = B,
and R = C). In
GAP, each element of R is denoted
by its permutation notation. E.g. the follower is denoted (), whereas the
CONTROLLED
CONTROLLED NOT is written (7,8), because the seventh and
the eighth line of the truth table (i.e. Table 3c) are interchanged.
In order to classify the large number of elements of the group R,
we will introduce in the following paragraphs three different important
subgroups, namely E with 6 elements, F with 48 elements,
and finally G with 1,344 elements. They are ordered as
E < F < G < R
where < denotes `is proper subgroup of'. By means of each of these
three subgroups, we will partition R into double cosets, which will
serve as equivalence classes in the application of Section
6.
An important subgroup of R is formed by the follower together
with the five elements representing mere relabellings. Table 6a shows the
example e_{1}, satisfying P = A, Q
= C, and R = B, i.e. performing an exchange of B
and C. In
Page 312
permutation notation, gate e_{1} is written (2,3)(6,7).
A second example is e_{2} or (3,5)(4,6).
See Table 6b. Together these two elements generate the whole subgroup of
exchangers. The importance of this subgroup E comes from the fact
that these gates are trivial to implement in any technology. E.g. in electronics,
they consist merely of crossovers of metal lines. The subgroup E
of exchange gates contains six elements. It is denoted G_{6} (SW)
by Rayner and Newman [16] and is isomorphic to the
symmetric group S_{3} . Results from GAP show us
that E partitions the full group
R into 1,172 distinct double
cosets. A double coset of an element
g consists of all elements
e´
ge´´ , where both e´ and
e´´
are elements of the subgroup
E. This means that, although there
exist 40,320 different reversible gates, there are only 1,172 `really different'
ones, as soon as we consider exchangers as `for free'. From these 1,172
gates, all other 39,148 gates can be fabricated by merely adding one relabelling
gate to the left and one to the right.
In a next step, we can enlarge the above subgroup E, by introducing
the inverter or NOT gate. One can either invert A (i.e.
realize the gate P = NOT A, Q = B,
and R = C), or invert B (i.e. realize P = A,
Q
= NOT B , and R = C), or invert
C
(P = A, Q = B, and R = NOT C
). As an example, the cycle notation of the last gate is (1,2)(3,4)(5,6)(7,8).
These three inverters (denoted i_{1}, i_{2}
, and i_{3} ) generate a subgroup of order 2^{3}=
8,
isomorphic to Z_{2}^{3}, where Z_{2} is the cyclic group of order 2. Together, the
subgroup E of exchangers and the subgroup
I of inverters
generate a new subgroup F of order 48, isomorphic to S_{3}:Z_{2}^{3},
the semidirect product of S_{3} and Z_{2}^{3}. The elements of F are exactly the 48 gates mentioned in Section
4, i.e. the 3bit gates that fall apart into three distinct 1bit gates.
Using GAP, we find that the subgroup F partitions the
full group R into 52 distinct double cosets. This means that, although
there exist 40,320 different reversible gates, there are only 52 `really
different' ones, if we consider both exchangers and inverters as `for free'.
From these 52 gates, corresponding to representatives of the 52 distinct
double cosets of F, all other 40,268 gates can be fabricated by
merely adding one free gate to the left and one to the right. Table
7 gives a list of all 52 double cosets k_{i} . Note
that GAP gives them in a specific order, which has no a priori
meaning for the user. We also get a representative r_{i}
of class k_{i}. Again GAP's way of choosing this
representative is not transparent to the user. The different double cosets
constructed with F sometimes have different size. Table
7 gives n_{i} , i.e. the number of elements in the double
coset. At first sight, it may be a surprise that a double coset may contain
less than 48^{2 }= 2,304 members. This is caused by the fact that
different products f´gf´´ (with g
a member of R and both f´ and f´´
members of F) can lead to equal results. It is possible to prove
that each double coset contains a number of elements which is a multiple
of 48. Double coset k_{1} is the subgroup F itself,
with the follower () as representative r_{1} . We remark
that Feynman's gate (7,8) is the representative r_{4} of
class k_{4} .
If we take the elements of subgroup F and add the representative
r_{i}
of k_{i} , then these 49 elements together generate a subgroup.
Such a subgroup is called the closure of F and r_{i}
. Its order we denote by m_{i} in Table 7. From GAP,
we learn that

Sometimes m_{i} is as large as 40,320, meaning that the
closure of F and r_{i} is the full group R.
In other words, any element of R can then be written as a finite
product of form f´r_{i} f´´r_{i} f´´´
r_{i} f´´´´...,
i.e. a finite cascade of r_{i }gates
Page 313
separated by merely exchangers and/or inverters. In this case, we call
r_{i
}universal.

Sometimes m_{i} is as small as n_{i} +48,
meaning that k_{i} together with k_{1} forms
a subgroup. Any product of the form f´r_{i} f´´r_{i} f´´´r_{i} f´´´´
... then generates either an element of k_{1} or an element
of k_{i}. The only double cosets with this property are
k_{3}
and k_{31} .
In order to get more insight into the 52 double cosets in which R
is divided, we construct the lattice of all subgroups containing F
and contained in R. This yields a set of partially ordered subgroups:
Figure
2. We note ten different subgroups:

k_{1} = F

k_{1} k_{3} of order 192 = 4 x 48

k_{1} k_{31} of order 192 = 4 x 48

k_{1} k_{2} k_{3} of order
384 = 8 x 48

k_{1} k_{31} k_{40} of
order 576 = 12 x 48

k_{1} k_{8} k_{31} k_{40}
k_{49} of order 1,152 = 24 x 48

k_{1} k_{3} k_{36} k_{38}
of order 1,344 = 28 x 48

k_{1} k_{3} k_{19} k_{21}
k_{31} k_{33} k_{34}
of order 1,344 = 28 x 48

k_{1} k_{3} k_{5} k_{7}
k_{9}
k_{11}
k_{13}
k_{15}
k_{18}
k_{19}
k_{21}
k_{23}
k_{25}
k_{28}
k_{31}
k_{33}
k_{34}
k_{36}
k_{38}
k_{40}
k_{41}
k_{43}
k_{45}
k_{46}
k_{48}
k_{50}, forming the subgroup of
all even permutations and thus isomorphic to the alternating group A_{8
}of
order 20,160

the whole group R of order 40,320 itself.
Some of these subgroups have a particular interpretation. E.g. the subgroup
k_{1}
k_{8} k_{31} k_{40}
k_{49} is the closure of subgroup F and the subgroup of
the 36 conservative gates. A conservative gate [10]
is a gate where the output (P, Q, R) always has the same number
of 1's as the input (A, B, C). Fredkin's gate (2,3) is
an example. The subgroup
k_{1} k_{2}
k_{3}
is the closure of F and the subgroup of the 16 pseudoinverting
gates. We call a `pseudoinverting' gate a gate where the output (P, Q, R) always is equal to either the input (A, B, C) or to
(NOT A, NOT B, NOT C). Its
permutation notation consists merely of transpositions (i,9i).
Table 5b shows an example. The meaning of the subgroup
k_{1} k_{3}
k_{19} k_{21} k_{31}
k_{33} k_{34} will become clear below.
In a final step, we can enlarge subgroup F, by adding a Feynman
CONTROLLED
NOT. See Table 6d. The resulting G is a subgroup of R
and a supergroup of F. It is isomorphic to 2^{3}:L_{3
}(2),
the semidirect product of 2^{3}, i.e. the additive group
of all binary vectors of length 3, and L_{3}(2),
i.e. the multiplicative group of all nonsingular binary 3 x 3 matrices.
In detail, G is isomorphic to the multiplicative group of all nonsingular
binary 4 x 4 matrices of the form
with det(A) 0 and with a_{1}, a_{2}, a_{3} {0,1}. See Reference [4]. It is of order 1,344 and
divides the full group R into four double cosets: see Table
8. Double coset K_{1} is the subgroup G itself,
represented by representative R_{1} = (). It is
Page 314
Figure 2: The lattice.
identical to the subgroup k_{1} k_{3}
k_{19} k_{21} k_{31}
k_{33} k_{34} encountered above. It contains

all 48 reversible 3bit gates that fall apart into three distinct 1bit
gates,

all 288 reversible 3bit gates that fall apart into one 1bit gate and
one true 2bit gate,

another 1,008 gates, which are true 3bit gates, but can be constructed
by cascading two (or more) nontrue 3bit gates.
One can easily check that none of the 1,344 elements of G is universal
and that all 38,976 members of the three other double cosets, i.e. K_{2}
, K_{3}, and K_{4} are universal.
Page 315
Table 6: The subgroup generators: (a) EXCHANGER,
(b)
EXCHANGER, (c) NOT, (d) CONTROLLED NOT.
From top to bottom, four different representations: schematic, set of logic
equations, truth table, and permutation. Gates (a) and (b) together generate
subgroup E; Gates (a), (b), and (c) together generate subgroup F;
Gates (a), (b), (c), and (d) together generate subgroup G.
Page 316
Table 7: The double cosets k_{i}
of F in
R.
Page 317
Table 7: The double cosets k_{i}
of F in
R (continued).
6 Application
Which of R's three subgroups (E, F, or G) is
of importance, depends on the technological circumstances. In almost each
technology the exchangers are `for free'. E.g. in electronics, they are
implemented by a mere metal crossover. In the special case of dualline
electronics, each logic variable is represented by two metal lines of opposite
logic value, e.g. A together with NOT A. Therefore,
in dualrail electronics, also an inverter is `free of charge': we only
need a metal crossover to exchange A with NOT A.
In this technology, the CONTROLLED NOT is not for free. Thus we
are in the case of the free subgroup F [5] [6]
[7].
The following question arises [13]. We like to
be able to synthetize any arbitrary member of R with the help of
a limited number of generators. In electronics, we say: we like to implement
any arbitrary reversible 3bit gate with the help of a library with a limited
number of standard cells. If we denote by s_{1}, s_{2},
..., s_{m} the different members of the library, then an
arbitrary member r of R must satisfy
r = f ´s´f´´s´´f´´´...s
^{(n)}
f ^{(n+1)}, (1)
where s´, s´´, ..., s ^{(n)} are elements
of the library {s_{1}, s_{2 }, ..., s_{m}}
and
f´,
f´´, f ´´´, ..., f^{(n+1)} are
elements of
F = {f_{1}, f_{2}, ...,
f_{48}}.
The number n is called the `logic depth' of the implementation.
In order to minimize the number of standard cells, we have to choose them
from different double cosets and not from double coset k_{1}
. Thus the library will be a subset of the representatives r_{2},
r_{3},
..., r_{52}. From Table 7, it follows
that a library with a single building block is sufficient: each of the
representatives r_{4}, r_{6}, r_{10}, r_{12}, r_{14}, r_{16}, r_{17}, r_{20}, r_{22}, r_{24}, r_{26}, r_{27}, r_{29}, r_{30}, r_{
32}, r_{35}, r_{37}, r_{39}, r_{42}, r_{44}, r_{47}, r_{51} and
r_{52}
have m_{i} = 40,320 and are thus sufficient to generate
the whole group R. But, these 23 solutions are not
Page 318
equivalent. Indeed, we not only want to limit the number p of different
building blocks in the library, we also like to limit the number of times
we have to use the blocks, i.e. we like to minimize the depth n
of the products (1). It turns out that with building block r_{14}
all elements of R can be synthetized with n 4. The elements of k_{1 }need no r_{14} block
(i.e. n = 0); the elements of k_{14} need only one
r_{14}
block (i.e. n = 1); most elements of R need n = 2
or n = 3; only the elements of k_{34} need four cascaded
r_{14}
blocks (n = 4); on the average an arbitrary class of R needs
32/13 = 2.46 building blocks in cascade. Exactly the same results apply
to the building block r_{44} and to r_{47}
. Table 9 compares these three optimal choices to the
other twenty, i.e. less efficient, choices. In particular, we see in the
18 th line that Feynman's gate r_{4} needs 0 n
6 (with expectation value 97/26 = 3.73) in order to generate all R.
None of the double cosets k_{14}, k_{44}
, and k_{47} appears in the lattice of Figure
2, except at the top, in the parent group R itself. Indeed,
any element of any subgroup of Figure 2 can only generate
other elements of that particular subgroup. The underlying reason is clear:
such elements show `too much symmetry'. E.g. conservative gates (such as
Fredkin's gate) can, by cascading, only generate elements of k_{1} k_{8} k_{31} k_{40} k_{49}
, such that no finite depth n can generate the other elements of
R.
Finally, it is remarkable that the optimum double cosets k_{14},
k_{44},
and k_{47} are among the largest double cosets of Table
7: n_{14} = n_{44} = n_{47}
= 2,304.
If we consider depth n = 4 as too deep a cascade (too much silicon
surface area), we can construct a larger library. If we choose an p
= 2 library, there are four equivalent optimal combinations: r_{14}
together with r_{18}, r_{14} together with
r_{41},
r_{44}
together with r_{48} , and r_{44} together
with r_{50} . Now we have n 3, with expectation value 101/52 = 1.94. Enlarging the library to p
= 3 yields n 2 and average cascade depth 99/52 = 1.90.
Table 8: The double cosets K_{i}
of G in
R.
i 
N_{i} 
M_{i} 
R_{i} 
1 
1344 = 1344 x 1 
1344 = 1344 x 1 
() 
2 
9408 = 1344 x 7 
40320 = 1344 x 30 
(7,8) 
3 
18816 = 1344 x 14 
20160 = 1344 x 15 
(6,7,8) 
4 
10752 = 1344 x 8 
40320 = 1344 x 30 
(4,5)(6,7,8) 
7 Conclusion
The reversible gates of width w form a group, isomorphic to the symmetric
group S_{2w} . Group theory in general, and double cosets
in particular, are well
Table 9: Cascade depth n.
^{k}_{i} 
^{n}max 
^{n}ave 
^{k}_{14} 
4 
2.46 
^{k}_{44} 
4 
2.46 
^{k}_{47} 
4 
2.46 
^{k}_{22} 
4 
2.88 
^{k}_{17} 
4 
2.92 
^{k}_{39} 
4 
2.92 
^{k}_{16} 
5 
3.44 
^{k}_{6} 
5 
3.54 
^{k}_{10} 
5 
3.54 
^{k}_{20} 
5 
3.54 
^{k}_{35} 
5 
3.54 
^{k}_{24} 
5 
3.58 
^{k}_{26} 
5 
3.58 
^{k}_{29} 
5 
3.58 
^{k}_{32} 
5 
3.58 
^{k}_{37} 
5 
3.58 
^{k}_{51} 
5 
3.58 
^{k}_{4} 
6 
3.73 
^{k}_{30} 
6 
4.23 
^{k}_{52} 
6 
4.23 
^{k}_{42} 
7 
4.35 
^{k}_{27} 
7 
4.77 
^{k}_{12} 
8 
5.71 
suited to detect different classes within the (2^{w}
)! elements of the group. This can lead to an optimized choice of a set
of generators. In electronics, this means an optimal set of hardware building
blocks. With the help of GAP, we identified optimal gates g
that are able to generate all other elements of R by means of a
product of the form f´ gf´´gf´´´
... of minimal length.
Acknowledgement
Leo Storme is research associate of the Fund for Scientific Research
 Flanders (Belgium).
References
[1] Bennett, C.: "Logical reversibility of computation";
I.B.M.
Journal of Research and Development 17 (1973), 525532.
[2] Bennett, C., Landauer, R.: "The fundamental physical
limits of computation"; Scientific American 253 (July 1985),
3846.
[3] Bosma, W., Cannon, J., Playoust, C.: "The
Magma Algebra System I: the user language"; Journal of Symbolic
Computation 34 (1997), 235265.
[4] Conway, J.H., Curtis, R.T., Norton, S.P., Parker,
R.A., Wilson, R.A.: "Atlas of finite groups"; Oxford University Press,
New York (1985), p. 22.
[5] De Vos, A.: "Introduction to rMOS systems";
Proc.
4 th Workshop on Physics and Computation, Boston (1996), 9296.
[6] De Vos, A.: "Towards reversible digital computers";
Proc.
European Conference on Circuit Theory and Design, Budapest (1997),
923931.
[7] De Vos, A.: "Reversible computing"; Progress
in Quantum Electronics 23 (1999), 149.
[8] Feynman, R.: "Quantum mechanical computers";
Optics
News 11 (1985), 1120.
[9] Feynman, R.: "Feynman lectures on computation"
(A. Hey and R. Allen, eds); AddisonWesley, Reading (1996).
[10] Fredkin, E., Toffoli, T.: "Conservative logic";
International
Journal of Theoretical Physics 21 (1982), 219253.
[11] http://www.can.nl/SystemsOverview/Special/GroupTheory/GAP/index.html
[12] http://www.maths.usyd.edu.au:8000/u/magma/index.html
[13] Jacobs, G.: "Algebra der reversibele logische
schakelingen"; M.Sc. thesis, Universiteit Gent, Gent (1998).
[14] Keyes, R., Landauer, R.: "Minimal energy dissipation
in logic";
I.B.M. Journal of Research and Development 14
(1970), 153157.
[15] Landauer, R.: "Irreversibility and heat generation
in the computational process"; I.B.M. Journal of Research and Development
5 (1961), 183191.
[16] Rayner, M., Newman, D.: "On the symmetry of
logic"; Journal of Physics A: Mathematical and General 28
(1995), 56235631.
[17] Schönert, M.: "GAP"; Computer
Algebra Nederland Nieuwsbrief 9 (1992), 1928.
[18] Stix, G.: "Riding the back of electrons"; Scientific
American 279 (September 1998), 2021.
[19] Toffoli, T.: "Reversible computing"; in: "Automata,
languages and programming" (J. De Bakker and J. Van Leeuwen, eds); Springer,
New York (1980), pp. 632644.
