13 / 16
Ω
NXA
— функционально полный базис. Известно, что для построения
указанного многополюсника потребуется не более
2
2
n
−
k
элементов
из множества
Ω
NXA
. Каждый такой элемент можно выразить через
композицию обратимых вентилей NOT, CNOT и 2-CNOT. Согласно
рисунку, для этого необходимо не более двух обратимых вентилей и
не более одного дополнительного входа. Следовательно, обратимая
подсхема, задающая описанный выше многополюсник, имеет вен-
тильную сложность
L
1
6
2
2
n
−
k
+1
и использует
N
1
= 2
2
n
−
k
−
(
n
−
k
)
дополнительных входов. Каждый выход, соответствующий одному из
дополнительных входов, представляет собой выход одной из булевых
функций
n
−
k
переменных.
Выражение функциональных элементов базиса
Ω
NXA
через композицию
обратимых вентилей NOT, CNOT и 2-CNOT
Перед вычислением всех возможных значений конъюнкций
x
a
1
1
∧
. . .
∧
x
a
k
k
сперва получим с помощью обратимых вентилей все
инверсии
ˉ
x
i
,
1
6
i
6
k
. Для этого потребуется
L
2
= 2
k
вентилей
NOT и CNOT и
N
2
=
k
дополнительных входов. Затем вычисляем
все возможные конъюнкции
x
a
1
1
∧
. . .
∧
x
a
k
k
по индукции: для одного
входа, для двух и т.д. Для этого необходимо
L
3
=
k
−
1
X
i
=1
2
i
+1
= 2
k
+1
−
4
вентилей 2-CNOT и
N
3
=
L
3
дополнительных входов.
Далее строим подсхему для вычисления преобразования
f
h
. Для ка-
ждого вектора
h
a
1
, . . . , a
k
i
потребуется
L
4
=
n
вентилей 2-CNOT для
определения конъюнкции с выходами преобразования
f
h
(
h
a
1
, . . . , a
k
,
x
k
+1
, . . . , x
n
i
)
, значения для которых берутся с выходов многополюс-
ника. Функция XOR из формулы (10) выполняется вентилем 2-CNOT,
поэтому на данном этапе потребуется
N
4
=
n
дополнительных входов.
Значения на выходах, соответствующих этим дополнительным входам,
являются выходами преобразования
f
h
.
Теперь можно оценить величину
L
∗
(
h
)
:
L
∗
(
h
)
6
L
1
+
L
2
+
L
3
+2
k
L
4
;
L
∗
(
h
)
6
2
2
n
−
k
+1
+ 2
k
+ 2
k
+1
+
n
2
k
= 2
2
n
−
k
+1
+ 2
k
+ 2
k
(
n
+ 2)
. Оце-
ним также число требуемых при данном построении дополнительных
вдохов схемы:
N
=
N
1
+
N
2
+
N
3
+
N
4
;
N
= 2
2
n
−
k
−
(
n
−
k
) +
k
+
+ 2
k
+1
−
4 +
n
= 2
2
n
−
k
+ 2
k
+ 2
k
+1
−
4
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 79