Background Image
Previous Page  8 / 14 Next Page
Information
Show Menu
Previous Page 8 / 14 Next Page
Page Background

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