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

Abstract

Рассматриваются сложность и глубина обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT при ограничениях на количество используемых дополнительных входов. Изучаются функции Шеннонa сложности $L(n, q)$ и глубины $D(n,q)$ обратимой схемы, реализующей отображение $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$, при условии, что число дополнительных входов $q$ находится в диапазоне $8n < q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$. Доказываются верхние оценки $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ и $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ для указанного диапазона значений $q$. Устанавливается порядок роста $L(n,q) \asymp n2^n \mathop / \log_2 q$ для таких значений $q$, что $n^2 \lesssim q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$.