Techniques for the Synthesis of Reversible Toffoli Networks

Abstract

This paper presents novel techniques for the synthesis of reversible networks of Toffoli gates, as well as improvements to previous methods. Gate count and technology oriented cost metrics are used. Our synthesis techniques are independent of the cost metrics. Two new iterative synthesis procedure employing Reed-Muller spectra are introduced and shown to complement earlier synthesis approaches. The template simplification suggested in earlier work is enhanced through introduction of a faster and more efficient template application algorithm, updated (shorter) classification of the templates, and presentation of the new templates of sizes 7 and 9. A novel ``resynthesis'' approach is introduced wherein a sequence of gates is chosen from a network, and the reversible specification it realizes is resynthesized as an independent problem in hopes of reducing the network cost. Empirical results are presented to show that the methods are effective both in terms of the realization of all 3x3 reversible functions and larger reversible benchmark specifications.

20 pages, 5 figures

References in corpus (3)

• Scalable multi-particle entanglement of trapped ions
• Benchmarking quantum control methods on a 12-qubit system
• Quantum Circuit Identities

Cited by in corpus (26)

• Synthesis and Optimization of Reversible Circuits - A Survey
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• Basic circuit compilation techniques for an ion-trap quantum machine
• A Study of Optimal 4-bit Reversible Toffoli Circuits and Their Synthesis
• A Library-Based Synthesis Methodology for Reversible Logic
• Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning
• Verified compilation of space-efficient reversible circuits
• Reversible Circuit Optimization via Leaving the Boolean Domain
• Exact and practical pattern matching for quantum circuit optimization
• Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost
• Reducing Quantum Cost in Reversible Toffoli Circuits
• Linear and logarithmic time compositions of quantum many-body operators
• Reversible circuit compilation with space constraints
• Depth-Optimized Reversible Circuit Synthesis
• Application of Permutation Group Theory in Reversible Logic Synthesis
• Reversible Logic Synthesis with Minimal Usage of Ancilla Bits
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Optimal and asymptotically optimal NCT reversible circuits by the gate types
• Reduction of circuit depth by mapping qubit-based quantum gates to a qudit basis
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Ancilla-free synthesis of large reversible functions using binary decision diagrams
• Design Automation and Design Space Exploration for Quantum Computers
• Synthesis methods for reversible circuits consisting of NOT, CNOT and 2-CNOT gates (Ph.D. thesis)
• Self-Inverse Functions and Palindromic Circuits