14 / 16
В работе [3] принято, что
n
−
k
=
b
log
2
(
n
−
log
2
n
)
c
:
L
∗
(
h
)
≤
2
n
+1
n
+ 2(
n
−
log
2
(
n
−
log
2
n
)) +
(
n
+ 2)2
n
+1
n
−
log
2
n
.
2
n
+1
;
N
=
2
n
n
+ 2(
n
−
log
2
(
n
−
log
2
n
)) +
2
n
+2
n
−
log
2
n
−
4
∼
5
∙
2
n
n
.
I
Можно сделать важный вывод о зависимости вентильной сложно-
сти обратимой схемы от числа дополнительных входов на основании
теоремы 4.
Утверждение 1.
Почти для всех подстановок
h
∈
A
(
Z
n
2
)
исполь-
зование дополнительных входов позволяет снизить вентильную слож-
ность реализующих их обратимых схем.
J
Следует из теорем 3 и 4.
I
Заключение.
При решении задачи синтеза обратимой схемы, ре-
ализующей какую-либо четную подстановку, приходится искать ком-
промисс между вентильной сложностью синтезированной схемы и чи-
слом используемых дополнительных входов в схеме.
В настоящей работе были доказаны некоторые асимптотические
оценки вентильной сложности обратимых схем, состоящих из венти-
лей NOT, CNOT и 2-CNOT. Было установлено, что среди всех мини-
мальных обратимых схем, не использующих дополнительные входы,
максимальная вентильная сложность схемы эквивалентна с точностью
до порядка
n
2
n
/
log
2
n
. При этом применение
∼
5
∙
2
n
/n
дополнитель-
ных входов позволяет построить обратимую схему, реализующую за-
данную четную подстановку с вентильной сложностью
.
2
n
+1
.
Направлением дальнейших исследований является изучение зави-
симости вентильной сложности обратимых схем, состоящих из венти-
лей NOT, CNOT и 2-CNOT, от числа используемых в схеме дополни-
тельных входов.
ЛИТЕРАТУРА
1.
Shannon C.E.
The synthesis of two-terminal switching circuits // Bell System
Technical Journal. 1949. Vol. 28. No. 1. С. 59–98.
2.
Яблонский С.В.
Введение в дискретную математику. М.: Наука, 1986. 384 с.
3.
Interlando J.C.
Toward a Theory of One-way Functions via Gate Complexity of
Boolean Functions // Ph. D. Thesis, University of Notre Dame, Indiana, USA, 2006.
100 p.
4.
Feynman R.
Quantum Mechanical Computers // Optic News. 1985. Vol. 11. No. 2.
P. 11–20.
5.
Maslov D.A.
Reversible Logic Synthesis // Ph. D. Thesis, University of New
Brunswick Fredericton, N.B., Canada, 2003. 165 p.
6.
Закаблуков Д.В.
Снижение вентильной сложности обратимых схем без исполь-
зования таблиц эквивалентных замен композиций вентилей // Наука и образова-
ние: Электрон. науч.-техн. издание. 2014. № 3. DOI: 10.7463/0314.0699195 (дата
обращения: 20.04.2014).
80 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1