10 / 14
A
3
=
0 0 0
. . .
0
1 0 0
. . .
0
. . . . . . . . . . . . . . .
0 1 1
. . .
1
1 1 1
. . .
1
|
{z
}
log
2
k
0
. . .
0
0
. . .
0
. . . . . . . . .
0
. . .
0
0
. . .
0
| {z }
n
−
log
2
k
.
To do this
L
3
gates from
Ω
2
n
set are needed in total:
L
3
=
k
X
i
=2
L
(
i
)
3
6
6
(
k
−
1)(2
k
+1
+ 40 log
2
k
)
.
Now we will apply the conjugation with the permutation to permutation
g
(
K
)
3
defined by
N
i
gate for all
i >
log
2
k
. To do this
L
4
6
2(
n
−
log
2
k
)
NOT gates are required. The result is a permutation
g
(
K
)
4
and corresponding
A
4
matrix:
A
4
=
0 0 0
. . .
0
1 0 0
. . .
0
. . . . . . . . . . . . . . .
0 1 1
. . .
1
1 1 1
. . .
1
|
{z
}
log
2
k
1
. . .
1
1
. . .
1
. . . . . . . . .
1
. . .
1
1
. . .
1
| {z }
n
−
log
2
k
.
Matrix
A
was formed according to formula (8), the permutation
g
(
K
)
4
is a composition of
K
independent transpositions, therefore, it can be said
that
g
(
K
)
4
permutation can be defined by
C
{
n,n
−
1
,...,
log
2
k
+1
}
;1
gate. This gate
has
n
−
log
2
k
controlling inputs, so it can be replaced by a composition of
no more than
L
5
= 8(
n
−
log
2
k
−
3)
2-CNOT gates [5].
The given algorithm allows obtaining
g
(
K
)
4
permutation from the given
g
(
K
)
permutation by the conjugation:
g
(
K
)
4
=
g
(
K
)
g
1
◦
g
2
◦
g
3
◦
g
4
, where
g
i
is
a permutation, defined by the algorithm of
L
i
/
2
complexity using gates
from
Ω
2
n
set. As it was shown in work [7], for any
g
permutation, defined
by a composition of gates from
Ω
2
n
set, equation
g
=
g
−
1
is true. Therefore
g
(
K
)
=
g
(
K
)
4
g
−
1
4
◦
g
−
1
3
◦
g
−
1
2
◦
g
−
1
1
. So, the upper bound of
L
(
g
(
K
)
)
can be
estimated:
76 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1