General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
Dmitry V. Zakablukov






О зависимости сложности и глубины обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT,
    от количества дополнительных входов
General Upper Bounds for Gate Complexity and Depth of Reversible Circuits 
    Consisting of NOT, CNOT and 2-CNOT Gates
    Д. В. Закаблуков[Аспирант МГТУ им. Н. Э. Баумана, кафедра <<Информационная безопасность>>, г. Москва, 
    e-mail: ]

    Dmitry V. Zakablukov[Post-graduate of Information Security Chair, BMSTU, Moscow, 
    e-mail: ]
    December 30, 2023
===========================================================================================================================================================================================================================================================================



УДК 004.312, 519.7    
   
Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-01-00196 A.


В работе рассматривается вопрос сложности и глубины обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT,
в условиях ограничения на количество используемых дополнительных входов.
Изучаются функции Шеннонa сложности L(n, q) и глубины D(n,q) обратимой схемы, реализующей отображение f_2^n →_2^n,
при условии, что количество дополнительных входов q находится в диапазоне 8n < q ≲ n2^n-o(n).
Доказываются верхние оценки L(n,q) ≲ 2^n + 8n2^n  / (log_2 (q-4n) - log_2 n - 2) и
D(n,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2)) для указанного диапазона значений q.

The paper discusses the gate complexity and the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
in the case, when the number of additional inputs is limited.
We study Shannon's gate complexity function L(n, q) and depth function D(n, q) for a reversible circuit implementing a
Boolean transformation f_2^n →_2^n with 8n < q ≲ n2^n-o(n) additional inputs.
The general upper bounds L(n,q) ≲ 2^n + 8n2^n  / (log_2 (q-4n) - log_2 n - 2) and
D(n,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2)) are proved
for this case.


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

Keywords: reversible logic, gate complexity, circuit depth, computations with memory.



§ ВВЕДЕНИЕ

Теория схемной сложности берет свое начало с работы Шеннона <cit.>, в которой было предложено в качестве меры сложности
булевой функции рассматривать сложность реализующей ее минимальной контактной схемы.

О. Б. Лупановым установлена <cit.> асимптотика сложности L(n) ∼ρ 2^n  / n
булевой функции от n переменных в произвольном конечном полном базисе элементов с произвольными положительными весами,
где ρ обозначает минимальный приведенный вес элементов базиса.
Также в работе <cit.> им были рассмотрены схемы из функциональных элементов с задержками и было доказано,
что в регулярном базисе функциональных элементов любая булева функция может быть реализована схемой,
имеющей задержку T(n) ∼τ n, где τ — минимум приведенных задержек всех элементов базиса, при сохранении
асимптотически оптимальной сложности. Однако вопрос зависимости значений функций L(n) и T(n)
от количества используемых регистров памяти в данных работах не рассматривался.

Вопрос о вычислениях с ограниченной памятью был рассмотрен Н. А. Карповой в работе <cit.>,
где доказано, что в базисе классических функциональных элементов, реализующих все  булевы функции,
асимптотическая оценка функции Шеннона сложности схемы с тремя и более регистрами памяти
зависит от значения p, но не изменяется при увеличении количества используемых регистров памяти.

В данной работе рассматриваются схемы, состоящие из обратимых функциональных элементов NOT, CNOT и 2-CNOT.
Определение таких функциональных элементов и схем было дано, например, в работах <cit.>.
Функции Шеннона сложности L(n,q) и глубины D(n,q) обратимой схемы, состоящей из элементов NOT, CNOT и 2-CNOT
и реализующей некоторое булево отображение _2^n →_2^n с использованием q дополнительных входов,
были определены в работах <cit.>.

В работе <cit.> были получены следующие оценки сложности обратимой схемы:

    L(n,0) ≍ n2^n  / log_2 n   , 
    
        L(n,q_0) ≍ 2^n  при  q_0 ∼ n 2^n-⌈ n  / ϕ(n)⌉  ,

где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
и ψ(n) — любые сколь угодно медленно растущие функции.

В работе <cit.> были получены следующие оценки глубины обратимой схемы:

    D(n,q) ⩾2^n(n-2)/3(n+q)log_2(n+q) - n/3(n+q)  , 
    
        D(n,0) ⩽n2^n+5/ψ(n)( 1 + ε(n) )   ,

где ψ(n) = log_2 n - log_2 log_2 n - log_2 ϕ(n),
ϕ(n) < n  / log_2 n — любая сколь угодно медленно растущая функция,

    ε(n) = 1/4ϕ(n) +(4 + o(1))log_2 n ·log_2 log_2 n/n  .

Для схем с дополнительными входами были получены следующие оценки глубины обратимой схемы:

    D(n,q_1) ≲ 3n  при  q_1 ∼ 2^n   ,
            
    
        D(n,q_2) ≲ 2n  при  q_2 ∼ϕ(n)2^n    ,

где ϕ(n) = o(n) — любая сколь угодно медленно растущая функция.

Таким образом, на сегодняшний день известны оценки сложности и глубины обратимой схемы только в двух крайних случаях:
когда в схеме совсем не используются дополнительные входы и когда их количество весьма велико.
В данной работе при помощи алгоритма синтеза, основанного на стандартном методе О. Б. Лупанова, доказывается,
что для любого значения q в диапазоне 8n < q ≲ n2^n-o(n) верны соотношения
L(n,q) ≲ 2^n + 8n2^n  / (log_2 (q-4n) - log_2 n - 2) и
D(n,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2)).




§ ОСНОВНЫЕ ПОНЯТИЯ


