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:1412.2662 · Discrete Mathematics and Applications

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

Dmitry Vladimirovich Zakablukov

Published Feb 1, 2017• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1515/dma-2017-0007

Related papers

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

Lower bounds for the CNOT-complexity of linear reversible operators

Søren Fuglede Jørgensen

The CNOT-complexity of an invertible matrix over $\mathbb{F}_2$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all $n \times n$ matrices is known to be $Θ(n^2 / \log n)$, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity $3(n-1)$. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least $4n - o(n)$, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$, whose CNOT-complexity exceeds that of the cyclic permutation on $n$ symbols.

quant-pharXiv:2607.22248•Jul 27, 2026•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 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
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 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 CNOT-complexity of an invertible matrix over F2\mathbb{F}_2F2​ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all n×nn \times nn×n matrices is known to be Θ(n2/log⁡n)Θ(n^2 / \log n)Θ(n2/logn), no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity 3(n−1)3(n-1)3(n−1). We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least 4n−o(n)4n - o(n)4n−o(n), asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix A∈GLn(F2)A \in \mathrm{GL}_{n}(\mathbb{F}_2)A∈GLn​(F2​), n=17167n = 17167n=17167, whose CNOT-complexity exceeds that of the cyclic permutation on nnn symbols.
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.
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.