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:1505.02372

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

Dmitry Vladimirovich Zakablukov

Published May 10, 2015• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1505.02372

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

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

Dmitry Vladimirovich Zakablukov

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.

arXiv:1702.08045•Feb 26, 2017•0 citations

Asymptotic bounds of depth for a reversible circuit consisting of NOT, CNOT and 2-CNOT gates

Dmitry Vladimirovich Zakablukov

The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. Reversible circuit depth function $D(n, q)$ for a circuit implementing a transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ is introduced as a function of $n$ and the number of additional inputs $q$. It is proved that for the case of implementing a permutation from $A(\mathbb Z_2^n)$ with a reversible circuit having no additional inputs the depth is bounded as $D(n, 0) \gtrsim 2^n / (3\log_2 n)$. It is proved that for the case of implementing a transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with a reversible circuit having $q_0 \sim 2^n$ additional inputs the depth is bounded as $D(n, q_0) \lesssim 3n$.

arXiv:1501.04344•Jan 18, 2015•0 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

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

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
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.
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 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)L(n, q)L(n,q) and depth function D(n,q)D(n, q)D(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 8n<q≲n2n−o(n)8n < q \lesssim n2^{n-o(n)}8n<q≲n2n−o(n) additional inputs. The general upper bounds 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)≲2n+1(2,5+log⁡2n−log⁡2(log⁡2(q−4n)−log⁡2n−2))D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))D(n,q)≲2n+1(2,5+log2​n−log2​(log2​(q−4n)−log2​n−2)) are proved for this case.
The paper discusses the asymptotic depth of a reversible circuit consisting of NOT, CNOT and 2-CNOT gates. Reversible circuit depth function D(n,q)D(n, q)D(n,q) for a circuit implementing a transformation f ⁣:Z2n→Z2nf\colon \mathbb Z_2^n \to \mathbb Z_2^nf:Z2n​→Z2n​ is introduced as a function of nnn and the number of additional inputs qqq. It is proved that for the case of implementing a permutation from A(Z2n)A(\mathbb Z_2^n)A(Z2n​) with a reversible circuit having no additional inputs the depth is bounded as D(n,0)≳2n/(3log⁡2n)D(n, 0) \gtrsim 2^n / (3\log_2 n)D(n,0)≳2n/(3log2​n). It is proved that for the case of implementing a transformation f ⁣:Z2n→Z2nf\colon \mathbb Z_2^n \to \mathbb Z_2^nf:Z2n​→Z2n​ with a reversible circuit having q0∼2nq_0 \sim 2^nq0​∼2n additional inputs the depth is bounded as D(n,q0)≲3nD(n, q_0) \lesssim 3nD(n,q0​)≲3n.
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</
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.
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.