7 / 16
из вентилей NOT, CNOT и 2-CNOT, основанный на теории групп под-
становок. Было доказано, что вентильная сложность синтезированной
схемы удовлетворяет соотношению
L
(
n
)
.
7
n
2
n
.
(3)
Этот алгоритм основан на представлении подстановки в виде произ-
ведения пар независимых транспозиций с последующей реализацией
этих пар с помощью обратимых вентилей. Если обобщить этот алго-
ритм для синтеза большего числа независимых транспозиций, можно
получить асимптотическую верхнюю оценку сложности
L
(
n
)
.
Теорема 2.
L
(
n
)
.
52
n
2
n
/
log
2
n
.
J
Покажем, что
L
(
h
)
.
52
n
2
n
/
log
2
n
для всех
h
∈
A
(
Z
n
2
)
. Любую
подстановку
h
∈
A
(
Z
n
2
)
можно представить в виде композиции непе-
ресекающихся циклов так, чтобы сумма длин этих циклов не превос-
ходила
2
n
. Для композиции двух независимых циклов верно равенство
(
i
1
, i
2
, . . . , i
l
1
)
◦
(
j
1
, j
2
, . . . , j
l
2
) =
= (
i
1
, i
2
)
◦
(
j
1
, j
2
)
◦
(
i
1
, i
3
, . . . , i
l
1
)
◦
(
j
1
, j
3
, . . . , j
l
2
)
,
(4)
а для цикла длиной
l
>
5
— равенство
(
i
1
, i
2
, . . . , i
l
) = (
i
1
, i
2
)
◦
(
i
3
, i
4
)
◦
(
i
1
, i
3
, i
5
, i
6
, . . . , i
l
)
.
(5)
Представим подстановку
h
в виде композиции групп независимых
транспозиций, по
K
транспозиций в каждой группе, и оставшейся
подстановки
h
0
:
h
=
◦
x
t
,
y
t
∈
Z
n
2
((x
1
,
y
1
)
◦
. . .
◦
(x
K
,
y
K
))
◦
h
0
.
(6)
Для подстановки
h
0
оценим число независимых циклов и их длину
в разложении. Согласно формулам (4) и (5), в разложении
h
0
нельзя
получить
K
независимых транспозиций, если число независимых ци-
клов строго меньше
K
и их длина строго меньше 5. Отсюда следует,
что сумма длин циклов в разложении
h
0
не превосходит
4(
K
−
1)
.
Обозначим через
M
g
множество подвижных точек произвольной
подстановки
g
∈
S
(
Z
n
2
)
:
M
g
=
{
x
∈
Z
n
2
|
g
(x)
6
= x
}
. С учетом изложен-
ного выше,
|
M
h
|
6
2
n
,
|
M
h
0
|
6
4(
K
−
1)
.
В соответствии с формулами (4)–(6), в декомпозиции подстановки
h
можно получить не более
|
M
h
|
/K
групп, в каждой из которых
K
независимых транспозиций, а в декомпозиции подстановки
h
0
— не
более
|
M
h
0
|
/
2
пар независимых транспозиций и не более одной пары
зависимых транспозиций.
Пара зависимых транспозиций
(
i, j
)
◦
(
i, k
)
выражается через
произведение двух пар независимых транспозиций:
(
i, j
)
◦
(
i, k
) =
= ((
i, j
)
◦
(
r, s
))
◦
((
r, s
)
◦
(
i, k
))
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 73