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.
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.
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.
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.
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.
In order to efficiently automatically construct quantum reversible logic circuits with low cost,a novel method for quantum circuit's synthesis is proposed.Through the line topology transformation and truth table permutation,it converts an n-qubit circuit synthesis problem into single quantum circuit synthesis using traditional recursive thought.Then directly generate relevant circuit.After optimization,the quantum reversible logic circuit is synthesized finally.All 3-qubit reversible logic circuits have been synthesized by this method.The average number of EGT gates is only 6.41,and the number is down to 5.22 after optimization.Experimental results show that the number of gates to construct reversible logic circuits is less than other methods.For any n-qubit binary logic function,the number of EGT gates is less than n2n-1.Meanwhile,it voids the exponential nature of the memory or run-time complexity,and is very simple to implement in classical computer.
In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.