2 / 14
In view of the aforesaid, the gate complexity of the minimal reversible
circuit consisting of gates NOT, CNOT and 2-CNOT will be regarded as
the measurement of complexity of even permutation.
In works [5–13] various algorithms of synthesis of reversible circuits are
suggested, and in some cases upper bound of synthesized circuit is given.
But until now, exact asymptotic bounds of reversible circuits, composed of
gates NOT, CNOT and 2-CNOT and defining some even permutation from
A
(
Z
n
2
)
group were unknown.
In this article it will be proved by estimating the number of nonequivalent
reversible circuits, that there is an even permutation
h
∈
A
(
Z
n
2
)
that cannot
be defined by the reversible circuit composed of gates NOT, CNOT and
2-CNOT, without the use of additional inputs with
.
n
2
n
−
1
/
log
2
n
gate
complexity. Also it will be proved that any even permutation
h
∈
A
(
Z
n
2
)
can be defined by a reversible circuit composed of gates NOT, CNOT и
2-CNOT without the use of additional inputs with
.
52
n
2
n
/
log
2
n
gate
complexity. It will be shown, that every even permutation
h
∈
A
(
Z
n
2
)
can be
implemented by reversible circuit composed of NOT, CNOT and 2-CNOT
gates, using
∼
5
∙
2
n
/n
additional inputs with
.
2
n
+1
gate complexity.
Terms of reference.
Let us consider the following model of a reversible
circuit: all of the gates in the circuit have the same number of the inputs;
outputs of one gate are directly connected to the inputs of the following
gate. In this case, inputs of the first gate are inputs of the reversible circuit,
outputs of the last gate are outputs of the reversible circuit.
Basic definition of the reversible gates NOT and
k
-CNOT was given
in work [4]. Recall that NOT gate, inversing value at
j
th
input is denoted
by
N
j
in work [4]; and the gate
k
-CNOT (extended Toffoly’s element with
k
controlling inputs), inverting the value at
j
th
input then and only then,
when the value is equal to 1 at all of the inputs
i
1
, . . . , i
k
is denoted through
C
i
1
,...,i
k
;
j
=
C
I
;
j
;
i
1
, . . . , i
k
is a set of controlling inputs,
j /
∈
I
.
Any reversible circuit with
n >
3
inputs composed of gates NOT,
CNOT and 2-CNOT defines some sort of even permutation at
Z
n
2
set.
In this case, this circuit can
implement
some Boolean transformation.
To work with definition of the reversible circuit implementing given
Boolean transformation
Z
m
2
→
Z
m
2
, the
ϕ
n,n
+
k
:
Z
n
2
→
Z
n
+
k
2
and
ψ
π
n
+
k,n
:
Z
n
+
k
2
→
Z
n
2
, images of the following type will be needed
ϕ
n,n
+
k
(
h
x
1
, . . . , x
n
i
) =
h
x
1
, . . . , x
n
,
0
, . . . ,
0
i
;
ψ
π
n
+
k,n
(
h
x
1
, . . . , x
n
+
k
i
) =
h
x
π
(1)
, . . . , x
π
(
n
)
i
, π
∈
S
(
Z
n
+
k
)
.
Let us denote
ϕ
n,n
+
k
as an
extending
image;
ψ
π
n
+
k,n
as a
reducing
image;
π
permutation as the output rearrangement.
68 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1