Application of Permutation Group Theory in Reversible Logic Synthesis
Preprint
Abstract
This paper discusses various applications of permutation group theory in the synthesis of reversible logic circuits, consisting of Toffoli gates with negative control lines. First asymptotically optimal synthesis algorithm is described. An algorithm for the gate complexity reduction, based on equivalent replacements of gates compositions, is introduced. New approach for combining group theory based synthesis algorithms with Reed-Muller spectra based synthesis algorithms is described. Experimental results are presented to show that the proposed synthesis techniques allows to reduce input lines count, the gate complexity or the quantum cost of a reversible circuit, implementing a known benchmark specification.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On asymptotic gate complexity and depth of reversible circuits without additional memoryJournal of Computer and System Sciences, 2016
- Synthesis and optimization of reversible circuits—a surveyACM Computing Surveys, 2013
- Reducing the Depth of Quantum Circuits Using Additional Circuit LinesLecture Notes in Computer Science, 2013
- Reversible circuit synthesis using a cycle-based approachACM Journal on Emerging Technologies in Computing Systems, 2010
- Reducing Reversible Circuit Cost by Adding Lines2010
- Quantum Circuit Simplification and Level CompactionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008
- Techniques for the synthesis of reversible Toffoli networksACM Transactions on Design Automation of Electronic Systems, 2007
- Synthesis of reversible logic circuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003
- Transformation rules for designing CNOT-based quantum circuitsProceedings of the 39th conference on Design automation - DAC '02, 2002
- Logical Reversibility of ComputationIBM Journal of Research and Development, 1973