4 / 14
(defining the same even permutation), if these gates are
independent.
Conditions of independence of two
k
-CNOT gates were described in
work [4].
In the
Ω
2
n
set all the gates have no more than two controlling inputs,
therefore when
n
→ ∞
some sequential gates can be pairwise independent.
Determine the probability of the case, when
k
of such gates are pairwise
independent. Let us assume the following:
C
I
;
t
gate is independent of every
preceding gate, if there is no such
C
I
0
;
t
0
gate preceding to the concerned
one, that
t
∈
I
0
or
t
0
∈
I
. We denote by
P
i
the probability of the case, when
these conditions are met for
i
th
gate in the sequence,
P
1
= 1
. In this case,
the probability
P
(
k
)
when
k
sequential gates are pairwise independent, is
P
(
k
) =
k
Y
i
=1
P
i
.
The probability
P
i
is higher for NOT and CNOT gates for
2-CNOT gates, because they have less controlling inputs. For these
gates the probability of meeting the second condition described above
is higher. Therefore, it is possible to state without loss of generality in
P
(
k
)
calculation, that all gates are 2-CNOT.
The first gate
C
{
j
1
,l
1
}
;
t
1
can be chosen by any possible way. When
choosing the next gate
C
{
j
2
,l
2
}
;
t
2
, independently from the first one, the
values of
j
2
and
l
2
must not coincide with
t
1
: There exist (
n
−
1
2
) ways to do
this. The value of
t
2
must not be equal to
j
1
,
l
1
,
j
2
,
l
2
: There are
n
−
4
ways to choose the value of
t
2
. Similar reasoning can be done also for the
third gate
C
{
j
3
,l
3
}
;
t
3
: there are (
n
−
2
2
) ways to choose values of
j
3
and
l
3
and
n
−
6
ways to choose the value of
t
3
Therefore, probability
P
k
satisfies
the
P
k
>
(
n
−
2
k
)
n
−
k
+1
2
(
n
−
2)
n
2
or
P
k
>
(
n
−
2
k
)(
n
−
k
+ 1)(
n
−
k
)
(
n
−
2)
n
(
n
−
1)
relation.
The “
>
” sign means that in the real circuit there are more ways to choose
i
th
gate so it is independent with every preceding gate. Given
k
=
o
(
n
)
and
n
→ ∞
the probability
P
k
>
1
−
o
(1)
,
P
k
∼
1
, then also
P
(
k
)
∼
1
.
Therefore, the proportion of reversible circuits, composed of the gates from
Ω
2
n
set, with at least two dependent gates among
k
=
o
(
n
)
sequential gates,
tends to zero.
Let us prove by estimating the number of different nonequivalent
circuits that there is an even permutation
h
∈
A
(
Z
n
2
)
that can not be
defined by a reversible circuit composed of the gates from
Ω
2
n
set and
without the use of additional inputs with
.
n
2
n
−
1
/
log
2
n
gate complexity.
Let us denote the complexity of minimal reversible circuit by
L
(
h
)
,
composed of gates from
Ω
2
n
set, without the use of additional inputs and
defining
h
∈
A
(
Z
n
2
)
even permutation. Let us define the Shannon function
70 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1