Определение обратимых функциональных элементов, в частности NOT и k-CNOT, можно найти в работах <cit.>.
Mы будем пользоваться формальным определением этих элементов из работы <cit.>.

Напомним, что через N_j^n обозначается функциональный элемент NOT (инвертор) с n входами,
задающий преобразование _2^n →_2^n вида

    f_j(⟨ x_1, …, x_n ⟩) = ⟨ x_1, …, x_j ⊕ 1, …, x_n ⟩  .

Через C_i_1,…,i_k;j^n = C_I;j^n, j ∉ I, обозначается функциональный элемент k-CNOT с n входами
(контролируемый инвертор, обобщенный элемент Тоффоли с k контролирующими входами),
задающий преобразование _2^n →_2^n вида

    f_i_1,…,i_k;j(⟨ x_1, …, x_n ⟩) =
            ⟨ x_1, …, x_j ⊕ x_i_1∧…∧ x_i_k, …, x_n ⟩  .

Будем рассматривать только функциональные элементы NOT, CNOT (1-CNOT) и 2-CNOT и обратимые схемы, состоящие из них.

Через L(), D() и Q() будем обозначать сложность обратимой схемы , ее глубину и количество дополнительных входов
соответственно.
Функции Шеннона сложности L(n,q) и глубины D(n,q) обратимой схемы, состоящей из элементов NOT, CNOT и 2-CNOT
и реализующей некоторое булево отображение _2^n →_2^n с использованием q дополнительных входов,
были определены в работах <cit.>.

Значимыми входами схемы будем называть все входы, не являющиеся дополнительными, а значимыми выходами — те выходы,
значения на которых нужны для дальнейших вычислений.



§ ЗАВИСИМОСТЬ СЛОЖНОСТИ ОБРАТИМОЙ СХЕМЫ ОТ КОЛИЧЕСТВА ДОПОЛНИТЕЛЬНЫХ ВХОДОВ


Рассмотрим обратимую схему _n на рис. <ref>,
реализующую все конъюнкции n переменных вида
x_1^a_1∧…∧ x_n^a_n, a_i ∈_2. Схема имеет n значимых входов и 2^n значимых выходов;
в нее входят подсхемы _⌈ n  / 2 ⌉ и _⌊ n  / 2 ⌋,
реализующие конъюнкции от меньшего числа переменных.
Если все 2^n конъюнкций на значимых выходах основной схемы реализовать одновременно, а не по мере необходимости,
то L(_n) ∼ 2^n и Q(_n) ∼ 2^n,
как было доказано в работе <cit.>.
С другой стороны, мы можем конструировать конъюнкции по мере необходимости по одной, а не все сразу, используя только лишь значимые выходы
подсхем _⌈ n  / 2 ⌉ и _⌊ n  / 2 ⌋ и всего один дополнительный вход,
который и будет хранить значение нужной нам конъюнкции. После того, как все необходимые операции с этим значимым выходом будут
осуществлены, мы можем его обнулить, применив те же функциональные элементы, что и для его получения, но в обратном порядке.
Таким образом, в рассматриваемом нами случае для получения каждой конъюнкции потребуется не более двух элементов 2-CNOT,
а для получения t конъюнкций (последовательно, по мере необходимости) — не более 2t элементов 2-CNOT.
Следовательно, L(_n) ≲ O(2^n  / 2) + 2t, Q(_n) ≲ O(2^n  / 2) + 1.
Такой же подход можно применить к подсхемам
_⌈ n  / 2 ⌉ и _⌊ n  / 2 ⌋, а также к подсхемам этих подсхем.

    

Если вообще не хранить промежуточных значений, а конструировать конъюнкции по мере необходимости, имея лишь входы
x_1, …, x_n, x̅_1, …, x̅_n, то для получения каждой конъюнкции x_1^a_1∧…∧ x_n^a_n,
очевидно, потребуется не более 2(n-1) элементов 2-CNOT, а дополнительных входов потребуется всего (n-1) на все конъюнкции.
К примеру, на рис. <ref> показан пример конструирования 
конъюнкции x̅_1 x̅_2 x̅_3 x_4 x_5 x̅_6 x_7 x_8 с
использованием промежуточных значений x̅_1 x̅_2, x̅_3 x_4, x_5 x̅_6
и x_7 x_8 и последующем обнулением значений на незначимых выходах.



Рассмотрим в общем случае обратимую схему _CONJ(n,q), которая реализует конъюнкции
n переменных вида x_1^a_1∧…∧ x_n^a_n, a_i ∈_2,
при условии, что для хранения промежуточных значений отведено q дополнительных входов,
а значения x̅_1, …, x̅_n уже получены ранее.
Обозначим через L_CONJ(n, q, t) сложность схемы _CONJ(n,q),
реализующей по мере необходимости t конъюнкций, не обязательно различных, причем значение t может быть любым,
в том числе больше 2^n.
Также обозначим через Q_CONJ(n, q, t) общее количество необходимых дополнительных входов для такой обратимой схемы.
Из рассуждений выше можно вывести следующие простые оценки:

    L_CONJ(n, 0, t)    ⩽ 2(n-1)t
              , 
    
        Q_CONJ(n, 0, t)     = n-1
              .

Для q_0 ∼⌈ n  / 2 ⌉ + ⌊ n  / 2 ⌋ верны соотношения

    L_CONJ(n, q_0, t) ⩽ q_0 + 2t    , 
    
        Q_CONJ(n, q_0, t) ⩽ q_0 + 1    .


