ВЕНТИЛЬНАЯ СЛОЖНОСТЬ ОБРАТИМЫХ СХЕМ КАК МЕРА СЛОЖНОСТИ ЧЕТНЫХ ПОДСТАНОВОК
Рассмотрен вопрос сложности четных подстановок через оценку вентильной сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT и 2-CNOT. Доказано, что все четные подстановки на множестве Zn задаются обратимой схемой, не использующей дополнительные входы, с вентильной сложностью, эквивалентной с точность до порядка n2n / log2 n; оставшиеся четные подстановки задаются обратимой схемой, не использующей дополни- тельные входы, с меньшей вентильной сложностью. Установлено, что любая четная подстановка на множестве Zn реализуется обратимой схемой с вентильной сложностью ;S 2n+1 при использовании ~ 5 ∙ 2n /n дополнительныхвходов. Для всех четных подстановок применение дополнительных входов позволяет снизить вентильную сложность реализующих их обратимых схем