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

Advanced materials research

Iterative Construct of Reversible Network Based on Cascade Operation

Yi Qing Zhang, Zhi Jin Guan, Can Gang Lu, Jin Feng He

Published Sep 1, 2013• 0 citations
Publisher

Abstract

Reversible logic synthesis has become a fast developing area. In order to construct reversible logic gate network, this paper presents an algorithm of iterative construct reversible network by cascade operation. The cascade operation was implemented with Boolean permutation. We proposed two important decision condition of Boolean permutation, and changed to choose balance function of suffice Boolean permutation condition for the problem of construct reversible network. The result of algorithm analysis show that it is can be implemented fleetly.

DOI
10.4028/www.scientific.net/amr.798-799.419

Related papers

The Reversible Network Cascade Based on Reversible Logic Gate Coding Method

Hui Li, Zhijin Guan, Shanli Chen +1 more

Reversible computing is an emerging area of research and reversible logic synthesis is its important aspect. This paper provides reversible network cascade method based on reversible logic gate coding method. According to the number of vertical lines and control bits, which from small to large, the method constructs automatically the different output vectors corresponding network meanwhile the algorithm can generate all the reversible network. Compared with the three variables reversible function test in benchmark, its control gates amounts are much less and the cost is much lower.

International Conference on Information Assurance and Security (IAS)•Jan 1, 2009•1 citation

Reversible network cascade based on permutation group

Yanming Lü

By means of analyzing the equivalence relation of reversible gate logic network to permutation group,the reversible gate network cascade was converted into the cycle of symmetric group.It was verified that any neighboring 3-cycle permutation (u,s,t) could be generated by four(n-2)-CNOT gates and 2n NOT gates at least.Thus,n-digit even bivariate reversible network could be constructed with NOT and 2-CNOT gates.A constructing method of reversible network cascade was proposed by means of permutation of cycle of symmetric group.The validity of this method was verified by an example.The result showed that the network was without garbage output.Meantime,the trigger of the reversible gate was even more flexible and effective.

Journal of Lanzhou University of Technology•Jan 1, 2008•0 citations

Construction of reversible network-based the anti-sequence of natural number pair

Yueqin Hang, Zhijin Guan, Lei Yang

Reversible computing is an emerging area of research and reversible logic synthesis is its important aspect. This paper proposed the reversible logic gate network cascade method-based the anti-sequence of natural number pair, which can generate single reversible network or the batching continuous sequence numbers reversible network. Compared with examples of the benchmark, the number of control-bit and the number of the reversible logic gates have been improved to some degree.

International Conference on Computer and Communication Technologies in Agriculture Engineering•Jun 1, 2010•0 citations

Network Structure Cascade for Reversible Logic

Zhijin Guan, Xiaolin Qin, Yi-Qing Zhang +1 more

A reversible logic function maps each of the 2m input patterns to a unique output pattern. The network cascade structure problem is to realize a reversible function by a cascade of primitive reversible gates. We present a method that synthesizes a network with family of Toffoli gates. The cascade algorithm finds cascade of Toffoli gates with no backtracking and minimal look-ahead, and apply transformations that reduce the number of gates in the network. We have synthesized all three input and output reversible functions and compare our results to the other optimal results. We also present the results of applying our synthesis method to obtain networks for number of benchmark function.

International Conference on Natural Computation (ICNC)•Jan 1, 2007•2 citations

Exact Toffoli Network Synthesis of Reversible Logic Using Boolean Satisfiability

Daniel J. Grosse, Xiaobo Chen, Rolf Drechsler

Compact synthesis results for reversible logic is of major interest in low-power design and quantum computing. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoli gates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable iff there exists a network representation with d gates. Thus we can guarantee minimality. For a set of benchmarks experimental results are given.

IEEE Dallas Circuits and Systems Conference (DCAS)•Oct 1, 2006•10 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 30, 2006•371 citations
Reversible logic synthesis has become a fast developing area. In order to construct reversible logic gate network, this paper presents an algorithm of iterative construct reversible network by cascade operation. The cascade operation was implemented with Boolean permutation. We proposed two important decision condition of Boolean permutation, and changed to choose balance function of suffice Boolean permutation condition for the problem of construct reversible network. The result of algorithm analysis show that it is can be implemented fleetly.
Reversible computing is an emerging area of research and reversible logic synthesis is its important aspect. This paper provides reversible network cascade method based on reversible logic gate coding method. According to the number of vertical lines and control bits, which from small to large, the method constructs automatically the different output vectors corresponding network meanwhile the algorithm can generate all the reversible network. Compared with the three variables reversible function test in benchmark, its control gates amounts are much less and the cost is much lower.
By means of analyzing the equivalence relation of reversible gate logic network to permutation group,the reversible gate network cascade was converted into the cycle of symmetric group.It was verified that any neighboring 3-cycle permutation (u,s,t) could be generated by four(n-2)-CNOT gates and 2n NOT gates at least.Thus,n-digit even bivariate reversible network could be constructed with NOT and 2-CNOT gates.A constructing method of reversible network cascade was proposed by means of permutation of cycle of symmetric group.The validity of this method was verified by an example.The result showed that the network was without garbage output.Meantime,the trigger of the reversible gate was even more flexible and effective.
A reversible logic function maps each of the 2m input patterns to a unique output pattern. The network cascade structure problem is to realize a reversible function by a cascade of primitive reversible gates. We present a method that synthesizes a network with family of Toffoli gates. The cascade algorithm finds cascade of Toffoli gates with no backtracking and minimal look-ahead, and apply transformations that reduce the number of gates in the network. We have synthesized all three input and output reversible functions and compare our results to the other optimal results. We also present the results of applying our synthesis method to obtain networks for number of benchmark function.
Compact synthesis results for reversible logic is of major interest in low-power design and quantum computing. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoli gates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable iff there exists a network representation with d gates. Thus we can guarantee minimality. For a set of benchmarks experimental results are given.
Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25