Оценка глубины обратимых схем из функциональных элементов NOT, CNOT и 2-CNOT

Рассматривается вопрос об асимптотической глубине обратимых схем, состоящих из функциональных элементов 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$.