Reversible Circuit Synthesis Using a Cycle-Based Approach

Abstract

Reversible logic has applications in various research areas including signal processing, cryptography and quantum computation. In this paper, direct NCT-based synthesis of a given $k$-cycle in a cycle-based synthesis scenario is examined. To this end, a set of seven building blocks is proposed that reveals the potential of direct synthesis of a given permutation to reduce both quantum cost and average runtime. To synthesize a given large cycle, we propose a decomposition algorithm to extract the suggested building blocks from the input specification. Then, a synthesis method is introduced which uses the building blocks and the decomposition algorithm. Finally, a hybrid synthesis framework is suggested which uses the proposed cycle-based synthesis method in conjunction with one of the recent NCT-based synthesis approaches which is based on Reed-Muller (RM) spectra. The time complexity and the effectiveness of the proposed synthesis approach are analyzed in detail. Our analyses show that the proposed hybrid framework leads to a better quantum cost in the worst-case scenario compared to the previously presented methods. The proposed framework always converges and typically synthesizes a given specification very fast compared to the available synthesis algorithms. Besides, the quantum costs of benchmark functions are improved about 20% on average (55% in the best case).

25 pages, 21 figures, 2 tables

References in corpus (3)

• Synthesis of Quantum Logic Circuits
• Quantum Circuit Simplification and Level Compaction
• Benchmarking quantum control methods on a 12-qubit system

Cited by in corpus (15)

• Synthesis and Optimization of Reversible Circuits - A Survey
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Reversible Circuit Optimization via Leaving the Boolean Domain
• Depth-Optimized Reversible Circuit Synthesis
• Application of Permutation Group Theory in Reversible Logic Synthesis
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
• Optimal and asymptotically optimal NCT reversible circuits by the gate types
• Ancilla-Quantum Cost Trade-off during Reversible Logic Synthesis using Exclusive Sum-of-Products
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Ancilla-free synthesis of large reversible functions using binary decision diagrams
• Ancilla-free Reversible Logic Synthesis via Sorting
• Asymptotically optimal synthesis of reversible circuits
• Development of Tool for Mapping Conventional Circuit to Reversible Logic
• Structured decomposition for reversible Boolean functions
• Ancilla-Input and Garbage-Output Optimized Design of a Reversible Quantum Integer Multiplier