3 / 16
одного вентиля напрямую соединены с входами следующего за ним
вентиля. В таком случае входами обратимой схемы являются входы
первого вентиля, выходами – выходы последнего вентиля.
Базовое определение обратимых вентилей NOT и
k
-CNOT было да-
но в работе [4]. Напомним, что через
N
j
в работе [4] обозначен вентиль
NOT, инвертирующий значение на
j
-м входе; через
C
i
1
,...,i
k
;
j
=
C
I
;
j
—
вентиль
k
-CNOT (обобщенный элемент Тоффоли с
k
контролирующи-
ми входами), инвертирующий значение на
j
-м входе тогда и только то-
гда, когда значение на всех входах
i
1
, . . . , i
k
равно 1;
I
=
{
i
1
, . . . , i
k
}
—
множество контролирующих входов,
j /
∈
I
.
Любая обратимая схема c
n >
3
входами, состоящая из вентилей
NOT, CNOT и 2-CNOT, задает какую-либо четную подстановку на
множестве
Z
n
2
. При этом такая схема может
реализовывать
некоторое
булево преобразование. Для того чтобы ввести определение обрати-
мой схемы, реализующей заданное булево преобразование
Z
m
2
→
Z
m
2
,
понадобятся отображения
ϕ
n,n
+
k
:
Z
n
2
→
Z
n
+
k
2
и
ψ
π
n
+
k,n
:
Z
n
+
k
2
→
Z
n
2
вида
ϕ
n,n
+
k
(
h
x
1
, . . . , x
n
i
) =
h
x
1
, . . . , x
n
,
0
, . . . ,
0
i
;
ψ
π
n
+
k,n
(
h
x
1
, . . . , x
n
+
k
i
) =
h
x
π
(1)
, . . . , x
π
(
n
)
i
, π
∈
S
(
Z
n
+
k
)
.
Назовем
ϕ
n,n
+
k
расширяющим
отображением;
ψ
π
n
+
k,n
—
редуцирующим
отображением, подстановку
π
— перестановкой выходов.
Рассмотрим произвольную четную подстановку
h
∈
A
(
Z
n
2
)
, кото-
рая задает булево преобразование
f
h
:
Z
n
2
→
Z
n
2
. Введем определения
обратимых схем, реализующих преобразование
f
h
либо без использо-
вания дополнительных входов, либо с использованием дополнитель-
ных входов.
Определение 1.
Обратимая схема
S
g
реализует преобразование
f
h
без использования дополнительных входов (дополнительной памя-
ти), если она имеет ровно
n
входов, при этом существует такая под-
становка
π
∈
S
(
Z
n
)
, что задаваемое этой схемой булево преобразо-
вание
g
:
Z
n
2
→
Z
n
2
удовлетворяет условию
ψ
π
n,n
(
g
(x)) =
f
h
(x)
,
x
∈
Z
n
2
.
Определение 2.
Обратимая схема
S
g
реализует преобразование
f
h
c использованием
k >
0
дополнительных входов (дополнитель-
ной памяти), если она имеет
n
+
k
входов, при этом существу-
ет такая подстановка
π
∈
S
(
Z
n
+
k
)
, что задаваемое этой схемой
булево преобразование
g
:
Z
n
+
k
2
→
Z
n
+
k
2
удовлетворяет условию
ψ
π
n
+
k,n
(
g
(
ϕ
n,n
+
k
(x))) =
f
h
(x)
,
x
∈
Z
n
2
.
Отметим, что обратимая схема
S
g
задает преобразование
f
h
при
g
(x) =
f
h
(x)
.
Напомним некоторые понятия из анализа [2]. Пусть
f
(
n
)
и
g
(
n
)
—
вещественные положительные функции натуральной переменной
n
,
тогда:
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 69