Выведем зависимость значения функции L_CONJ(n, q, t) от значения q.

    Для любого значения q > 2n, q ≲ 2^n верны соотношения
    
    L_CONJ(n, q, t)    ⩽ q + 8nt/log_2 q - log_2 n - 1  , 
    
            Q_CONJ(n, q, t)    ⩽ q + n - 1
                  .



    Соотношение Q_CONJ(n, q, t) ⩽ q + n - 1 следует из соотношения (<ref>).

    

    Рассмотрим структуру искомой обратимой схемы _CONJ(n,q) на рис. <ref>:
    она разбита на K = ⌈log_2 n ⌉ уровней, нумерация ведется снизу вверх.
    На уровне номер k расположены 2^k-1 обратимых подсхем, все они имеют примерно одинаковое количество значимых входов и выходов
    и реализуют все конъюнкции от некоторого подмножества переменных x_1, …, x_n, причем подмножества для разных схем
    одного уровня не пересекаются, их объединение равно всему множеству { x_1, …, x_n }, а мощности
    данных подмножеств примерно равны.

    Для пояснения структуры схемы _CONJ рассмотрим частный ее случай для n = 7.
    Схема имеет K = 3 уровня, каждый ее уровень расписан в Таблице <ref>.
    Из данной таблицы видно, что если некоторая подсхема _k;i на уровне k имеет 2^m значимых выходов,
    то на уровне (k+1) есть ровно две подсхемы _k+1;j и _k+1;j+1, подключенные к ней,
    первая из которых имеет 2^⌊ m  / 2 ⌋ значимых выходов, а вторая —
    2^⌈ m  / 2 ⌉ значимых выходов.
    Структура подсхемы _k;i проста: она реализует конъюнкции каждого значимого выхода подсхемы _k+1;j с каждым значимым
    выходом подсхемы _k+1;j+1 (см. рис. <ref>). Следовательно, сложность такой подсхемы будет равна
    2^⌊ m  / 2 ⌋· 2^⌈ m  / 2 ⌉ = 2^m (используются только элементы 2-CNOT).
    
    
        
    

    Вернемся к общей схеме _CONJ. Нам дано q дополнительных входов для хранения промежуточных значений.
    Разумнее всего потратить их для хранения значений на выходах подсхем самых высоких уровней, поскольку видно, что чем меньше
    уровень схемы _CONJ, тем больше требуется дополнительных входов для хранения промежуточных значений.
    
    Рассмотрим случай, когда мы имеем возможность хранить все промежуточные значения.
    Обозначим через L_k количество элементов на k-м уровне схемы. К примеру, L_1 = 2^n,
    L_2 = 2^⌊ n  / 2 ⌋ + 2^⌈ n  / 2 ⌉.

    Оценим значение L_k. Поскольку
    
    ⌈n/2⌉ = ⌊n + 1/2⌋⩽n + 1/2  ,

    то
    
    L_2 ⩽ 2 ·max(2^⌊n/2⌋, 2^⌈n/2⌉) =
                2 · 2^⌈n/2⌉⩽ 2 · 2 ^ n/2 + 1/2  .

    Отсюда следует, что
    
    L_3 ⩽ 4 · 2 ^ n/4 + 1/4 + 1/2  ,  
    
            L_4 ⩽ 8 · 2 ^ n/8 + 1/8 + 1/4 + 1/2  ,  
    
            L_k ⩽ 2^k · 2 ^ n  / 2^k-1  .

    Обозначим δ_k = 2^k · 2 ^ n  / 2^k-1. Значение переменной k лежит в диапазоне
    [1, …, K], K = ⌈log_2 n ⌉, k ∈ℕ.
    Сделаем переобозначение переменной: k = K - s, тогда s = s(k) = K - k. Если k обозначает номер уровня схемы
    при нумерации от выходов ко входам (снизу вверх), то (s+1) будет означать номер уровня схемы при нумерации от входов к выходам
    (сверху вниз).
    Значение переменной s лежит в диапазоне [0, …, K - 1], s ∈ℤ_+.
    В этом случае
    
    δ_k = 2^K/2^s· 2^(2n · 2^s)  / 2^K⩽2n/2^s· 2^2^s+1 = Δ_s    .

    Следовательно, мы получили цепочку неравенств
    
    L_k ⩽δ_k ⩽Δ_s(k) = 2n/2^s· 2^2^s+1  .

    
    Выпишем первые члены ряда { Δ_s(k) }: { 8n, 16n, 128n, … }. Видно, что с ростом s значение
    Δ_s растет все быстрее. Более того, можно утверждать, что для любого s ⩾ 1 верно соотношение
    
    ∑_i=0^s-1Δ_i⩽Δ_s/2  .

    Отсюда следует, что
    
    ∑_i=0^s Δ_i⩽3Δ_s/2  , 
    ∑_i=K^K-s L_i ⩽3n/2^s· 2^2^s+1  .

    Другими словами, сумма сложностей всех подсхем на последних (s+1) уровнях (при нумерации снизу вверх) не превышает
    3n · 2^-s + 2^s+1.
    
    Вернемся снова к общей схеме _CONJ.
    Из рис. <ref> видно,
    что для конструирования по мере необходимости одного значимого выхода схемы _CONJ на первых r уровнях
    будет использовано не более (1 + 2 + 4 + … + 2^r-1)=(2^r - 1) элементов 2-CNOT.
    Столько же функциональных элементов потребуется для обнуления
    значений на незначимых выходах. Следовательно, при условии, что количество уровней, для которых подсхемы
    надо конструировать по мере необходимости, не превышает r, верно соотношение
    
    L_CONJ(n, q, t) ⩽ q + 2(2^r - 1)· t ⩽ q + t · 2^r+1  .

    Слагаемое q в данном соотношении, очевидно, следует из того факта, что для получения значения на одном выходе
    любой подсхемы _k;i требуется ровно один элемент 2-CNOT.
    Если мы можем хранить не более q промежуточных значений на выходах подсхем,
    то для их хранения потребуется не более q элементов 2-CNOT.

    Нам требуется оценить значение r. Пусть для данного по условию задачи значения q выполняется неравенство
    
    3n/2^s· 2^2^s+1⩽ q < 3n/2^s+1· 2^2^s+2

    для некоторого значения s ∈ [0, …, K - 1], s ∈ℤ_+. Тогда мы можем утверждать,
    что данного значения q достаточно для хранения значений на всех выходах подсхем на последних (s+1) уровнях
    при нумерации уровней снизу вверх (см. соотношение (<ref>)),
    а количество первых уровней, для которых подсхемы нужно конструировать по мере необходимости,
    не превышает (k-1), поскольку (s+1) = K - (k-1).
    Следовательно, r ⩽ k-1.
    Из правого неравенства соотношения (<ref>) следует, что
    
    log_2 q < log_2 3 + log_2 n - s - 1 + 2^s+2  , 
    2^K/2^k = 2^s > log_2 q - (log_2 3 + log_2 n - s - 1)/4  , 
    
            (log_2 q - (log_2 3 + log_2 n - s - 1))2^k < 4 · 2^K    , 
    
            K = ⌈log_2 n ⌉ ,   s ⩾ 0  ⇒
                2^k < 8n/log_2 q - log_2 n - 1  при q > 2n  .

    
    Поскольку r + 1 ⩽ k, то
    
    2^r+1 < 8n/log_2 q - log_2 n - 1  при q > 2n  .

    Из этого неравенства и неравенства (<ref>)
    следует оценка из утверждения Леммы
    
    L_CONJ(n, q, t) ⩽ q + 8nt/log_2 q - log_2 n - 1  .

    Ограничение q ≲ 2^n из утверждения Леммы связано с тем,
    что при значениях q ≳ 2^n не наблюдается снижение сложности обратимой схемы для рассматриваемого способа синтеза.


