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

Discrete Mathematics and Applications

Synthesis of reversible circuits consisting of NOT, CNOT and 2-CNOT gates with small number of additional inputs

Dmitry Vladimirovich Zakablukov

Published Dec 1, 2022• 0 citations
Publisher
DOI
10.1515/dma-2022-9998

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

Synthesis of reversible circuits with minimal costs

Guowu Yang, Xiaoyu Song B, William N. N. Hung +2 more

CALCOLO•Sep 1, 2008•16 citations

A New Algorithm for Reversible Logic Circuit Synthesis

Naga Kumar Gaju

International Journal of Engineering Research and•Feb 22, 2018•0 citations

Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)

Dmitry Vladimirovich Zakablukov

In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.

arXiv:1806.00687•Jun 2, 2018•1 citation

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

Synthesis of Ternary Reversible Circuits based on Permutation Cycles

P. Mercy Nesa Rani

Lecture notes in networks and systems•Jan 1, 2021•0 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)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.
In this paper, reversible circuits consisting of NOT, CNOT and 2-CNOT gates are studied. Several asymptotically optimal by the order of magnitude synthesis methods are described. Some circuit's complexity reduction approaches are considered. Implementation of discrete logarithm within a reversible circuit is discussed. The main conclusion in the paper is that the usage of additional inputs (additional memory) in reversible circuits almost always allow to reduce their complexity, depth and weight.
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.