ii iii
iii i

1
Transposition: A cycle of length 2 is called a trans-
position. Every cycle of length k in SN (N > 1) is ex-
pressible as a product (k 1) of transpositions in the fol-
lowing manner,


 

1211,111312
,, ,,,,,
kkk k
iiiiiiiiii ii

Since, the inverse of a permutation is the permutation
obtained by interchanging the rows between them. This
results to state that every transposition is the inverse of
its own.

1
,.,, ,
j
kjkjkjk kj
ii iiIiiiiii

A product of disjoint cycle or transpositions is com-
mutative.



,, ,,
j
kmnmn jk
iiiiii ii
An important property which will be particularly in-
teresting for this paper is that one can decompose a
transposition in the following product,



,,,,
j
ljkkljk
iiiiii ii
3. Algebra of Reversible Logic
Now we show that the algebra of reversible logic can be
introduced in terms of permutation group and the concept
of cycle works as the building block of reversible gate.
Hence, we adopt the following statements,
For every n-bit reversible logic there exist a unique
permutation of degree 2n. This means, the properties and
the operations of permutation groups are applicable for
reversible logic as well.
This statement is discussed in the beginning of the lit-
erature. Recall that as a subgroup of a symmetric group,
all the necessary group axioms are satisfied by permuta-
tion group; that is it contains the identity permutation, the
inverse permutation and the associative and closure
property. Since reversible logic mimics a permutation as
shown before, the composite operations between permu-
tations can also be adapted for reversible gates.
Since every reversible gate is expressible by corre-
sponding permutation, hence it is possible to express a
reversible gate as a product of disjoint cycles and nec-
essarily as a product of transpositions.
Let us examine the logic of an inverter which is
and 1 since it is a single bit logic, the gate
can be expressed as a permutation of degree 2 which is
010

NOT
01 0,1
10




