Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Congress on Evolutionary Computation (CEC)

Fast algorithm for 4-qubit reversible logic circuits synthesis

Zhiqiang Li, Hanwu Chen, Baowen Xu, Wenjie Liu, Xiaoyu Song B, Xilin Xue

Published Jun 1, 2008• 12 citations
Publisher

Abstract

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.

DOI
10.1109/cec.2008.4631091

Related papers

Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis

Zhiqiang Li, Hanwu Chen, Guowu Yang +1 more

Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of n -bit circuits reaches near 2×n! . This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.

Journal of Applied Mathematics•Jan 1, 2013•5 citations

Fast Algorithms for 4-qubit Reversible Logic Circuits Synthesis

Xiling Xue

Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost.We present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and minimum 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 near2×n!.We firstly have created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the Controlled-Not gate,NOT gate and Toffoli gate library,and our method can achieve 16 steps through cascading created circuits.Our algorithm can not only synthesizes all the 4-qubit benchmark circuits,but also runs extremely fast.

Dianzi xuebao•Jan 1, 2008•5 citations

A Synthesis Algorithm for 4-Bit Reversible Logic Circuits with Minimum Quantum Cost

Zhiqiang Li, Hanwu Chen, Xiaoyu Song B +1 more

This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.

ACM Journal on Emerging Technologies in Computing Systems•Dec 30, 2014•3 citations

Bi-Directional Synthesis of 4-Bit Reversible Circuits

Guowu Yang, Xiaoyu Song B, William N. N. Hung +1 more

Reversible circuits play an important role in quantum computing, which is one of the most promising emerging technologies. In this paper, we investigate the problem of optimally synthesizing 4-bit reversible circuits. We present an enhanced bi-directional synthesis approach. Owing to the exponential nature of the memory and run-time complexity, all existing methods can only perform four steps for the Controlled-Not gate NOT gate, and Peres gate library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can optimally be synthesized by over 5 × 106 times. We synthesized 1000 random 4-bit reversible circuits. The statistical analysis result supports our estimation. The quantum cost of our result is also better than the quantum cost of other approaches. The promising experimental results demonstrate the effectiveness of our approach.

The Computer Journal•Jul 14, 2007•36 citations

Efficient Algorithm for Synthesis of Optimal NCV 3-Qubit Reversible Circuits Using New Quantum Logic Gate Library

Xiao Fang-ying

Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum NOT,CNOT,Controlled-V and Controlled-V+(NCV)gates,the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis.This paper proposes using NCV gates to create a new quantum logic gate library,which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic synthesis to easily solved two-valued logic synthesis.We present a 3-qubit efficient synthesis algorithms based on perfect hash function,which can quickly construct all optimal 3-qubit circuits——the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.

Dianzi xuebao•Jan 1, 2013•2 citations

Bi-Direction Synthesis for Reversible Circuits

Guowu Yang, Xiaoyu Song B, William N. N. Hung +1 more

Quantum computing is one of the most promising emerging technologies of the future. Reversible circuits are an important class of quantum circuits. In this paper, we investigate the problem of optimally synthesizing four-qubit reversible circuits. We present an enhanced bidirectional synthesis approach. Due to the super-exponential increase on the memory requirement, all the existing methods can only perform four steps for the CNP (Control-Not gate, NOT gate, and Peres gate) library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can be optimally synthesized by over 5/sup */10/sup 6/ times. Moreover, our approach is faster than the existing approaches by orders of magnitude. The promising experimental results demonstrate the effectiveness of our approach.

IEEE Computer Society Annual Symposium on VLSI•May 24, 2005•14 citations
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.
Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of n -bit circuits reaches near 2×n! . This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.
Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost.We present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and minimum 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 near2×n!.We firstly have created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the Controlled-Not gate,NOT gate and Toffoli gate library,and our method can achieve 16 steps through cascading created circuits.Our algorithm can not only synthesizes all the 4-qubit benchmark circuits,but also runs extremely fast.
This article presents an algorithm which can quickly find the exact minimum solution to almost all of 4-bit reversible functions. We assume minimization of quantum cost (MQC). This algorithm is designed in the most memory-efficient way, or it will quickly run out of memory. Therefore, we construct the shortest coding of permutations, the topological compression and flexible data structures for the memory savings. First, hash tables are used for all 8-gate 4-bit circuits with the minimization of gate count (MGC) by using the GT library (with NOT, CNOT, Toffoli and Toffoli-4 gates). Second, we merge and split the hash tables, thus generating a single longer hash table for high-performance. Third, we synthesize these circuits with MQC by using the GTP library (with GT, Peres, and Inverted Peres gates) based on the hash table. Finally, according to the comparison of the QC of circuits, the algorithm can quickly converge for any 4-bit reversible circuit with MQC. By synthesizing all benchmark functions, in comparison with Szyprowski and Kerntopf [2011], the running time and QC are reduced up to 99.95% and 18.2%, respectively.
Reversible circuits play an important role in quantum computing, which is one of the most promising emerging technologies. In this paper, we investigate the problem of optimally synthesizing 4-bit reversible circuits. We present an enhanced bi-directional synthesis approach. Owing to the exponential nature of the memory and run-time complexity, all existing methods can only perform four steps for the Controlled-Not gate NOT gate, and Peres gate library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can optimally be synthesized by over 5 × 106 times. We synthesized 1000 random 4-bit reversible circuits. The statistical analysis result supports our estimation. The quantum cost of our result is also better than the quantum cost of other approaches. The promising experimental results demonstrate the effectiveness of our approach.
Owing to the exponential nature of the memory or run-time complexity,many existing methods can only synthesize 3-qubit logic circuits using quantum logic gate library,however,a few can optimally synthesize 3-qubit logic circuits for quantum NOT,CNOT,Controlled-V and Controlled-V+(NCV)gates,the key approach reduces the NCV quantum circuit synthesis problem to four-valued logic synthesis.This paper proposes using NCV gates to create a new quantum logic gate library,which is exactly the same as NCV gate library in the synthesis of all optimal 3-qubit circuits,thus it also reduces the four-valued logic synthesis to easily solved two-valued logic synthesis.We present a 3-qubit efficient synthesis algorithms based on perfect hash function,which can quickly construct all optimal 3-qubit circuits——the average speed that synthesizes circuits with minimum cost is nearly 127 times faster than that of the best result of Maslov 2007.
Quantum computing is one of the most promising emerging technologies of the future. Reversible circuits are an important class of quantum circuits. In this paper, we investigate the problem of optimally synthesizing four-qubit reversible circuits. We present an enhanced bidirectional synthesis approach. Due to the super-exponential increase on the memory requirement, all the existing methods can only perform four steps for the CNP (Control-Not gate, NOT gate, and Peres gate) library. Our novel method can achieve 12 steps. As a result, we augment the number of circuits that can be optimally synthesized by over 5/sup */10/sup 6/ times. Moreover, our approach is faster than the existing approaches by orders of magnitude. The promising experimental results demonstrate the effectiveness of our approach.