Личный кабинет
Подробное описание документа
Закаблуков Д. В.
Вентильная сложность обратимых схем как мера сложности четных подстановок / Закаблуков Д. В. - DOI 10.18698/0236-3933-2015-1-67-82 // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. - 2015. - № 1. -
Рассмотрен вопрос сложности четных подстановок через оценку вентильной сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT и 2-CNOT. Доказано, что все четные подстановки на множестве Zn2 задаются обратимой схемой, не использующей дополнительные входы, с вентильной сложностью, эквивалентной с точность до порядка n2n/ log2n; оставшиеся четные подстановки задаются обратимой схемой, не использующей дополнительные входы, с меньшей вентильной сложностью. Установлено, что любая четная подстановка на множестве Zn2 реализуется обратимой схемой с вентильной сложностью < 2n+1 при использовании ~ 5 • 2n/n дополнительных входов. Для всех четных подстановок применение дополнительных входов позволяет снизить вентильную сложность реализующих их обратимых схем.
