Background Image
Previous Page  11 / 16 Next Page
Information
Show Menu
Previous Page 11 / 16 Next Page
Page Background

становку

g

(

K

)

4

и соответствующую ей матрицу

A

4

:

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

 

.

Матрица

A

была сформирована согласно формуле (8), подстановка

g

(

K

)

4

представляет собой композицию

K

независимых транспозиций,

следовательно, можно утверждать: подстановка

g

(

K

)

4

задается венти-

лем

C

{

n,n

1

,...,

log

2

k

+1

}

;1

. Этот вентиль имеет

n

log

2

k

контролиру-

ющих входов, поэтому его можно заменить композицией не более

L

5

= 8(

n

log

2

k

3)

вентилей 2-CNOT [5].

Приведенный алгоритм позволяет получить из исходной подста-

новки

g

(

K

)

подстановку

g

(

K

)

4

путем действия сопряжением:

g

(

K

)

4

=

=

g

(

K

)

g

1

g

2

g

3

g

4

, где

g

i

— подстановка, задаваемая описанным ал-

горитмом со сложностью

L

i

/

2

вентилями множества

Ω

2

n

. Как было

показано в работе [7], для любой подстановки

g

, задаваемой компо-

зицией вентилей множества

Ω

2

n

, верно равенство

g

=

g

1

. Отсюда

следует

g

(

K

)

=

g

(

K

)

4

g

1

4

g

1

3

g

1

2

g

1

1

. Таким образом, можно оценить

сверху величину

L

(

g

(

K

)

)

:

L

(

g

(

K

)

)

6

5

X

i

=1

L

i

;

L

(

g

(

K

)

)

6

2

n

+ 2

k

+1

+ (

k

1)(2

k

+1

+ 40 log

2

k

)+

+2(

n

log

2

k

) + 8(

n

log

2

k

3)

.

Упрощая эту формулу, получаем

L

(

g

(

K

)

)

6

12

n

+

k

(2

k

+1

+ 40 log

2

k

)

50 log

2

k

24

. При

K

= 2

верно неравенство

L

(

g

(2)

)

6

12

n

+ 324

.

Подставляем полученные оценки в формулу (7):

L

(

h

)

.

2

n

k/

2

(12

n

+

k

(2

k

+1

+ 40 log

2

k

))) +

k

(12

n

+ 324);

L

(

h

)

.

2

n

+1

12

n

k

+ 2

k

+1

+

o

(

k

) +

O

(

kn

)

.

При

k

=

o

(

n

)

оценку для

L

(

h

)

можно упростить

L

(

h

)

.

2

n

+1

×

×

12

n

k

+ 2

k

+1

.

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 77