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

Dianzi xuebao

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

Xiao Fang-ying

Published Jan 1, 2013• 2 citations
OpenAlex

Abstract

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.

Related papers

Effective Hash-Based Algorithm for Reversible Logic Circuits Synthesis with Minimum Cost

Zhiqiang Li, Hanwu Chen, Baowen Xu +2 more

We present an effective algorithm which can construct optimal 3-qubit reversible logic circuits for any given reversible logic gates and costs by constructing a minimal perfect hash function. We also present an algorithm which can automatically construct quantum gate library. In the experiments on 3-qubit synthesis, our algorithm synthesizes all optimal reversible circuits with extremely fast speed--the average speed which synthesizes circuits with minimum cost is 365 times faster than that of best result.

International Conference on Natural Computation (ICNC)•Jan 1, 2008•1 citation

Fast algorithm for 4-qubit reversible logic circuits synthesis

Zhiqiang Li, Hanwu Chen, Baowen Xu +3 more

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.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2008•12 citations

An Algorithm for Synthesis of Optimal 3-qubit Reversible Circuits Based on Bit Operation

Zhiqiang Li, Hanwu Chen, Baowen Xu +2 more

We use bit operation to construct the novel and perfect Hash function and present an efficient algorithm which can construct optimal quantum reversible logic circuits with various types of gates by using the Hash table and produce quantum circuits with minimal cost in theory. Judging by the internationally recognized reversible functions of three variables, the algorithm not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm which synthesizes circuit with minimum length is 69.8 times that of currently best result [9].

International Conference on Genetic and Evolutionary Computing•Sep 1, 2008•2 citations

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
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.
We present an effective algorithm which can construct optimal 3-qubit reversible logic circuits for any given reversible logic gates and costs by constructing a minimal perfect hash function. We also present an algorithm which can automatically construct quantum gate library. In the experiments on 3-qubit synthesis, our algorithm synthesizes all optimal reversible circuits with extremely fast speed--the average speed which synthesizes circuits with minimum cost is 365 times faster than that of best result.
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.
We use bit operation to construct the novel and perfect Hash function and present an efficient algorithm which can construct optimal quantum reversible logic circuits with various types of gates by using the Hash table and produce quantum circuits with minimal cost in theory. Judging by the internationally recognized reversible functions of three variables, the algorithm not only synthesizes all optimal reversible logic circuits, but also runs extremely faster than other ones. The experimental results show that the average speed of the algorithm which synthesizes circuit with minimum length is 69.8 times that of currently best result [9].
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.