10 / 16
этого потребуется
L
(
i
)
3
вентилей множества
Ω
2
n
:
L
(
i
)
3
6
2(2
k
−
log
2
k
−
1) + 2 log
2
k
+ 2(log
2
k
+ 8(log
2
k
−
3) + log
2
k
);
L
(
i
)
3
6
2
k
+1
+ 20 log
2
k.
2. Не существует такого элемента
b
i,j
матрицы
A
2
, что
b
i,j
= 1
,
j >
log
2
k
. Тогда можно утверждать, что для всех
i
0
< i
верно неравен-
ство:
ϕ
log
2
k
(
h
b
i,
1
, . . . , b
i,
log
2
k
i
)
6
=
ϕ
log
2
k
(
h
b
i
0
,
1
, . . . , b
i
0
,
log
2
k
i
)
. В против-
ном случае нашлись бы две одинаковые строки в матрице
A
2
, что про-
тиворечит циклическому виду подстановки
g
(
K
)
2
. Применяем действие
сопряжением подстановкой, задаваемой вентилем
C
{
1
,...,
log
2
k
}
;log
2
k
+1
так, чтобы в итоге этого действия
b
i,
log
2
k
+1
= 1
. Перед этим и по-
сле этого, возможно, потребуется инвертировать не более
log
2
k
зна-
чений
b
i,j
0
= 0
,
j
0
6
log
2
k
, с помощью подстановок, задаваемых вен-
тилями NOT. Вентиль
C
{
1
,...,
log
2
k
}
;
j
имеет
log
2
k
контролирующих вхо-
дов, таким образом, он может быть заменен композицией не более
8(log
2
k
−
3)
вентилей 2-CNOT [5].
Далее выполняем те же действия, что и в предыдущем вариан-
те. Следовательно, для приведения
i
-й строки к такому же виду, что
и в предыдущем случае (см. п. 1), в сумме потребуется
L
(
i
)
3
венти-
лей множества
Ω
2
n
:
L
(
i
)
3
6
2(log
2
k
+ 8(log
2
k
−
3) + log
2
k
) + 2
k
+1
+
+ 20 log
2
k
= 2
k
+1
+ 40 log
2
k
.
В результате последовательного применения указанных действий
ко всем строкам матрицы
A
2
начиная со второй, будет получена новая
подстановка
g
(
K
)
3
и соответствующая ей матрица
A
3
:
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
.
Для этого в сумме потребуется
L
3
вентилей множества
Ω
2
n
:
L
3
=
=
k
X
i
=2
L
(
i
)
3
6
(
k
−
1)(2
k
+1
+ 40 log
2
k
)
.
Теперь для всех
i >
log
2
k
применяем к подстановке
g
(
K
)
3
дей-
ствие сопряжением подстановкой, задаваемой вентилем
N
i
. Для этого
необходимо
L
4
6
2(
n
−
log
2
k
)
вентилей NOT. Получим итоговую под-
76 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1