11 / 16
становку
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