2 / 16
время сложность булевых функций хорошо изучена: доказаны ниж-
няя асимптотическая оценка сложности (теорема Шеннона) и верхняя
асимптотическая оценка сложности (теорема Лупанова), а также их
асимптотическое равенство
2
n
/n
для булевой функции
n
перемен-
ных [2]. В работе [3] изучен вопрос сложности булева преобразо-
вания
Z
n
2
→
Z
n
2
: доказано, что сложность такого преобразования не
превышает
O
n
2
n
n
+ log
2
n
; доказательство проводится путем явно-
го построения схемы, задающей это преобразование и состоящей из
функциональных элементов NOT, AND и XOR.
В настоящей работе рассмотрен вопрос вентильной сложности
схем, состоящих из обратимых логических вентилей NOT, CNOT и
2-CNOT. Определение обратимых вентилей NOT и
k
-CNOT, а также
обратимых схем, включающих в себя эти вентили, было изложено,
например, в работе [4]. В работах [5, 6] было доказано следующее:
•
вентили NOT, CNOT и 2-CNOT задают четную подстановку в
схеме с
n >
3
входами;
•
множество подстановок, задаваемых вентилями NOT, CNOT и
2-CNOT с
n
входами, при
n
6
3
генерирует симметрическую группу
S
(
Z
n
2
)
, а при
n >
3
— знакопеременную группу
A
(
Z
n
2
)
.
В связи с изложенным в качестве меры сложности четной подста-
новки предлагается рассматривать вентильную сложность задающей
ее минимальной обратимой схемы, состоящей из вентилей NOT, CNOT
и 2-CNOT.
В работах [5–13] предложены различные алгоритмы синтеза обра-
тимых схем и в некоторых случаях дана оценка сверху вентильной
сложности синтезированной схемы. Однако до сих пор не были из-
вестны строгие асимптотические оценки вентильной сложности обра-
тимой схемы, состоящей из вентилей NOT, CNOT и 2-CNOT и задаю-
щей какую-либо четную подстановку из группы
A
(
Z
n
2
)
.
В настоящей работе с помощью оценки числа различных неэквива-
лентных обратимых схем будет доказано, что существует такая четная
подстановка
h
∈
A
(
Z
n
2
)
, которая не может быть задана обратимой схе-
мой, состоящей из вентилей NOT, CNOT и 2-CNOT и не использую-
щей дополнительные входы с вентильной сложностью
.
n
2
n
−
1
/
log
2
n
.
Также будет доказано, что любая четная подстановка
h
∈
A
(
Z
n
2
)
мо-
жет быть задана обратимой схемой, включающей в себя вентили NOT,
CNOT и 2-CNOT и не использующей дополнительные входы с вен-
тильной сложностью
.
52
n
2
n
/
log
2
n
. Будет показано, что любая чет-
ная подстановка
h
∈
A
(
Z
n
2
)
может быть реализована обратимой схе-
мой, состоящей из вентилей NOT, CNOT и 2-CNOT и использующей
∼
5
∙
2
n
/n
дополнительных входов с вентильной сложностью
.
2
n
+1
.
Основные понятия.
Рассмотрим следующую модель обратимой
схемы: все вентили в схеме имеют одинаковое число входов, выходы
68 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1