Dmitry Vladimirovich Zakablukov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Dmitry Vladimirovich Zakablukov has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Aleksey Evgenievich Zhukov
Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет)
1 shared publication - Georgii Kormakov
SKOLTECH
1 shared publication - Sergey Isaevich Gurov
Lomonosov Moscow State University, Moscow, Russian Federation
1 shared publication
Latest Publications
- 1 December 2022
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 32 (6) , 418
Synthesis of reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs
Article Synthesis of reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs was published on December 1, 2022 in the journal Discrete Mathematics and Applications (volume 32, issue 6).
- 1 December 2022
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 32 (6) , 418
Synthesis of reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs
Article Synthesis of reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs was published on December 1, 2022 in the journal Discrete Mathematics and Applications (volume 32, issue 6).
- 1 August 2022
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 32 (4) , 279-284
On synthesis of reversible circuits consisting of NOT, CNOT, 2-CNOT gates with small number of additional inputs
Reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs are considered. For such a circuit implementing a map f : Z 2 n → Z 2 n , $f\colon \mathbb Z_2^n \to \mathbb Z_2^n,$ we study the Shannon complexity function L(n, q) under the condition that the number of additional inputs is q = O(n 2). For this range of q, it is shown that L ( n , q ) ≍ n 2 n / log 2 n . $L(n,q) \asymp n2^n \mathop / \log_2 n.$ We show that L ( n , q ) ≍ n 2 n / log 2 ( n + q ) $L(n,q) \asymp n2^n \mathop / \log_2 (n+q)$ for all q ≲ n 2 n − ⌈ n / ϕ ( n ) ⌉ , $q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil},$ where ϕ ( n ) → ∞ and n / ϕ ( n ) − log 2 n → ∞ as n → ∞ . $\phi(n) \to \infty {\text {and}} \,n \mathop / \phi(n) - \log_2 n \to \infty \,{\text {as}}\, n \to \infty.$- 1 August 2022
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 32 (4) , 279-284
On synthesis of reversible circuits consisting of NOT, CNOT, 2-CNOT gates with small number of additional inputs
Reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs are considered. For such a circuit implementing a map f : Z 2 n → Z 2 n , $f\colon \mathbb Z_2^n \to \mathbb Z_2^n,$ we study the Shannon complexity function L(n, q) under the condition that the number of additional inputs is q = O(n 2). For this range of q, it is shown that L ( n , q ) ≍ n 2 n / log 2 n . $L(n,q) \asymp n2^n \mathop / \log_2 n.$ We show that L ( n , q ) ≍ n 2 n / log 2 ( n + q ) $L(n,q) \asymp n2^n \mathop / \log_2 (n+q)$ for all q ≲ n 2 n − ⌈ n / ϕ ( n ) ⌉ , $q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil},$ where ϕ ( n ) → ∞ and n / ϕ ( n ) − log 2 n → ∞ as n → ∞ . $\phi(n) \to \infty {\text {and}} \,n \mathop / \phi(n) - \log_2 n \to \infty \,{\text {as}}\, n \to \infty.$- Open Access
- 30 September 2019
- Published by Internet Media League in Международный научный журнал "Современные информационные технологии и ИТ-образование"
- Vol. 15 (3) , 541-552
Обратимые вычисления: обзор проблемы и новые результаты (отказоустойчивость и криптография)
В работе рассмотрены основные положения обратимости как новой парадигмы развития вычислительной техники. Первые разделы носят обзорный характер. Показана неизбежность т. н. теплового проклятия при сохранении традиционной парадигмы создания средств ВТ. Изложены основы обратимой логики, рассмотрены основные обратимые логические элементы и модели обратимых вычислений, в т. ч. обратимые клеточные автоматы. Кратко рассмотрены обратимые языки программирования. Во второй части затронуты основные вопросы логического синтеза схем из обратимых элементов и физическая реализация обратимой схемотехники. Кратко описана проблематика синтеза отказоустойчивых схем в парадигме обратимой схемотехники. Предлагается техника синтеза сбоеустойчивых обратимых элементов в хэмминговом пространстве и описываются некоторые такие схемы. Далее рассматривается проблематика применения схем из обратимых логических элементов в криптографии. Описывается предлагаемая общая схема создания обратимых схем с уборкой мусора , предназначенных для криптографических применений. The paper considers the main provisions of reversibility as a new paradigm for the development of computer technology. The first sections are of an overview nature. The inevitability of the so-called heat curse while maintaining the traditional paradigm of creating means of computer engineering. The fundamentals of reversible logic are presented, the main reversible logic elements and models of reversible computations, including reversible cellular automata, are considered. Reversible programming languages are briefly reviewed. The second part addresses the basic issues of the logical synthesis of circuits from reversible elements and the physical implementation of reversible circuitry. The synthesis of fault-tolerant circuits in the paradigm of reversible circuitry is briefly described. A technique for synthesizing fault-tolerant reversible elements in a hamming space is proposed and some such schemes are described. Next, the problems of using circuits of reversible logic elements in cryptography are considered. The proposed general scheme for creating reversible schemes with garbage collection intended for cryptographic applications is described.
- 30 September 2019
- Published by Internet Media League in Международный научный журнал "Современные информационные технологии и ИТ-образование"
- Vol. 15 (3) , 541-552
Open AccessОбратимые вычисления: обзор проблемы и новые результаты (отказоустойчивость и криптография)
В работе рассмотрены основные положения обратимости как новой парадигмы развития вычислительной техники. Первые разделы носят обзорный характер. Показана неизбежность т. н. теплового проклятия при сохранении традиционной парадигмы создания средств ВТ. Изложены основы обратимой логики, рассмотрены основные обратимые логические элементы и модели обратимых вычислений, в т. ч. обратимые клеточные автоматы. Кратко рассмотрены обратимые языки программирования. Во второй части затронуты основные вопросы логического синтеза схем из обратимых элементов и физическая реализация обратимой схемотехники. Кратко описана проблематика синтеза отказоустойчивых схем в парадигме обратимой схемотехники. Предлагается техника синтеза сбоеустойчивых обратимых элементов в хэмминговом пространстве и описываются некоторые такие схемы. Далее рассматривается проблематика применения схем из обратимых логических элементов в криптографии. Описывается предлагаемая общая схема создания обратимых схем с уборкой мусора , предназначенных для криптографических применений. The paper considers the main provisions of reversibility as a new paradigm for the development of computer technology. The first sections are of an overview nature. The inevitability of the so-called heat curse while maintaining the traditional paradigm of creating means of computer engineering. The fundamentals of reversible logic are presented, the main reversible logic elements and models of reversible computations, including reversible cellular automata, are considered. Reversible programming languages are briefly reviewed. The second part addresses the basic issues of the logical synthesis of circuits from reversible elements and the physical implementation of reversible circuitry. The synthesis of fault-tolerant circuits in the paradigm of reversible circuitry is briefly described. A technique for synthesizing fault-tolerant reversible elements in a hamming space is proposed and some such schemes are described. Next, the problems of using circuits of reversible logic elements in cryptography are considered. The proposed general scheme for creating reversible schemes with garbage collection intended for cryptographic applications is described.
- Open Access
On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates
The paper discusses the gate complexity of reversible circuits with the small number of additional inputs consisting of NOT, CNOT and 2-CNOT gates. We study Shannon's gate complexity function $L(n, q)$ for a reversible circuit implementing a Boolean transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $q \leqslant O(n^2)$ additional inputs. The general bound $L(n,q) \asymp n2^n \mathop / \log_2 n$ is proved for this case.Open AccessOn Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates
The paper discusses the gate complexity of reversible circuits with the small number of additional inputs consisting of NOT, CNOT and 2-CNOT gates. We study Shannon's gate complexity function $L(n, q)$ for a reversible circuit implementing a Boolean transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $q \leqslant O(n^2)$ additional inputs. The general bound $L(n,q) \asymp n2^n \mathop / \log_2 n$ is proved for this case. - Open Access
General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
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\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $8n < q \lesssim n2^{n-o(n)}$ additional inputs. The general upper bounds $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ and $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ are proved for this case.Open AccessGeneral Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
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\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $8n < q \lesssim n2^{n-o(n)}$ additional inputs. The general upper bounds $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ and $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ are proved for this case. - 1 February 2017
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 27 (1) , 57-67
On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
The paper is concerned with the problem of complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. For a reversible circuit implementing a map f : Z 2 n → Z 2 n $f: \mathbb Z_2^n\, \to\, \mathbb Z_2^n$ we define the Shannon complexity function L(n, q) as a function of n and the number q of additional inputs in the circuit. We prove the lower estimate L ( n , q ) ⩾ 2 n ( n − 2 ) 3 log 2 ( n + q ) − n 3 $L(n,q)\, \geqslant\, \displaystyle\frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the complexity of a reversible circuit and derive the upper estimate L(n, 0) ⩽ 48n2 n (1 + o(1)) / log2 n if there are no additional inputs. The asymptotic upper estimate for the complexity is shown to be L(n, q 0) ≲ 2 n with q 0 ∽ n2 n−o(n) additional inputs.- 1 February 2017
- Published by Walter de Gruyter GmbH in Discrete Mathematics and Applications
- Vol. 27 (1) , 57-67
On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
The paper is concerned with the problem of complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates. For a reversible circuit implementing a map f : Z 2 n → Z 2 n $f: \mathbb Z_2^n\, \to\, \mathbb Z_2^n$ we define the Shannon complexity function L(n, q) as a function of n and the number q of additional inputs in the circuit. We prove the lower estimate L ( n , q ) ⩾ 2 n ( n − 2 ) 3 log 2 ( n + q ) − n 3 $L(n,q)\, \geqslant\, \displaystyle\frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}$ for the complexity of a reversible circuit and derive the upper estimate L(n, 0) ⩽ 48n2 n (1 + o(1)) / log2 n if there are no additional inputs. The asymptotic upper estimate for the complexity is shown to be L(n, q 0) ≲ 2 n with q 0 ∽ n2 n−o(n) additional inputs.- 6 October 2016
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 84, 132-143
On asymptotic gate complexity and depth of reversible circuits without additional memory
- 6 October 2016
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 84, 132-143
On asymptotic gate complexity and depth of reversible circuits without additional memory
- 30 June 2016
- Published by Springer Nature
- p. 223-238
Application of Permutation Group Theory in Reversible Logic Synthesis
- 30 June 2016
- Published by Springer Nature
- p. 223-238
Application of Permutation Group Theory in Reversible Logic Synthesis
- 1 May 2016
- Published by Allerton Press in Moscow University Mathematics Bulletin
- Vol. 71 (3) , 89-97
Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
- 1 May 2016
- Published by Allerton Press in Moscow University Mathematics Bulletin
- Vol. 71 (3) , 89-97
Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
- Open Access
On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory
The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript{2}NOT gates. We consider a set $F(n,q)$ of all transformations $\mathbb B^n \to \mathbb B^n$ that can be realized by reversible circuits with $(n+q)$ inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ in case of $q > 0$: $L(n,q_0) \lesssim 2^n$ if $q_0 \sim n 2^{n-o(n)}$ and $D(n,q_1) \lesssim 3n$ if $q_1 \sim 2^n$.Open AccessOn Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory
The reversible logic can be used in various research areas, e.g. quantum computation, cryptography and signal processing. In the paper we study reversible logic circuits with additional inputs, which consist of NOT, CNOT and C\textsuperscript{2}NOT gates. We consider a set $F(n,q)$ of all transformations $\mathbb B^n \to \mathbb B^n$ that can be realized by reversible circuits with $(n+q)$ inputs. An analogue of Lupanov's method for the synthesis of reversible logic circuits with additional inputs is described. We prove upper asymptotic bounds for the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ in case of $q > 0$: $L(n,q_0) \lesssim 2^n$ if $q_0 \sim n 2^{n-o(n)}$ and $D(n,q_1) \lesssim 3n$ if $q_1 \sim 2^n$.