8 / 14
Let us impose restrictions on the
k
value, so that it can only be a power
of two:
k
= 2
log
2
k
. If
k
6
log
2
n
, there are no more than
2
k
pairwise
distinct columns in
A
matrix. Without the loss of generality, let us assume
that such columns are the first
2
k
columns. If so, for any
j
th
column
j >
2
k
there is an equal
i
th
column,
i
6
2
k
. Effecting on permutation
g
(
K
)
with
the permutation conjugation defined by
C
i
;
j
gate, it is possible to zero the
j
th
column of
A
matrix (this requires two CNOT gates). By repeating these
steps for all the columns with indexes more than
2
k
, we will get a new
g
(
K
)
1
permutation, for which the
A
matrix will have the form
A
1
=
a
1
,
1
. . . a
1
,
2
k
a
2
,
1
. . . a
2
,
2
k
∙ ∙ ∙
∙ ∙ ∙
∙ ∙ ∙
a
k
−
1
,
1
∙ ∙ ∙
a
k
−
1
,
2
k
a
k,
1
∙ ∙ ∙
a
k,
2
k
0
∙ ∙ ∙
0
0
∙ ∙ ∙
0
∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙
0
. . .
0
0
. . .
0
| {z }
n
−
2
k
.
To obtain
A
1
matrix,
L
1
6
2
n
CNOT gates are needed.
For all
a
1
,i
= 1
we will effect on permutation
g
(
K
)
1
with the permutation
conjugation, defined by
N
i
gate. To do this,
L
2
6
2
k
+1
NOT gates are
needed. The result is a permutation
g
(
K
)
2
and corresponding
A
2
matrix:
A
2
=
0
. . .
0
b
2
,
1
∙ ∙ ∙
b
2
,
2
k
∙ ∙ ∙
∙ ∙ ∙
∙ ∙ ∙
b
k
−
1
,
1
∙ ∙ ∙
b
k
−
1
,
2
k
b
k,
1
∙ ∙ ∙
b
k,
2
k
0
∙ ∙ ∙
0
0
∙ ∙ ∙
0
∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙ ∙
0
∙ ∙ ∙
0
0
∙ ∙ ∙
0
| {z }
n
−
2
k
.
Elements of
A
2
matrix are denoted by
b
i,j
to show their distinction from
elements of
A
1
matrix.
Now we will find a number in correspondence with the vector by image
ϕ
m
:
Z
m
2
→
Z
2
m
:
ϕ
m
(
h
x
1
, . . . , x
m
i
) =
m
X
i
=1
x
i
2
i
−
1
. We will sequentially
apply a conjugation to
g
(
K
)
2
permutation, affecting all rows of
A
2
matrix,
starting with the second row. Let the current row have index
i
. This row is
pairwise different from all the rows with an index less than
i
, because all
the rows of
A
2
matrix are different. There are two options:
74 ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1