Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1806.00687

Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)

Dmitry Vladimirovich Zakablukov

Published Jun 2, 2018• 1 citation
arXivHTMLPDF

Abstract

In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.

DOI
10.48550/arxiv.1806.00687

Related papers

On Synthesis of Reversible Circuits with Small Number of Additional Inputs Consisting of NOT, CNOT and 2-CNOT Gates

Dmitry Vladimirovich Zakablukov

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.

arXiv:1802.02346•Feb 7, 2018•0 citations

On Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory

Dmitry Vladimirovich Zakablukov

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$.

arXiv:1505.02372•May 10, 2015•0 citations

On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates

Dmitry Vladimirovich Zakablukov

Abstract 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) ⩽ 48 n 2 n (1 + o (1)) / log 2 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 ∽ n 2 n − o ( n ) additional inputs.

arXiv:1412.2662•Discrete Mathematics and Applications•Feb 1, 2017•6 citations

On the dependence of the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates on the number of additional inputs

Dmitry Vladimirovich Zakablukov

Abstract The paper is concerned with the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates under constraints on the number of additional inputs. We study the Shannon functions for the complexity L ( n , q ) and depth D ( n , q ) of a reversible circuit implementing a map f : ℤ 2 n → ℤ 2 n $f\colon \mathbb{Z}_2^n \to \mathbb{Z}_2^n$ under the condition that the number of additional inputs q is in the range 8 n < q ≲ n 2 n − ⌈ n / ϕ ( n ) ⌉ $8n < q \mathbin{\lower.3ex\hbox{$\buildrel<\over {\smash{\scriptstyle\sim}\vphantom{_x}}$}} n{2^{n - \left\lceil {n{\rm{ }}/\phi (n)} \right\rceil }}$ , where ϕ ( n ) → ∞ and n / ϕ ( n ) − log 2 n → ∞ as n → ∞. We establish the upper estimates L ( n , q ) ≲ 2 n + 8 n 2 n / ( log 2 ( q − 4 n ) − log 2 n − 2 ) $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\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 − 4 n ) − log 2 n</

Discrete Mathematics and Applications•Feb 1, 2021•4 citations

Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates

Dmitry Vladimirovich Zakablukov

The paper discusses the asymptotic depth of a reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function D(n, q) is introduced for a circuit implementing a mapping f: Z 2 → Z 2 as a function of n and the number q of additional inputs. It is proved that for the case of implementation of a permutation from A(Z 2 ) with a reversible circuit having no additional inputs the depth is bounded as D(n, 0) ≳ 2 n /(3log2 n). It is also proved that for the case of transformation f: Z 2 → Z 2 with a reversible circuit having q 0 ~ 2 n additional inputs the depth is bounded as D(n,q 0) ≲ 3n.

Moscow University Mathematics Bulletin•May 1, 2016•2 citations

Reduction of the reversible circuits gate complexity without using the equivalent replacement tables for the gate compositions

Dmitri Zakablukov

The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.

Science and Education of the Bauman MSTU•Mar 3, 2014•5 citations
In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.
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)L(n, q)L(n,q) for a reversible circuit implementing a Boolean transformation f ⁣:Z2n→Z2nf\colon \mathbb Z_2^n \to \mathbb Z_2^nf:Z2n​→Z2n​ with q⩽O(n2)q \leqslant O(n^2)q⩽O(n2) additional inputs. The general bound L(n,q)≍n2n/log⁡2nL(n,q) \asymp n2^n \mathop / \log_2 nL(n,q)≍n2n/log2​n is proved for this case.
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)F(n,q)F(n,q) of all transformations Bn→Bn\mathbb B^n \to \mathbb B^nBn→Bn that can be realized by reversible circuits with (n+q)(n+q)(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)L(n,q)L(n,q) and the depth function D(n,q)D(n,q)D(n,q) in case of q>0q > 0q>0: L(n,q0)≲2nL(n,q_0) \lesssim 2^nL(n,q0​)≲2n if q0∼n2n−o(n)q_0 \sim n 2^{n-o(n)}q0​∼n2n−o(n) and D(n,q1)≲3nD(n,q_1) \lesssim 3nD(n,q1​)≲3n if q1∼2nq_1 \sim 2^nq1​∼2n.
Abstract 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:Z2n → Z2nf: \mathbb Z_2^n\, \to\, \mathbb Z_2^nf:Z2n​→Z2n​ 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) ⩾ 2n(n−2)3log⁡2(n+q)−n3L(n,q)\, \geqslant\, \displaystyle\frac{2^n(n-2)}{3\log_2(n+q)} - \frac{n}{3}L(n,q)⩾3log2​(n+q)2n(n−2)​−3n​ for the complexity of a reversible circuit and derive the upper estimate L ( n , 0) ⩽ 48 n 2 n (1 + o (1)) / log 2 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 ∽ n 2 n − o ( n ) additional inputs.
Abstract The paper is concerned with the complexity and depth of reversible circuits consisting of NOT, CNOT, and 2-CNOT gates under constraints on the number of additional inputs. We study the Shannon functions for the complexity L ( n , q ) and depth D ( n , q ) of a reversible circuit implementing a map f : ℤ 2 n → ℤ 2 n f ⁣:Z2n→Z2nf\colon \mathbb{Z}_2^n \to \mathbb{Z}_2^nf:Z2n​→Z2n​ under the condition that the number of additional inputs q is in the range 8 n < q ≲ n 2 n − ⌈ n / ϕ ( n ) ⌉ $8n < q \mathbin{\lower.3ex\hbox{$\buildrel<\over {\smash{\scriptstyle\sim}\vphantom{_x}}$}} n{2^{n - \left\lceil {n{\rm{ }}/\phi (n)} \right\rceil }}$ , where ϕ ( n ) → ∞ and n / ϕ ( n ) − log 2 n → ∞ as n → ∞. We establish the upper estimates L ( n , q ) ≲ 2 n + 8 n 2 n / ( log 2 ( q − 4 n ) − log 2 n − 2 ) L(n,q)≲2n+8n2n/(log⁡2(q−4n)−log⁡2n−2)L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)L(n,q)≲2n+8n2n/(log2​(q−4n)−log2​n−2) and D ( n , q ) ≲ 2 n + 1 ( 2 , 5 + log 2 n − log 2 ( log 2 ( q − 4 n ) − log 2 n</
The paper discusses the asymptotic depth of a reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function D(n, q) is introduced for a circuit implementing a mapping f: Z 2 → Z 2 as a function of n and the number q of additional inputs. It is proved that for the case of implementation of a permutation from A(Z 2 ) with a reversible circuit having no additional inputs the depth is bounded as D(n, 0) ≳ 2 n /(3log2 n). It is also proved that for the case of transformation f: Z 2 → Z 2 with a reversible circuit having q 0 ~ 2 n additional inputs the depth is bounded as D(n,q 0) ≲ 3n.
The subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources. Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions. This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted). Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers. The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered. The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.