Закаблуков Дмитрий Владимирович

В статье изучается проблема снижения вентильной сложности обратимых схем, состоящих из вентилей NOT и k-CNOT, без использования таблиц замен. Делается обобщение вентиля k-CNOT на случай нулевого значения на некоторых управляющих входах этого вентиля. Для таких обобщенных вентилей k-CNOT рассматриваются различные эквивалентные замены композиций обратимых вентилей. Приводится доказательство корректности таких замен путем сравнения результирующего преобразования до и после замены. Показано применение на практике эквивалентных замен для снижения вентильной сложности абстрактной обратимой схемы.