2.2. TWO IMPORTANT YOUNG SUBGROUPS OF S
2
w
27
A
2
, A
3
, …, A
w
are not changed. Submatrix U
22
tells what happens with the remaining w 1
bits if bit A
1
equals 1. e circuit is called a controlled circuit. See Figure 2.1a. We will denote
the group of matrices of the kind (2.2) by P
z
(n). It is a subgroup of the group P(n) of all n n
permutation matrices. We call A
2
; A
3
; : : : ; A
w
the controlled bits and A
1
the controlling bit.
Table 2.2: Truth table of three reversible logic circuits of width 3: (a) an arbitrary circuit,
(b) a controlled circuit, and (c) a controlled NOT gate
A
1
A
2
A
3
P
1
P
2
P
3
A
1
A
2
A
3
P
1
P
2
P
3
A
1
A
2
A
3
P
1
P
2
P
3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 1 1
1 1 0
1 0 0
0 0 0
1 0 1
0 1 0
0 0 1
0 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 1 0
1 1 1
1 0 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 0 0
0 0 1
1 1 0
1 1 1
0 0 0
1 0 1
0 1 0
0 1 1
(a) (b) (c)
U
22
U
11
U
(a) (b) (c) (d)
Figure 2.1: Schematic of four reversible logic circuits of width 5: (a) a controlled circuit: if A
1
D 1
then apply U
22
, (b) a controlled gate: if f .A
2
; A
3
; A
4
; A
5
/ D 1 then apply U , (c) a controlled
NOT gate: if f .A
2
; A
3
; A
4
; A
5
/ D 1 then apply P
1
D A
1
, and (d) another controlled circuit: if
A
1
D 0 then apply U
11
.
28 2. BOTTOM
2.2.2 CONTROLLED
NOT
GATES
We now introduce a second class of reversible logic circuits. ey are based on the Young sub-
group S
n=2
2
= S
2
w1
2
. We describe these gates, called controlled gates, by means of their relation-
ship between the w outputs P
1
; P
2
; : : : ; P
w
and the w inputs A
1
; A
2
; : : : ; A
w
. We have P
2
D A
2
,
P
3
D A
3
, …, P
w
D A
w
. e remaining output, i.e., P
1
, is controlled by means of some Boolean
function f of the w 1 inputs A
2
, A
3
, …, A
w
:
• if f .A
2
; A
3
; : : : ; A
w
/ D 0, then we have P
1
D A
1
; and
• if, however, f .A
2
; A
3
; : : : ; A
w
/ D 1, then P
1
is computed from A
1
by applying the gate U
(see Figure 2.1b).
In other words: if f D 0, then we apply the IDENTITY gate to A
1
, otherwise we apply the U gate
to A
1
. Because, according to Section 2.1, in the classical world, there exist only two possible 1-
bit gates U , that is, the IDENTITY gate and the NOT gate, and because a controlled IDENTITY
equals an uncontrolled IDENTITY, we only have to consider the case where U is the NOT. e
controlled gate then is a controlled NOT. Making use of the XOR function, we can write the rule
of the controlled NOT in the following compact way, that is, as a set of w Boolean equations:
P
1
D f .A
2
; A
3
; : : : ; A
w
/ ˚ A
1
P
2
D A
2
P
3
D A
3
: : : : : :
P
w
D A
w
:
See Figure 2.1c.
e controlled NOT gates form a group isomorphic to the group of Boolean functions of
2
w1
variables. We will denote this group of 2
w
2
w
matrices by P
x
(2
w
). It is a subgroup of
the group P(2
w
). Its order is 2
2
w1
, which is equal to the number of functions f acting on
w 1 variables (Section 1.4). We call A
2
; A
3
; : : : ; A
w
the controlling bits and A
1
the controlled
bit. We call f the control function. If this function is an AND of the input bits or their negations,
then the controlled NOT is called a TOFFOLI gate. For example, in Figure 2.2b, where w equals 5,
we have
f .A
2
; A
3
; A
4
; A
5
/ D A
2
A
3
A
5
:
us, in a TOFFOLI, the control function is a single term and thus a single product of literals. e
controlling bits which are not inverted are marked by a black bullet; the controlling bits which
are inverted are marked by a white bullet.
2
ere are 3
w1
different TOFFOLI gates controlling
2
We already encountered a TOFOLLI gate in Section 1.6. ere, however, not the first but the last bit is the controlled bit.
Bit C is controlled by the controlling bits A and B:
A
P D A
B
Q D B
C
R D AB ˚ C :
2.2. TWO IMPORTANT YOUNG SUBGROUPS OF S
2
w
29
the bit A
1
. ey form a group isomorphic to C
w1
3
, where C
3
is the cyclic group of order 3.
See Section 1.5.
(a) (b)
Figure 2.2: (a) A controlled NOT gate and (b) a TOFFOLI gate.
Another example of control gate is given by Table 2.2c, where w D 3. It has the control
function f .A
2
; A
3
/ D A
2
C A
3
. Its permutation matrix is
0
B
B
B
B
B
B
B
B
B
B
B
@
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
1
C
C
C
C
C
C
C
C
C
C
C
A
:
We can stress its membership of
S
2
S
2
S
2
S
2
by writing
0
B
B
B
B
B
B
B
B
B
B
B
@
0 1
1 0
0 1
0 1
1 0
0 1
1 0
1 0
1
C
C
C
C
C
C
C
C
C
C
C
A
; (2.3)
a matrix composed of four large S
2
blocks (here one
1 0
0 1
block and three
0 1
1 0
blocks).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.