Оценка глубины обратимых схем из функциональных элементов NOT, CNOT и 2-CNOT / Д. В. Закаблуков. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2016. № 3. С. 3-12.
Рассматривается вопрос об асимптотической глубине обратимых схем, состоящих
из функциональных элементов NOT, CNOT и 2-CNOT.
Вводится функция Шеннона D(n, q) глубины обратимой схемы, реализующей
какое-либо отображение f\colon \mathbb Z_2^n \to \mathbb Z_2^n,
как функция от n и от количества дополнительных входов схемы q.
Доказывается, что при реализации отображения f, задающего четную подстановку на множестве \mathbb Z_2^n,
обратимой схемой, не использующей дополнительные входы, верно соотношение D(n, 0) \gtrsim 2^n / (3\log_2 n).
Устанавливается также, что при использовании q_0 \sim 2^n дополнительных
входов для реализации произвольного отображения
f\colon \mathbb Z_2^n \to \mathbb Z_2^n в обратимой схеме верно соотношение D(n, q_0) \lesssim 3n.
Ключевые слова:
обратимые схемы, глубина схемы, вычисления с памятью.
