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