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

DOI10.1016/J.JCSS.2016.09.010zbMATH Open1391.94921arXiv1504.06876OpenAlexW2963059938MaRDI QIDQ340566FDOQ340566

Authors: Dmitriy V. Zakablukov 

Publication date: 14 November 2016

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

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

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

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

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)

Cites Work

• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Title not available (Why is that?)
• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines
• Fast synthesis of invertible circuits based on permutation group theory
• Title not available (Why is that?)

Cited In (12)

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