6 / 14
−
2
n
log
2
n
+
n
−
n
log
2
log
2
n
log
2
n
−
n
2
n
=
−
log
2
n
;
s
=
n
2
n
+
o
(
n
2
n
)
2 log
2
n
+
o
(log
2
n
)
.
It is obvious that given the value of
s
,
log
2
(
C
(
n, s
)
/
|
A
(
Z
n
2
)
|
)
→
→ −∞
given
n
→ ∞
, i.e. the part of reversible circuits composed of
gates from
Ω
2
n
set without the use of additional inputs, with a complexity
less than
s
, tends to zero.
It is important that if the above described values of
s
and
k
, the
conditions
k
=
o
(
n
)
, k
=
o
(
s
)
are fulfilled, therefore the application of
formula (2) is correct. Then
s
∼
n
2
n
−
1
/
log
2
n
. That shows the validity of
the theorem.
I
Asymptotic upper bound
. In paper [7] the algorithm of synthesis of
reversible circuits, composed of gates NOT, CNOT and 2-CNOT, based
on the theory of permutation groups, was proposed. It was proved that the
gate complexity of the synthesized circuit satisfies the following ratio:
L
(
n
)
.
7
n
2
n
.
(3)
This algorithm is based on the representing of permutation as the
production of pairs of independent transpositions followed by the imple-
mentation of these pairs using reversible gates. Generalizing this algorithm
for the synthesis of the large number of independent transpositions, it is
possible to obtain an asymptotic upper bound of the circuit-size complexity
L
(
n
)
.
Theorem 2.
L
(
n
)
.
52
n
2
n
/
log
2
n
.
J
Let us demonstrate that
L
(
h
)
.
52
n
2
n
/
log
2
n
for all values of
h
∈
A
(
Z
n
2
)
. Any permutation
h
∈
A
(
Z
n
2
)
can be represented as a
composition of disjoint cycles so that the sum of the lengths of these
cycles does not exceed 2
n
. For the composition of two independent cycles
the following equation is true:
(
i
1
, i
2
, . . . , i
l
1
)
◦
(
j
1
, j
2
, . . . , j
l
2
) =
= (
i
1
, i
2
)
◦
(
j
1
, j
2
)
◦
(
i
1
, i
3
, . . . , i
l
1
)
◦
(
j
1
, j
3
, . . . , j
l
2
)
,
(4)
and for the cycle with the length
l
>
5
the following equation is true
(
i
1
, i
2
, . . . , i
l
) = (
i
1
, i
2
)
◦
(
i
3
, i
4
)
◦
(
i
1
, i
3
, i
5
, i
6
, . . . , i
l
)
.
(5)
We represent the permutation
h
as a composition of independent
transposition groups, with
K
transpositions in each group, and the remaining
permutation
h
0
:
h
=
◦
x
t
,
y
t
∈
Z
n
2
((x
1
,
y
1
)
◦
. . .
◦
(x
K
,
y
K
))
◦
h
0
.
(6)
72 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1