It can be seen that the inverter is logically reversible,
but unfortunately is not a universal gate in the sense that
any arbitrary Boolean logic is not realizable in terms of
inverter alone. For quantum computation, we need uni-
versal reversible gates. One of such gates is the Taffoli-
Fredkin (T-F) gate [2,3] which is necessarily a 3-bit gate
with 3 inputs (a, b, c) and corresponding outputs (a', b',
c'). The relationship between the input and output is the
following

'
'
'
aa
bb
cc ab

Here
denotes the Exclusive OR and
denotes
the AND function. The variables a and b are control bits
where c is called the target bit. As seen from the logic,
the control bit suffers from no change while passing
through the gate. However the target bit flips if both con-
trol bits are logic 1. The permutation corresponding to
this gate is,
T-F
000001010011 100101 110111
000001010011100101 111 110



And the corresponding transposition is T-F
= (110,
111). We can also write the transposition in decimal
symbol which would be more convenient for calculation.
In case of T-F gate, the transposition is (6, 7).
The similar treatment can be accounted for more com-
plex gates. Such a gate is Peres gate [4], which is another
reversible and universal one. Peres gate is mainly inter-
esting due to its combination of T-F gate and C-NOT gate
which makes it an attractive candidate to realize complex
logic such as addition, subtraction etc. Peres gate is also a
3-bit gate which maintains relationship between the input
and output as following,
Copyright © 2012 SciRes. JQIS
S. M. BAHAUDDIN, A. A. MD. IRFAN
Copyright © 2012 SciRes. JQIS
63

'
'
'
aa
bab
cc ab

 
= (4, 6)(6, 7)(5, 6)
= (4, 6)(5, 7)(5, 7)(6, 7)(5, 7)(5, 7)(5, 6)
= (4, 6)(5, 7)(5, 6)(5, 7)(5, 6)
= (4, 6)(5, 7)(6, 7)
As seen from the logic, the outputs of bit b and c suffer
from CNOT and T-F operations respectively while bit a
remains unchanged. The permutation corresponding to
this gate is,
Now going from right to left, all we have to do is to sum
up the corresponding C-NOT gates as per transpositions.
Then the decomposition will denote Peres gate through
the joining of 3-bit C-NOT gates as shown below:
Peres
000001010011 100101 110111
000 001010 011110111101100



The corresponding cycle has a length of 4 and can be
decomposed in 3 transpositions,
In the above example, let the C-NOT of cycle (6, 7)
and (4, 6) (5, 7) are expressed as C1 and C2 respectively.
Then clearly C1, C2 are one-to-one mapping of
0,1,2,, 7S
C
onto itself and the Peres gate is merely
a composite (12
) of C1 and C2 which can mathe-
matically written by (12
)(x) = C1(C2(x)),
C
CC
x
S
.
Since this is the closure property of permutation group, it
is obvious that

Peres 100,110,101,111
100,111100,101100,110
In decimal symbol, the cycle of Peres gate is (4, 6, 5, 7)
= (4, 7)(4, 5)(4, 6).
4. Construction of General Gates 12
CC
S8.
Similarly, for n = 4, we have four options to choose
any one as a target bit and for each target bit, there exists
23 – 1 = 7 unique combinations of control bits. Hence
there are 7 × 4 = 28 numbers of C-NOT gate for n = 4
(Table 1). Again each of the 28 gates can be realized by
a unique product of transpositions as shown in Figure 2.
We showed earlier, with example, that the product of
cycles of a permutation is sufficient to realize any re-
versible logic. In an extension, let us introduce an n bit
C-NOT gate. In this case, we can realize the C-NOT op-
eration on any one bit of n while the control bits are the
other (n – 1) bits or (n – 2) and so on. If n = 3, then we can
choose any one as a target bit out of three and for each
target bit, there exist 22 – 1 = 3 unique combinations of
control bits. This means there are 9 possible C-NOT gate
for n = 3 (Figure 1), where each of them can be realized
by a unique product of transpositions.
At this juncture, let us imagine that we intend to real-
ize the logic of a full adder, which is evidently irreversi-
ble. By adding an extra bit, we can make it reversible,
which means it would be a 4-bit reversible logic. But
now the question lies where we want to put that extra bit.
Since there were 3 bits in an irreversible full adder, we
have different positions of significance (from MSB to
LSB) to put that extra bit. In our paper, we have intro-
duced 3 logics of such reversible Full Adder where the
extra bit is set at three different positions of significance
starting from LSB. The permutation corresponding to the
gates are given below. Here, in all three cases, the output
of a full adder logic is realized only when the extra bit is
zero. In addition, the least significant two bits of the
outputs are the sum and carry-out.
Now we will utilize the properties of cycles, to prove
that any reversible logic can be simulated by a combina-
tion of elementary gates. In other words, we will prove that
the decomposition of reversible logic is possible by exploit-
ing the properties of cycles under permutation algebra.
As an example, we can realize Peres gate in terms of
the 3-bit C-NOT gates
Peres
= (4, 6, 5, 7)
= (6, 5, 7, 4)
FA-1
0000000100100011 01000101011001111000 10011010 10111100 11011110 1111
00000011 0110010000100001010101111010 1011110111001001 100011111110
 
 

FA-2
00000001001000110100010101100111 10001001 10101011 11001101 11101111
00000010000100110110010101110100 1110 1101 11111100100110111000 1010
 
 

FA-3
0000000100100011010001010110011110001001 101010111100110111101111
0000001001100001 01000101001101111010 1001110110111100 1000 1110 1111
 
 

Now the corresponding cycles in decimal are, FA-3
= (1, 2, 6, 3)(8, 10, 13)
FA-1
= (1, 3, 4, 2, 6, 5)(8, 10, 13)(9, 11, 12)(14, 15) As we stated before, our intention is to decompose
these reversible adder logics by 4-bit C-NOT gates only.
= (1, 2)(4, 6, 7)(8, 14)(9, 13, 11, 12)(10, 15)
FA-2
S. M. BAHAUDDIN, A. A. MD. IRFAN
64
(6,7)(2,3)(6,7)(5,7)(4,6)(5,7)
(4,5)(6,7)
(2,6)(3,7)
(3,7)
(1,3 )(6, 7)
(1,5 )(3, 7)
Figure 1. Possible permutations and corresponding trans-
positions of 3-bit C-NOT gates.
Table 1. Transpositions of 4-bit C-NOT gates correspond-
ing to Figure 2.
Row 1 (target bit at 1st LSB) Row 3 (target bit at 3rd LSB)
No. Transpositions No. Transpositions
1 (14,15) 1 (11,15)
2 (6,7)(14,15) 2 (3,7)(11,15)
3 (10,11)(14,15) 3 (9,13)(11,15)
4 (12,13)(14,15) 4 (10,14)(11,15)
5 (8,9)(10,11)(12,13)(14,15) 5 (8,12)(9,13)(10,14)(11,15)
6 (4,5)(6,7)(12,13)(14,15) 6 (2,6)(3,7)(10,14)(11,15)
7 (2,3)(6,7)(10,11)(14,15) 7 (1,5)(3,7)(9,13)(11,15)
Row 2 (target bit at 2nd LSB) Row 4 (target bit at MSB)
No. Transpositions No. Transpositions
1 (13,15) 1 (7,15)
2 (5,7)(13,15) 2 (3,11)(7,15)
3 (9,11)(13,15) 3 (5,13)(7,15)
4 (12,14)(13,15) 4 (6,14)(7,15)
5 (8,10)(9,11)(12,14)(13,15) 5 (4,12)(5,13)(6,14)(7,15)
6 (4,6)(5,7)(12,14)(13,15) 6 (2,10)(3,11)(6,14)(7,15)
7 (1,3)(5,7)(9,11)(13,15) 7 (1,9)(3,11)(5,13)(7,15)
Figure 2. Possible permutations of 4-bit C-NOT gates.
Figure 3. Realization of full adderFA -3
expressed by 26
4-bit C-NOT gates.
Here, we will utilize the expression of different C-NOT
gates in terms of corresponding transpositions and we
will operate permutation algebra on these transpositions
according to the lemmas to obtain the logic of reversible
adder. So, let us first examine the reversible logic of φFA-3
and then decompose it into elementary transpositions
which are available for C-NOT operation in following
manner,
FA-3
= (1, 2, 6, 3)(8, 10, 13)
= (3, 1, 2, 6)(8, 10, 13)
= (3, 6)(3, 2)(3, 1)(8, 13)(8, 10)
= (3, 7)(6, 7)(3, 7)(2, 3)(1, 3)(12, 13)(8, 12)(12, 13)
(8, 10)
Now, if we give a closure look at the figures of C-
NOT gates previously sketched before with their corre-
sponding product of transpositions, we can immediately
reveal that the first transposition (3, 7) cannot be realized
alone by any C-NOT gate rather it can be construted by a
combination of (3, 7) (11, 15) and (11, 15). According to
the previous statement, we can say that both of the
transpositons (6, 7) and (12, 13) also require a combina-
tion of two C-NOT gates while each of the four transpo-
sitions (1, 3), (2, 3), (8, 10) and (8, 12) requires a combi-
nation of four distinct C-NOT gates. In summary, we have
to add a total of 26 C-NOT gates to realize the logic of
FA-3
(Figure 3).
It is now evident that we could also simulate the logic
of FA-2
(shown in Figure 4) and FA-1
(not shown) as
well. Our calculation shows that the FA-2
can be con-
structed by 40 C-NOT gates while FA-1
will be com-
prised of 53 C-NOT gates.
5. Conclusion
The decomposition of complex gate by means of the
product of transposition and corresponding n-bit C-NOT
gate gives us further opportunity to express the logic in
more elementary gates. This is because any n-bit C-NOT
gate and corresponding unitary operations can be ex-
pressed as a composition of 2 bit C-NOT and the T-F
Figure 4. Realization of full adder expressed by 40 4-bit C-NOT gates.
FA -2
Copyright © 2012 SciRes. JQIS
S. M. BAHAUDDIN, A. A. MD. IRFAN 65
[5]. Moreover, th
REFERENCES
[1] J. F. Humphre Theory,” 5th Edi-
anguages and Program-
gate e number of basic operations to7th Colloquium on Automata, L
perform all these steps showed in our examples is
mathematically efficient and unique and thus can be eas-
ily estimated. Hence we conclude that permutation alge-
bra can be employed as an inherent structure to construct
complex reversible circuit for quantum computational
networks.
ys, “A Course in Group
tion, Oxford University Press, Oxford, 1996.
[2] T. Taffoli, “Reversible Computing,” Proceedings of the
ming, Vol. 85, 1980, pp. 632-644.
doi:10.1007/3-540-10003-2_104
[3] E. Fredkin and T. Taffoli, “Conservative Logic,” Interna-
tional Journal of Theoretical Physics, Vol. 21, No. 3-4,
1982, pp. 219-253. doi:10.1007/BF01857727
[4] A. Peres, “Reversible Logic and Quantum Computers,”
Physical Review A, Vol. 32, No. 6, 1985, pp. 3266-3276.
doi:10.1103/PhysRevA.32.3266
[5] A. Barenco, C. H. Bennett, C. Cleve, D. P. DiVincenzo,
N. Margolus, P. Shor, T. Sleator, J. A. Smolin and H.
Weinfurter, “Elementary Gates for Quantum Computa-
tion,” Physical Review A, Vol. 52, No. 5, 1995, pp. 3457-
3467. doi:10.1103/PhysRevA.52.3457
Copyright © 2012 SciRes. JQIS