Отметим, что по аналогии со схемой _CONJ можно построить схему _XOR, которая для заданных входов
x_1, …, x_n реализует на своих значимых выходах значения x_1 ∧ a_1 ⊕…⊕ x_n ∧ a_n,
a_i ∈_2. Для этого просто надо каждый элемент 2-CNOT в схеме _CONJ заменить на два элемента CNOT.
Следовательно,

    L_XOR(n, q, t) ⩽ 2q + 16nt/log_2 q - log_2 n - 1  , 
    
        Q_XOR(n, q, t) ⩽ q + n - 1    .


Теперь мы можем доказать основную теорему данного раздела.

    Для любого значения q > 8n, q ≲ n 2^n-⌈ n  / ϕ(n)⌉,
    где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
    и ψ(n) — любые сколь угодно медленно растущие функции, верно соотношение
    
    L(n,q) ≲ 2^n + 8n2^n/log_2 (q-4n) - log_2 n - 2  .



    Опишем алгоритм синтеза 𝐀_𝐪,
    который является модификацией стандартного алгоритма О. Б. Лупанова и который предназначен для синтезирования обратимых схем
    в условиях ограничения на количество используемых дополнительных входов.
    
    Произвольное булево отображение f_2^n →_2^n можно представить в виде некоторых n булевых функций
    f_i_2^n →_2 от n переменных
    
    f( x) = ⟨ f_1( x), f_2( x), …, f_n( x) ⟩  .

    Каждую функцию f_i( x) можно разложить по последним (n-k) переменным:
    
    f_i( x) = ⊕_a_k+1, …, a_n ∈_2x_k+1^a_k+1∧…∧ x_n^a_n∧ f_i(⟨ x_1, …, x_k, a_k+1, …, a_n ⟩)   .


    Каждая из n2^n-k булевых функций f_i(⟨ x_1, …, x_k, a_k+1, …, a_n ⟩), 1 ⩽ i ⩽ n,
    является функцией от k переменных x_1, …, x_k, ее можно получить при помощи аналога
    СДНФ, в котором дизъюнкции заменяются на сложение по модулю два:
    
    f_i(⟨ x_1, …, x_k, a_k+1, …, a_n ⟩) = f_i,j = ⊕_σ∈_2^k 
    f_i,j(σ) = 1
                x_1^σ_1∧…∧ x_k^σ_k  .

    
    Все 2^k конъюнкций вида x_1^σ_1∧…∧ x_k^σ_k можно разделить на группы,
    в каждой из которых будет не более s конъюнкций. Обозначим через p = ⌈ 2^k  / s ⌉ количество таких групп.
    Используя конъюнкции одной группы, мы можем реализовать не более 2^s булевых функций по формуле (<ref>).
    Обозначим через G_i множество булевых функций, которые могут быть реализованы при помощи конъюнкций i-й группы,
    1 ⩽ i ⩽ p. Тогда |G_i| ⩽ 2^s.
    Следовательно, мы можем переписать формулу (<ref>) следующим образом:
    
    f_i(⟨ x_1, …, x_k, a_k+1, …, a_n ⟩) = ⊕_t=1 … p
     g_j_t∈ G_t
     1 ⩽ j_t ⩽ |G_t| g_j_t(⟨ x_1, …, x_k⟩)   .

    
    Отсюда следует, что
    
    f_i( x) = ⊕_a_k+1, …, a_n ∈_2( ⊕_t=1 … p
     g_j_t∈ G_t
     1 ⩽ j_t ⩽ |G_t|
                x_k+1^a_k+1∧…∧ x_n^a_n∧ g_j_t(⟨ x_1, …, x_k⟩) )   .


    Общая структура обратимой схемы _f, которая реализует отображение f
    и которая синтезируется алгоритмом 𝐀_𝐪,
    показана на рис. <ref>.
    
        
    
    Сперва реализуем отрицания для всех входных значений x_1, …, x_n со сложностью 2n (по элементу NOT и CNOT на каждый вход),
    задействовав n дополнительных входов.
    
    Разобьем множество значимых входов схемы x_1, …, x_n на две группы: { x_1, …, x_k }
    и { x_k+1, …, x_n }.
    Первую группу входов вместе с их отрицаниями подадим на подсхему _1 = _CONJ(k,q_1) для реализации некоторых t_1
    конъюнкций x_1^a_1∧…∧ x_k^a_k, a_i ∈_2, отведя данной подсхеме q_1 дополнительных входов
    для хранения промежуточных значений.
    Вторую группу входов вместе с их отрицаниями подадим на подсхему _2 = _CONJ(n-k,q_2) для реализации некоторых t_2
    конъюнкций x_k+1^a_k+1∧…∧ x_n^a_n, a_i ∈_2, отведя данной подсхеме q_2 дополнительных входов
    для хранения промежуточных значений.
    
    Будем реализовывать все 2^k различных конъюнкций на значимых выходах подсхемы _1 последовательно.
    Полученные значения будем хранить, используя дополнительные входы.
    Как только будут получены очередные s конъюнкций, соответствующие им s значимых выходов
    подаем на значимые входы подсхемы _3;i = _XOR(s,q_3) для получения значений некоторых t_3 функций от переменных
    x_1, …, x_k, отведя данной подсхеме q_3 дополнительных входов для хранения промежуточных значений.
    Всего будет не более p = ⌈ 2^k  / s ⌉ различных подсхем _3;i.
    Как только работа с очередной подсхемой _3;i будет закончена, значение на q_3 незначимых выходах обнуляем,
    применяя те же самые функциональные элементы, что и для получения подсхемы, но в обратном порядке.
    Затем обнуляем значения на s значимых выходах,
    служивших значимыми входами подсхеме _3;i, реализуя еще раз полученные ранее s конъюнкций при помощи подсхемы _1
    (см. рис. <ref>).
    Тем самым мы сможем не увеличивать количество используемых дополнительных входов, а использовать одни и те же дополнительные входы,
    увеличивая однако при этом сложность соответствующих подсхем в два раза.
    
    Из формулы (<ref>) следует,
    что имея значения некоторого значимого выхода подсхемы _2 и некоторого значимого выхода подсхемы _3;i,
    мы можем реализовать одно слагаемое во внутренней скобке, используя ровно один элемент 2-CNOT, контролируемый выход которого
    будет одним из n значимых выходов нашей конструируемой схемы _f
    (см. рис. <ref>).
    Рассматриваемое нами отображение f имеет n выходов, количество групп конъюнкций от первых k переменных x_1, …, x_k
    равно p, количество различных конъюнкций от последних (n-k) переменных x_k+1, …, x_n равно 2^n-k.
    Следовательно, схемная сложность реализации функции f_i по формуле (<ref>)
    равна p2^n-k, а отображения f в целом равна L_4 = pn2^n-k, при этом потребуется ровно n
    дополнительных входов для хранения выходных значений отображения f.
    
    Таким образом, мы можем вывести неравенство для L(f,q) следующего вида:
    
    L(f,q) = 2n + L_CONJ(k, q_1, t_1) + L_CONJ(n-k, q_2, t_2) + 
    
                + 2p · L_XOR(s, q_3, t_3) + pn2^n-k  ,

    и для Q(_f) следующего вида:
    
    Q(_f) = q = n + Q_CONJ(k, q_1, t_1) + 
    
                + Q_CONJ(n-k, q_2, t_2) + Q_XOR(s, q_3, t_3) + n    .

    
    Отметим, что каждая из 2^k различных конъюнкций на значимых выходах подсхемы _1 будет получена ровно два раза,
    следовательно, t_1 = 2^k+1.
    
    Поскольку каждый значимый выход подсхемы _2 используется в качестве входа для pn элементов 2-CNOT,
    а значимый выход подсхемы _3;i может использоваться в качестве входа для 2^n-k элементов 2-CNOT,
    возникает два различных способа конструирования нашей искомой схемы _f:
    
        
  * 
            В первом случае мы минимизируем значение t_2: для каждой группы конъюнкций от первых k переменных x_1, …, x_k
            мы один раз конструируем очередной значимый выход подсхемы _2, а затем конструируем для него
            n значимых выходов подсхемы _3;i. Тогда можно утверждать, что t_2 = p2^n-k, t_3 ⩽ n2^n-k.
        
  * Во втором случае мы минимизируем значение t_3: для каждой группы конъюнкций от первых k переменных x_1, …, x_k
            мы один раз конструируем очередной значимый выход подсхемы _3;i, а затем конструируем для него нужные значимые выходы
            подсхемы _2. Таких выходов может быть один, а может быть и 2^n-k. Однако мы точно можем утверждать,
            что t_2 ⩽ pn2^n-k, t_3 ⩽ 2^s.
    
    
    Оценим в общем случае значение L(f,q):
    
    L(f,q) ⩽ 2n + pn2^n-k + q_1 + q_2 + 4p q_3 +
                 8k2^k+1/log_2 q_1 - log_2 k - 1 + 
    
                    + 8(n-k)t_2/log_2 q_2 - log_2 (n-k) - 1
                    + 32pst_3/log_2 q_3 - log_2 s - 1  .

    
    Будем искать такие значения k и s, что p = ⌈ 2^k  / s ⌉∼ 2^k  / s. Тогда
    
    L(f,q) ≲ 2n + n2^n/s + q_1 + q_2 + 4q_3 2^k/s +
                 8k2^k+1/log_2 q_1 - log_2 k - 1 + 
    
                    + 8(n-k)t_2/log_2 q_2 - log_2 (n-k) - 1
                    + 32t_3 2^k/log_2 q_3 - log_2 s - 1  .

   
    
        
  * Пусть t_2 = p2^n-k∼ 2^n  / s, t_3 ⩽ n2^n-k. В этом случае 
            
    L(f,q) ≲ 2n + n2^n/s + q_1 + q_2 + 4q_3 2^k/s +
                         8k2^k+1/log_2 q_1 - log_2 k - 1 + 
    
                            + 8 · 2^n/log_2 q_2 - log_2 (n-k) - 1
                            + 32n2^n/log_2 q_3 - log_2 s - 1  .

            Положим s = n - k, k = ⌈ n  / ϕ(n) ⌉,
            где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
            и ψ(n) — любые сколь угодно медленно растущие функции.
            В этом случае будет верно неравенство 2^k  / s ⩾ψ(n).

            Поскольку q_3 ≲ 2^s и q_2 < q ≲ n 2^n-⌈ n  / ϕ(n)⌉,
            то q_2 = o(2^n) и верно соотношение
            
    2n + n2^n/s + q_2 + 4q_3 2^k/s≲ 2n + n2^n/n - o(n) + q_2 + 2^n+2/n-o(n)≲ 2^n    .


            Положим q_1 = 0, q_2 = q_3.    
            Согласно формуле (<ref>), L_CONJ(n, 0, t) ⩽ 2(n-1)t,
            следовательно, мы можем заменить в соотношении (<ref>)
            сложность подсхемы _1 на k2^k+2:
            
    L(f,q) ≲ 2^n + k2^k+2 + 8 · 2^n/log_2 q_2 - log_2 (n-k) - 1
                        + 32n2^n/log_2 q_3 - log_2 s - 1  .

            Очевидно, что k2^k+2 = 4⌈ n  / ϕ(n) ⌉· 2^⌈ n  / ϕ(n) ⌉ = o(2^n)
            и 8 · 2^n  / (log_2 q_3 - log_2 s - 1) = o (32n2^n  / (log_2 q_3 - log_2 s - 1) ),
            поэтому верно соотношение 
            
    L(f,q) ≲ 2^n + 32n2^n/log_2 q_3 - log_2 s - 1  .


            Согласно Лемме <ref>, Q_CONJ(n, q, t) ⩽ q + n - 1,
            поэтому соотношение (<ref>) можо переписать в виде
            
    q ⩽ n + k - 1 + q_2 + n - k -1 + q_3 + s - 1 + n = 4n - k + 2q_3 - 3 < 4n + 2q_3    .

            Следовательно, log_2 q_3 > log_2 (q - 4n) - 1. Отсюда получаем соотношение
            
    L(f,q) ≲ 2^n + 32n2^n/log_2 (q - 4n) - log_2 n - 2  ,

            которое верно при log_2 (q - 4n) > log_2 n + 2 ⇒ q > 8n.
            

        
  * Пусть t_2 ⩽ pn2^n-k∼ n2^n  / s, t_3 ⩽ 2^s. В этом случае 
            
    L(f,q) ≲ 2n + n2^n/s + q_1 + q_2 + 4q_3 2^k/s +
                         8k2^k+1/log_2 q_1 - log_2 k - 1 + 
    
                            + 8n2^n/log_2 q_2 - log_2 (n-k) - 1
                            + 32 · 2^n/log_2 q_3 - log_2 s - 1  .

            
            Как и в первом способе, положим s = n - k, k = ⌈ n  / ϕ(n) ⌉,
            где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
            и ψ(n) — любые сколь угодно медленно растущие функции;
            q_1 = 0, q_2 = q_3.
            Тогда из рассуждений, приведенных при описании первого способа, следует соотношение
            
    L(f,q) ≲ 2^n + 8n2^n/log_2 q_2 - log_2 (n-k) - 1
                            + 32 · 2^n/log_2 q_3 - log_2 s - 1  .


            Очевидно, что
            32 · 2^n  / (log_2 q_2 - log_2 (n-k) - 1) = o (8n2^n  / (log_2 q_2 - log_2 (n-k) - 1) ),
            поэтому верно соотношение 
            
    L(f,q) ≲ 2^n + 8n2^n/log_2 q_2 - log_2 (n-k) - 1  .

            
            Поскольку log_2 q_3 > log_2 (q - 4n) - 1, то и log_2 q_2 > log_2(q - 4n) - 1.
            Отсюда получаем соотношение
            
    L(f,q) ≲ 2^n + 8n2^n/log_2 (q - 4n) - log_2 n - 2  ,

            которое верно при log_2 (q - 4n) > log_2 n + 2 ⇒ q > 8n.

            Видно, что второй способ синтеза асимптотически лучше первого.
            

    Поскольку мы описали алгоритм синтеза обратимой схемы для произвольного отображения f, то
    
    L(n,q) ⩽ L(f,q) ≲ 2^n + 8n2^n/log_2 (q-4n) - log_2 n - 2

    при q > 8n.
    При значениях q ≳ n 2^n-⌈ n  / ϕ(n)⌉
    не наблюдается снижение сложности обратимой схемы для рассматриваемого способа синтеза.




