arXiv:1802.02346

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

Dmitry Vladimirovich Zakablukov

Published Feb 7, 2018• 0 citations

Abstract

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.

DOI: 10.48550/arxiv.1802.02346

Related papers

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

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

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 Asymptotic Gate Complexity and Depth of Reversible Circuits With Additional Memory

Dmitry Vladimirovich Zakablukov

arXiv:1505.02372May 10, 20150 citations

arXiv:1802.02346

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

Dmitry Vladimirovich Zakablukov

Published Feb 7, 2018• 0 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.1802.02346

Related papers

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

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

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 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$ .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.02372May 10, 20150 citations

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.

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.

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

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.

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

q_0 \sim n 2^{n-o(n)}

and

D(n,q_1) \lesssim 3n

q_1 \sim 2^n