Fast algorithm for 4-qubit reversible logic circuits synthesis

• Main Authors: Zhiqiang Li, Hanwu Chen, Baowen Xu, Wenjie Liu, Xiaoyu Song, Xilin Xue
• Format: Conference Proceeding
• Language: English
• Subjects: Evolutionary computation
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/CEC.2008.4631091

Owing to the exponential nature of the memory or run-tune complexity, many existing methods can only synthesize 3-qubit circuits, however, (G.W. Yang et al., 2005) can achieve 12 steps for the CNP (controlled-Not gate, NOT gate and Peres gate) library in 4-qubit circuit synthesis with mini-length by using an enhanced bi-directional synthesis approach. We mainly absorb the ideas of our 3-qubit synthesis algorithms based on hash table and present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and mini-length cost based on constructing the shortest coding and the specific topological compression, whose lossless compression ratios of the space of n-qubit circuits is near 2timesn!. Our algorithm has created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the CNT (Toffoli gate) library, and it can quickly achieve 16 steps through cascading created circuits. To the best of our knowledge, there are no other algorithms to achieve the contribution.