§ ЗАВИСИМОСТЬ ГЛУБИНЫ ОБРАТИМОЙ СХЕМЫ ОТ КОЛИЧЕСТВА ДОПОЛНИТЕЛЬНЫХ ВХОДОВ


Из доказательства Теоремы <ref> также можно получить верхнюю оценку для функции D(n,q)
в случае q > 8n, q ≲ n 2^n-o(n), но для этого необходимо сперва доказать вспомогательную лемму.


    Для любого значения q > 2n, q ≲ 2^n верны соотношения
    
    D_CONJ(n, q, t)    ⩽ q + 2t(2+log_2 n - log_2 (log_2 q - log_2 n - 1))   . 
    
            D_CONJ(n, 0, t)    ⩽ 2t ·⌈log_2 n ⌉  .



    Рассмотрим схему _CONJ(n,q) из Леммы <ref>.
    Согласно формуле (<ref>), верно неравенство
    L_CONJ(n, q, t) ⩽ q + 2t · 2^r. Промежуточные значения, хранимые на q дополнительных входах,
    можно получить с глубиной не более q.
    Также очевидно, что сконструировать по мере необходимости один значимый выход схемы _CONJ на первых r уровнях
    можно с глубиной r, см. рис. <ref>.
    Отсюда следует, что
    
    D_CONJ(n, q, t) ⩽ q + 2tr    .


    Согласно формуле (<ref>), при q > 2n верно неравенство
    
    2^r < 4n/log_2 q - log_2 n - 1  ,

    откуда следует, что
    
    r < 2 + log_2 n - log_2 (log_2 q - log_n - 1)    , 
    
            D_CONJ(n, q, t) ⩽ q + 2t(2+log_2 n - log_2 (log_2 q - log_2 n - 1))   .

    
    Соотношение D_CONJ(n, 0, t) ⩽ 2t ·⌈log_2 n ⌉ следует из соотношения (<ref>)
    и того факта, что сконструировать одну конъюнкцию x_1^a_1∧…∧ x_n^a_n можно с логарифмической глубиной
    ⌈log_2 n ⌉.


