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

С учетом изложенного оценим сверху величину

L

(

h

)

:

L

(

h

)

6

|

M

h

|

K

L

(

g

(

K

)

) +

|

M

h

0

|

2

L

(

g

(2)

) + 2

L

(

g

(2)

);

L

(

h

)

.

2

n

K

L

(

g

(

K

)

) + 2

KL

(

g

(2)

)

,

(7)

где

g

(

i

)

— произвольная подстановка, представляющая собой произве-

дение

i

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

Для произвольной подстановки

g

(

K

)

оценим величину

L

(

g

(

K

)

)

.

Пусть

k

=

|

M

g

(

K

)

|

= 2

K

. Задание подстановки

g

(

K

)

вентилями множе-

ства

Ω

2

n

будем проводить способом, описанным в работе [7]: действием

сопряжения приведем подстановку

g

(

K

)

к подстановке определенного

вида, которая задается простым способом. Действие сопряжением не

меняет цикловой структуры подстановки, поэтому подстановка

g

(

K

)

в

результате действия сопряжением всегда будет оставаться композици-

ей

K

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

Для подстановки

g

(

K

)

= (x

1

,

y

1

)

. . .

(x

K

,

y

K

)

составим матри-

цу

A

:

A

=

 

x

1

y

1

. . .

x

K

y

K

 

=

 

a

1

,

1

. . . a

1

,n

a

2

,

1

. . . a

2

,n

∙ ∙ ∙

∙ ∙ ∙

∙ ∙ ∙

a

k

1

,

1

. . . a

k

1

,n

a

k,

1

. . . a

k,n

 

.

(8)

Наложим ограничение на значение

k

так, чтобы оно было степе-

нью двойки:

k

= 2

b

log

2

k

c

. Если

k

6

log

2

n

, то в матрице

A

найдется

не более

2

k

попарно различных столбцов. Без ограничения общности

примем, что такими столбцами являются первые

2

k

столбцов. Тогда

для любого

j

-го столбца,

j >

2

k

, найдется равный ему

i

-й столбец,

i

6

2

k

. Применив к подстановке

g

(

K

)

действие сопряжением подста-

новкой, задаваемой вентилем

C

i

;

j

, можно обнулить

j

-й столбец матри-

цы

A

(для этого потребуется два вентиля CNOT). Повторяя указанное

действие для всех столбцов с индексами больше

2

k

, получаем новую

подстановку

g

(

K

)

1

, для которой матрица

A

1

будет иметь вид

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

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

.

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