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 :