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

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