Application of Permutation Group Theory in Reversible Logic Synthesis

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.

arXiv commentIn English, 15 pages, 2 figures, 7 tables. Proceeding of the RC 2016 conference

References in corpus (6)

• Synthesis and Optimization of Reversible Circuits - A Survey
• Quantum Circuit Simplification and Level Compaction
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Techniques for the Synthesis of Reversible Toffoli Networks
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• A Cost Minimization Approach to Synthesis of Linear Reversible Circuits

Cited by in corpus (3)

• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)