ОЦЕНКА ГЛУБИНЫ ОБРАТИМЫХ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ NOT, CNOT И 2-CNOT

Рассматривается вопрос об асимптотической глубине обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT. Вводится функция Шеннона D(n,q) глубины обратимой схемы, реализующей какое-либо отображение f: Zn2 —> Zn2, как функция от п и от количества дополнительных входов схемы q. Доказывается, что при реализации отображения /, задающего четную подстановку на множестве Zn2, обратимой схемой, не использующей дополнительные входы, верно соотношение D(n,0) > 2n/(3log2n). Устанавливается также, что при использовании </о ~ 2™ дополнительных входов для реализации произвольного отображения /: Zn2 — Zn2 в обратимой схеме верно соотношение D(n,q0) < Зп.

• Закаблуков Д.В.

• Общий отдел

• Физико-математические науки