Information Technology Reference
In-Depth Information
2
Preliminaries
2.1
Reversible Gates
The basic CNOT type reversible gates used for synthesis are the following:
(i) (1
×
1)NOT(
x
1
ₒ
x
1
)
(ii) (2
×
2) controlled NOT (CNOT) gate :(
x
1
,x
2
)
ₒ
(
x
1
,x
1
↕
x
2
)
(iii) (3
x
3
).
A generalized Toffoli gate has a set of control input
C
, a target input set
T
, and has
the form
TOF(C;T)
,where
C
= (
x
i
1
,x
i
2
, ..., x
i
k
)
T
=
×
3) To ff o li g ate (
x
1
,x
2
,x
3
)
ₒ
(
x
1
,x
2
,x
1
x
2
↕
{
x
j
}
and
C
∩
T
=
ˆ
.Itmapsan
input vector (
x
1
,x
2
, ..., x
n
) to (
x
1
,x
2
, ..., x
j−
1
,x
j
↕
(
x
i
1
.x
i
2
.....x
i
k
)
,x
j
+1
, ..., x
n
).
This is called a
k
-CNOT gate and the line
x
j
is known as the target line. Thus, a NOT
gate is
TOF
(
x
j
), a generalized Toffoli gate which has no control. The CNOT gate
TOF
(
x
i
,x
j
), also known as Feynman gate is a generalized Toffoli gate with one con-
trol bit; The simple (3
3) Toffoli gate is a generalized Toffoli gate with two controls.
Any reversible function can be realized as a cascade of
k
-CNOT gates. Fig. 1 shows the
standard graphics symbol for some common CNOT based reversible gates.
×
Fig. 1.
Different types of CNOT based reversible gates: (a) NOT gate (b) CNOT gate (c) Toffoli
gate
2.2
Quantum Cost Analysis
The quantum cost of a gate
G
is the number of elementary quantum operations required
to realize the function given by
G
. Table I shows the required quantum cost
Q
c
(
n
) in
the realization of Toffoli gate with
n
controls.
Ta b l e 1 .
Quantum cost of Toffoli gate with
n
controls
controls(
n
) 0 1 2 3 4 5 6 7 8
Quantum Cost(
Q
c
(
n
)) 1 1 5 13 29 61 125 253 509
2.3
Reversible Logic
A reversible function has equal number of inputs and outputs, and simply induces a
permutation on the set of input vectors to produce an output vector. Further, in a circuit
implementation with reversible gates, no fanout is allowed.
