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

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

Dmitry Vladimirovich Zakablukov

Published Jan 18, 2015• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1501.04344

Related papers

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

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

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

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

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