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)

Bidirectional matrix-based algorithm for 4-qubit reversible logic circuits synthesis

Dong Wang, Hanwu Chen, Wanning Zhu

Published Jul 1, 2010• 3 citations
Publisher

Abstract

Quantum reversible logic circuits synthesis is one of the key technologies to construct quantum computer. The algebraic model for quantum information processing is a unitary matrix operator. Matrix can better reflect the quantum state evolution and the properties of quantum computation. Bidirectional matrix-based algorithm for quantum reversible logic circuits synthesis is proposed in this paper. The matrix representation of quantum reversible circuit and the circuit transformation rules of adjacent matrix are employed to construct any quantum reversible circuit in this paper. Compared with, the computational complexity of our algorithm has been decreased exponentially and the speed has been increased by about 105times. In addition, the types of the quantum reversible circuits synthesized by our algorithm are extended from only even permutations in to even and odd ones. we have synthesized 13!=6227020800 quantum reversible circuits, which can't be done by other algorithms.

DOI
10.1109/cec.2010.5586417

Related papers

Matrix-based algorithm for 4-Qubit reversible circuits synthesis

Dong Wang, Shengyao Sun, Hanwu Chen

The mathematical model of the quantum reversible circuits is unitary matrix. Matrix can better reflect the quantum state evolution and further reflect the physical properties of the quantum computation. Matrix transformation based algorithm for 4-qubit reversible logic circuits synthesis is proposed in this paper. The algorithm skillfully uses the matrix representation of the quantum circuit and the circuit of the adjacent matrix to construct 4-qubit circuit with lower cost.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 13, 2013•0 citations

Qubits Reversible Logic Circuits Synthesis Based on Bisection Method

Dong Wang

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.

Dianzi xuebao•Jan 1, 2012•0 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

A novel quantum Boolean circuit synthesis method using matrix elementary transformations

Guangjun Xie

Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.

Chinese Journal of Quantum Electronics•Jan 1, 2011•0 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

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
Quantum reversible logic circuits synthesis is one of the key technologies to construct quantum computer. The algebraic model for quantum information processing is a unitary matrix operator. Matrix can better reflect the quantum state evolution and the properties of quantum computation. Bidirectional matrix-based algorithm for quantum reversible logic circuits synthesis is proposed in this paper. The matrix representation of quantum reversible circuit and the circuit transformation rules of adjacent matrix are employed to construct any quantum reversible circuit in this paper. Compared with, the computational complexity of our algorithm has been decreased exponentially and the speed has been increased by about 105times. In addition, the types of the quantum reversible circuits synthesized by our algorithm are extended from only even permutations in to even and odd ones. we have synthesized 13!=6227020800 quantum reversible circuits, which can't be done by other algorithms.
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.
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].
Quantum Boolean circuit is an interdisciplinary subject between classical reversible computing and quantum computing.It is of great significance to find a synthesis method of quantum Boolean circuit. A novel hybrid synthesis method is proposed which is based on the elementary transformation of matrices. Toffoli gate set is chosen as the basis gate library.Each logic gate in the library is a unitary matrix that can be decomposed into a product of a series of elementary transformation which is referred to a transformation path.Combined with some heuristics,the circuit structure composing of Toffoli gates can be constructed from the transformation path.In the end,a 3-qubit Boolean circuit is synthesized through the new method.
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.
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.