On asymptotic gate complexity and depth of reversible circuits without additional memory

DOI10.1016/J.JCSS.2016.09.010MaRDI QIDQ340566zbMATH OpenOpenAlexFDO

Authors Dmitriy V. Zakablukov

Publication date 14 November 2016

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.06876

zbMATH Keywords

reversible logicasymptotic boundscircuit depthgate complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12) General theory for finite permutation groups (20B05) Analytic circuit theory (94C05) Networks and circuits as models of computation; circuit complexity (68Q06)

Abstract: Reversible computation is one of the most promising emerging technologies of the future. The usage of reversible circuits in computing devices can lead to a significantly lower power consumption. In this paper we study reversible logic circuits consisting of NOT, CNOT and 2-CNOT gates. We introduce a set $F(n,q)$ of all transformations $mathbb{Z}_2^{n}omathbb{Z}_2^n$ that can be implemented by reversible circuits with $(n+q)$ inputs. We define the Shannon gate complexity function $L(n,q)$ and the depth function $D(n,q)$ as functions of $n$ and the number of additional inputs $q$. First, we prove general lower bounds for functions $L(n,q)$ and $D(n,q)$. Second, we introduce a new group theory based synthesis algorithm, which can produce a circuit $mathfrakS$ without additional inputs and with the gate complexity $L(mathfrakS)leq3n{2}^{n+4}(1+o(1))mathop/lo{g}_{2}n$. Using these bounds, we state that almost every reversible circuit with no additional inputs, consisting of NOT, CNOT and 2-CNOT gates, implements a transformation from $F(n,0)$ with the gate complexity $L(n,0)asympn{2}^{n}mathop/lo{g}_{2}n$ and with the depth $D(n,0)geq{2}^n(1-o(1))mathop/(3lo{g}_{2}n)$.

Recommendations

• 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
• Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
• Complexity of reversible circuits and their quantum implementations
• On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
• Mathematical Foundations of Computer Science 2005
• On the complexity of gradient gate circuits
• Reversible and irreversible computations of deterministic finite-state devices
• Depth-optimized reversible circuit synthesis
• Reversible modified reconstructability analysis of Boolean circuits and its quantum computation

Cites work

• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 5242374 (Why is no real title available?)
• Fast synthesis of invertible circuits based on permutation group theory
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines

Cited in

(12)

• Complexity of reversible circuits and their quantum implementations
• Theory and Applications of Models of Computation
• Application of Permutation Group Theory in Reversible Logic Synthesis
• A finite alternation result for reversible Boolean circuits
• On the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
• On synthesis of reversible circuits consisting of NOT, CNOT, 2-CNOT gates with small number of additional inputs
• Finding the redundant gates in reversible circuits
• Reversible circuit synthesis by genetic programming using dynamic gate libraries
• Estimation of the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates
• On the complexity of gradient gate circuits
• Realization and synthesis of reversible functions
• 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

This page was built for publication: On asymptotic gate complexity and depth of reversible circuits without additional memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340566)