9 / 14
1. There exists
b
i,j
= 1
,
j >
log
2
k
matrix element. In this case, for
all
b
i,j
0
= 1
,
j
0
6
=
j
,
j
0
>
log
2
k
elements, we will apply the conjugation
with the permutation, defined by
C
j
;
j
0
gate. To do this, no more than
2(2
k
−
log
2
k
−
1)
CNOT gates are needed. Then, for all
j
0
6
log
2
k
we
will apply the conjugation with the permutation, defined by
C
j
;
j
0
gate, so
that
ϕ
log
2
k
(
h
b
0
i,
1
, . . . , b
0
i,
log
2
k
i
) =
i
−
1
.
(9)
To do this, no more than
2 log
2
k
CNOT gates are needed. At the
last step we apply the conjugation with the permutation, defined by gate
C
{
1
,...,
log
2
k
}
;
j
. Before and after doing this, it is possible, we will need
to invert no more than
log
2
k
values of
b
0
i,j
0
= 0
,
j
0
6
log
2
k
, using
permutations defined by NOT gates. The gate
C
{
1
,...,
log
2
k
}
;
j
has
log
2
k
controlling inputs, and so it can be changed to a set of no more than
8(log
2
k
−
3)
2-CNOT gates [5].
After doing these transformations we have a row of matrix, with all
elements of indices higher than
log
2
k
, which is equal to 0, with the first
log
2
k
elements of this row satisfying (9) condition. To do this
L
(
i
)
3
gates
from set
Ω
2
n
are needed in total:
L
(
i
)
3
6
2(2
k
−
log
2
k
−
1) + 2 log
2
k
+
+ 2(log
2
k
+ 8(log
2
k
−
3) + log
2
k
);
L
(
i
)
3
6
2
k
+1
+ 20 log
2
k.
2. There is no such an element
b
i,j
of
A
2
matrix, when
b
i,j
= 1
,
j >
log
2
k
. It is possible to say, that for all
i
0
< i
the following inequation
is true:
ϕ
log
2
k
(
h
b
i,
1
, . . . , b
i,
log
2
k
i
)
6
=
ϕ
log
2
k
(
h
b
i
0
,
1
, . . . , b
i
0
,
log
2
k
i
)
. In the
opposite case, there would be two identical rows in
A
2
matrix, which
does not comply with a cyclic type of
g
(
K
)
2
permutation. We apply the
conjugation with the permutation defined by
C
{
1
,...,
log
2
k
}
;log
2
k
+1
gate, so
that it results in
b
i,
log
2
k
+1
= 1
. Before and after doing this, we will possibly
need to invert no more than
log
2
k
values
b
i,j
0
= 0
,
j
0
6
log
2
k
using
permutations defined by NOT gates. The
C
{
1
,...,
log
2
k
}
;
j
gate has
log
2
k
controlling inputs, and so it can be changed to a set of no more than
8(log
2
k
−
3)
2-CNOT gates[5].
After this, we perform the same operations, as in the previous case.
Therefore, to reduce the
i
th
row to the same view as in previous case
(see p. 1), in total
L
(
i
)
3
gates from
Ω
2
n
set are required:
L
(
i
)
3
6
2(log
2
k
+
+ 8(log
2
k
−
3) + log
2
k
) + 2
k
+1
+ 20 log
2
k
= 2
k
+1
+ 40 log
2
k
.
As the result of all the above described operations, sequentially applied
to all rows of
A
2
matrix starting from the second one, a new permutation
g
(
K
)
3
and corresponding
A
3
matrix will be formed:
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 75