Аналогично, для обратимой схемы _XOR(n,q) верно неравенство

    D_XOR(n, q, t) = 2D_CONJ(n, q, t) ⩽ 2q + 4t(2+log_2 n - log_2 (log_2 q - log_2 n - 1))

для любого значения q > 2n, q ≲ 2^n.

Итак, докажем последнюю теорему данной работы.

    Для любого значения q > 8n, q ≲ n 2^n-⌈ n  / ϕ(n)⌉,
    где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
    и ψ(n) — любые сколь угодно медленно растущие функции, верно соотношение
    
    D(n,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2))    .



    Рассмотрим обратимую схему _f из доказательства Теоремы <ref>,
    синтезированную алгоритмом 𝐀_𝐪.
    Из соотношения (<ref>) можно вывести аналогичное соотношение для глубины D(f,q) вида
    
    D(f,q) = 2 + D_CONJ(k, q_1, t_1) + D_CONJ(n-k, q_2, t_2) + 
    
                + 2p · D_XOR(s, q_3, t_3) + pn2^n-k  .


    Положим s = n - k, k = ⌈ n  / ϕ(n) ⌉, где ϕ(n) ⩽ n  / (log_2 n + log_2 ψ(n))
    и ψ(n) — любые сколь угодно медленно растущие функции.
    В этом случае будут верны соотношения p ∼ 2^k  / s ⩾ψ(n)
    и pn2^n-k∼ n2^n  / s ∼ 2^n.
    
    Положим q_1 = 0. Поскольку t_1 = 2^k+1, то
    
    D_CONJ(k, q_1, t_1) ⩽ 2t_1 ·⌈log_2 k ⌉⩽⌈log_2 ⌈ n  / ϕ(n)⌉⌉· 2^⌈ n  / ϕ(n) ⌉ + 2 = o(2^n)    .

    Таким образом, верно соотношение
    
    D(f,q) ≲ 2^n + D_CONJ(n-k, q_2, t_2) + 2^k+1/s· D_XOR(s, q_3, t_3)    .

   
    Рассмотрим те же два случая для t_2 и t_3, что и на с. item_first_case_for_theorem_L_n_q_bound_for_arbitrary_q.
    
        
  * Пусть t_2 = p2^n-k∼ 2^n  / s, t_3 ⩽ n2^n-k.
            В этом случае
            
    D_CONJ(n-k, q_2, t_2) ⩽ q_2 + 2^n+1/s(2+log_2 s - log_2 (log_2 q_2 - log_2 s - 1))    , 
    
                    D_XOR(s, q_3, t_3) ⩽ 2 q_3 + n2^n-k+2(2+log_2 s - log_2 (log_2 q_3 - log_2 s - 1))    .

            
            Положим q_2 = q_3. Обозначим d = 2+log_2 s - log_2 (log_2 q_2 - log_2 s - 1), тогда
            
    D(f,q) ≲ 2^n + q_2 + d2^n+1/s +
                        q_3 2^k+2/s + dn2^n+3/s  .

            
            Согласно формуле (<ref>),
            верно соотношение
            
    2^n + q_2 + 4q_3 2^k/s≲ 2^n    .

            Отсюда получаем, что
            
    D(f,q) ≲ 2^n + dn2^n+3/s≲
                        2^n + 2^n+3(2+log_2 n - log_2 (log_2 q_3 - log_2 n - 1))    .


            Из соотношения (<ref>) следует, что
            log_2 q_3 > log_2 (q - 4n) - 1. Таким образом, получаем итоговую оценку сверху вида
            
    D(f,q) ≲ 2^n(17 + 8(log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2)))    ,

            которая верна при log_2 (q - 4n) > log_2 n + 2 ⇒ q > 8n.
            

        
  * Пусть t_2 ⩽ pn2^n-k∼ n2^n  / s, t_3 ⩽ 2^s. В этом случае
            
    D_CONJ(n-k, q_2, t_2) ⩽ q_2 + n2^n+1/s(2+log_2 s - log_2 (log_2 q_2 - log_2 s - 1))    , 
    
                    D_XOR(s, q_3, t_3) ⩽ 2 q_3 + 2^s+2(2+log_2 s - log_2 (log_2 q_3 - log_2 s - 1))    .

            
            Положим q_2 = q_3. Обозначим d = 2+log_2 s - log_2 (log_2 q_2 - log_2 s - 1), тогда
            
    D(f,q) ≲ 2^n + q_2 + dn2^n+1/s + q_3 2^k+2/s + d2^n+3/s  .

            
            Согласно формуле (<ref>),
            верно соотношение
            
    2^n + q_2 + 4q_3 2^k/s≲ 2^n    .

            Отсюда получаем, что
            
    D(f,q) ≲ 2^n + dn2^n+1/s≲
                        2^n + 2^n+1(2+log_2 n - log_2 (log_2 q_2 - log_2 n - 1))    .


            Из соотношения (<ref>) следует, что
            log_2 q_2 > log_2 (q - 4n) - 1. Таким образом, получаем итоговую оценку сверху вида
            
    D(f,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2))    ,

            которая верна при log_2 (q - 4n) > log_2 n + 2 ⇒ q > 8n.

            Видно, что второй способ синтеза асимптотически лучше первого.
            
    
    Поскольку мы описали алгоритм синтеза обратимой схемы для произвольного отображения f, то
    
    D(n,q) ⩽ D(f,q) ≲ 2^n+1(2,5 + log_2 n - log_2 (log_2 (q - 4n) - log_2 n - 2))

    при q > 8n.


