8 / 16
С учетом изложенного оценим сверху величину
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