Application of Permutation Group Theory in Reversible Logic Synthesis

DOI10.1007/978-3-319-40578-0_17MaRDI QIDQ3186603zbMATH OpenOpenAlexFDO

Authors Dmitriy V. Zakablukov

Publication date 10 August 2016

Published in Reversible Computation (Search for Journal in Brave)

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

zbMATH Keywords

permutation group theoryreversible logic synthesis

Mathematics Subject Classification ID

Permutation groups (20B99) Networks and circuits as models of computation; circuit complexity (68Q06) Analytic circuit theory (94C05)

Abstract: The paper discusses various applications of permutation group theory in the synthesis of reversible logic circuits consisting of Toffoli gates with negative control lines. An asymptotically optimal synthesis algorithm for circuits consisting of gates from the NCT library is described. An algorithm for gate complexity reduction, based on equivalent replacements of gates compositions, is introduced. A new approach for combining a group-theory-based synthesis algorithm with a Reed-Muller-spectra-based synthesis algorithm is described. Experimental results are presented to show that the proposed synthesis techniques allow a reduction in input lines count, gate complexity or quantum cost of reversible circuits for various benchmark functions.

Recommendations

• scientific article; zbMATH DE number 1543308
• Theory and Applications of Models of Computation
• Fast synthesis of invertible circuits based on permutation group theory
• A reversible logical circuit synthesis algorithm based on decomposition of cycle representations of permutations
• A new reversible circuit synthesis algorithm based on cycle representations of permutations
• Generating the group of reversible logic gates
• Algebraic characterization of reversible logic gates
• The decomposition of an arbitrary reversible logic circuit

Cites work

• Logical Reversibility of Computation
• On asymptotic gate complexity and depth of reversible circuits without additional memory
• Reducing the Depth of Quantum Circuits Using Additional Circuit Lines
• Synthesis and optimization of reversible circuits -- a survey
• Templates for positive and negative control Toffoli networks

Cited in

(3)

• Reversible circuit synthesis by genetic programming using dynamic gate libraries
• Generating the group of reversible logic gates
• Optimizing the depth of quantum implementations of linear layers

Describes a project that uses

Uses Software

• RevLib
• RCViewer+
• GitHub

This page was built for publication: Application of Permutation Group Theory in Reversible Logic Synthesis

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