При увеличении количества дополнительных входов с q ∼ n 2^n-o(n) до q ∼ 2^n
верхняя асимптотическая оценка функции D(n,q) снижается с экспоненциальной до линейной,
см. соотношение (<ref>).
Однако выведение зависимости верхней оценки функции D(n,q) от q для диапазона n 2^n-o(n)≲ q ≲ 2^n
выходит за рамки данной работы.








§ ЗАКЛЮЧЕНИЕ


В данной работе были рассмотрены обратимые схемы, состоящие из функциональных элементов NOT, CNOT и 2-CNOT
и имеющие различное число дополнительных входов q.
Были изучены функции Шеннона сложности L(n, q) и глубины D(n,q) обратимой схемы,
реализующей какое-либо отображение _2^n →_2^n в условиях ограничения на значение q.
Были доказаны верхние оценки для функций L(n, q) и D(n, q) для диапазона 8n < q ≲ n2^n-o(n).
Из полученных соотношений можно сделать вывод, что использование дополнительной памяти в обратимых схемах,
состоящих из элементов NOT, CNOT и 2-CNOT, почти всегда позволяет существенно снизить сложность и глубину таких схем.






99
    shannon
    C. E. Shannon,
    “The synthesis of two-terminal switching circuits”,
    Bell System Technical Journal, 28:8 (1949), 59–98.

    lupanov_complexity
    О. Б. Лупанов,
    “Об одном методе синтеза схем”,
    Изв. вузов. Радиофизика.
    1958. Т. 1, № 1. С. 23–26.
        
    lupanov_delay
    О. Б. Лупанов,
    “О схемах из функциональных элементов с задержками”
    Проблемы кибернетики, вып. 23,
    Наука, M., 1970, 43–81.

    karpova
    Н. А. Карпова,
    “О вычислениях с ограниченной памятью”,
    Математические вопросы кибернетики, вып. 2,
    Наука, M., 1989, 131–144.

    feynman
    R. Feynman,
    “Quantum Mechanical Computers”,
    Optic News, 11:2 (1985), 11–20.
    DOI: http://doi.org/10.1364/ON.11.2.00001110.1364/ON.11.2.000011.

    maslov_thesis
    D. A. Maslov, Reversible Logic Synthesis,
    Ph. D. Thesis, University of New Brunswick Fredericton, N. B., Canada, 2003, 165 pp.

    shende
    V. V. Shende, A. K. Prasad, I. L. Markov, J. P. Hayes,
    “Synthesis of Reversible Logic Circuits”,
    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22:6 (2006), 710–722.
    DOI: http://doi.org/10.1109/TCAD.2003.81144810.1109/TCAD.2003.811448.
    
    my_dm_complexity
    Д. В. Закаблуков,
    “О сложности обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT”,
    Дискретная математика, 2016. Т. 28, № 2. С. 12–26.
    
    my_vestnik_mgu_depth
    Д. В. Закаблуков,
    “Оценка глубины обратимых схем из функциональных элементов NOT, CNOT и 2-CNOT”,
    Вестник Московского университета, серия <<Математика. Механика>>, 2016, № 3. С. 3–12.



