Эта публикация цитируется в 3 статьях

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

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

Тверской государственный университет

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

Ключевые слова: обратимые схемы, сложность схемы, глубина схемы, вычисления с памятью.

УДК: 519.714, 004.312

Статья поступила: 05.04.2017
Переработанный вариант поступил: 05.02.2020

DOI: 10.4213/dm1444

 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:1, 61–75

Реферативные базы данных:

• 
• 
• 
•