Moscow University Mathematics Bulletin

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

Dmitry Vladimirovich Zakablukov

Published May 1, 2016• 2 citations

Abstract

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.

DOI: 10.3103/s0027132216030013

Related papers

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

Dmitry Vladimirovich Zakablukov

arXiv:1501.04344Jan 18, 20150 citations

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

Dmitry Vladimirovich Zakablukov

arXiv:1702.08045Feb 26, 20170 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

Discrete Mathematics and ApplicationsFeb 1, 20214 citations

Lower bounds for the CNOT-complexity of linear reversible operators

Søren Fuglede Jørgensen

quant-pharXiv:2607.22248Jul 27, 20260 citations

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

Dmitry Vladimirovich Zakablukov

arXiv:1412.2662Discrete Mathematics and ApplicationsFeb 1, 20176 citations

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

Dmitry Vladimirovich Zakablukov

arXiv:1802.02346Feb 7, 20180 citations

Moscow University Mathematics Bulletin

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

Dmitry Vladimirovich Zakablukov

Published May 1, 2016• 2 citations

Publisher

Abstract

DOI: 10.3103/s0027132216030013

Related papers

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$ .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.04344Jan 18, 20150 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.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.08045Feb 26, 20170 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</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 ApplicationsFeb 1, 20214 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.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.22248Jul 27, 20260 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.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.2662Discrete Mathematics and ApplicationsFeb 1, 20176 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.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.02346Feb 7, 20180 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)

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

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.

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

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.

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.

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.