Вентильная сложность обратимых схем как мера сложности четных подстановок

1 / 16

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ИНФОРМАТИКИ
УДК 004.312, 519.7
ВЕНТИЛЬНАЯ СЛОЖНОСТЬ ОБРАТИМЫХ СХЕМ
КАК МЕРА СЛОЖНОСТИ ЧЕТНЫХ ПОДСТАНОВОК
Д.В. Закаблуков
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
Рассмотрен вопрос сложности четных подстановок через оценку вентильной
сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT
и 2-CNOT. Доказано, что все четные подстановки на множестве Z n
2 задают-
ся обратимой схемой, не использующей дополнительные входы, с вентильной
сложностью, эквивалентной с точность до порядка n2n / log2 n; оставшиеся
четные подстановки задаются обратимой схемой, не использующей дополни-
тельные входы, с меньшей вентильной сложностью. Установлено, что любая
четная подстановка на множестве Zn
2 реализуется обратимой схемой с вен-
тильной сложностью . 2n+1 при использовании ∼ 5 ∙ 2n /n дополнительных
входов. Для всех четных подстановок применение дополнительных входов по-
зволяет снизить вентильную сложность реализующих их обратимых схем.
Ключевые слова: обратимые схемы, вентильная сложность, сложность четных
подстановок.
GATE COMPLEXITY OF REVERSIBLE CIRCUITS AS A MEASURE
OF EVEN PERMUTATION COMPLEXITY
D.V. Zakablukov
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
The article discusses even permutation complexities via the evaluation of the gate
complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates, which
implements these permutations. It is proved that almost every even permutation on
the Z n
2 set is implemented by the reversible circuit not using additional inputs with
the gate complexity equivalent up to about n2n/ log2 n ; all other even permutations
are implemented by reversible circuit not using additional inputs with the less gate
complexity. It is established that every even permutation on the Zn
2 set is implemented
by the reversible circuit using ∼ 5 ∙ 2n/n additional inputs with the gate complexity
. 2n +1. It is stated that for almost every even permutations the usage of additional
inputs allows to decrease gate complexity of reversible circuits implementing them.
Keywords: reversible circuits, gate complexity, even permutation complexity.
Введение. В дискретной математике для оценки сложности того
или иного преобразования вводится мера сложности этого преобразо-
вания. В качестве меры сложности булевой функции зачастую рассма-
тривают вентильную сложность минимальной схемы, задающей эту
функцию. Впервые это было предложено К. Шенноном в работе [1],
с которой берет свое начало теория схемной сложности. В настоящее
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 67