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

ASME Press eBooks

Reversible Logic Synthesis Algorithm Based on Decreasing Complexity

Xueyun Cheng, Zhijin Guan, Zhu, Lingling

Published Jan 1, 2012• 0 citations
Publisher

Abstract

In order to reduce the scale of the generated reversible network, we present the concept of effective complexity-equal exchanging POT and splitting POT, and propose novel techniques for the synthesis of reversible networks of Toffoli gates. The interchanging and merging gates strategies in reversible network and relevant proofs are given, furthermore, we put forward the valid simplification method of a reversible network. The experimental results on all 3-bit and part of 4-bit reversible functions show that the proposed synthesis algorithm and simplification method have better performance in reducing reversible gate count as well as control bit count compared to other...

DOI
10.1115/1.859971.paper119

Related papers

A novel Toffoli network synthesis algorithm for reversible logic

Yexin Zheng, Chao Huang

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2009•12 citations

A novel Toffoli network synthesis algorithm for reversible logic

Yexin Zheng, Chao Huang

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 19, 2009•20 citations

Rule-based Optimization of Reversible Toffoli Circuits

Xueyu Cheng

Optimization of reversible circuits is one of key problems of reversible logic synthesis.To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules.The algorithm examines the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does' t change.The algorithm is irrelevant to the number of input lines,does' t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s3),which is superior to O(n!t2s3)of generally used template optimization technique.Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.

•Jan 1, 2013•0 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•379 citations

A simplification algorithm for reversible logic network of positive/negative control gates

Xueyun Cheng, Zhijin Guan, Wei Wang +1 more

To further simplify the reversible circuit cascaded by positive/negative control (PNC) gates, new merging, moving and splitting rules of PNC gates were proposed in the paper, and these rules have been proved correct by way of logic algebra. We gave a novel simplification algorithm for reversible logic network of PNC gates by utilizing these rules. Experimental results on all 3-bit reversible functions show that our simplification algorithm is effective, it can decrease the gate count as well as the number of control bits compared to some known results, which were yielded by two excellent heuristic methods. Because the proposed rules have the generality, our simplification algorithm can be easily extended to reversible functions with more number of input bits.

International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)•May 1, 2012•8 citations

Sorting Network for Reversible Logic Synthesis

Md. Saiful Islam, Md. Rafiqul Islam, Abdullah Al Mahmud +1 more

In this paper, we have introduced an algorithm to implement a sorting network for reversible logic synthesis based on swapping bit strings. The algorithm first constructs a network in terms of n*n Toffoli gates read from left to right. The number of gates in the circuit produced by our algorithm is then reduced by template matching and removing useless gates from the network. We have also compared the efficiency of the proposed method with the existing ones.

arXiv:1008.3694•Aug 22, 2010•4 citations
In order to reduce the scale of the generated reversible network, we present the concept of effective complexity-equal exchanging POT and splitting POT, and propose novel techniques for the synthesis of reversible networks of Toffoli gates. The interchanging and merging gates strategies in reversible network and relevant proofs are given, furthermore, we put forward the valid simplification method of a reversible network. The experimental results on all 3-bit and part of 4-bit reversible functions show that the proposed synthesis algorithm and simplification method have better performance in reducing reversible gate count as well as control bit count compared to other...
Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.
Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.
Optimization of reversible circuits is one of key problems of reversible logic synthesis.To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules.The algorithm examines the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does' t change.The algorithm is irrelevant to the number of input lines,does' t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s3),which is superior to O(n!t2s3)of generally used template optimization technique.Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.
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
To further simplify the reversible circuit cascaded by positive/negative control (PNC) gates, new merging, moving and splitting rules of PNC gates were proposed in the paper, and these rules have been proved correct by way of logic algebra. We gave a novel simplification algorithm for reversible logic network of PNC gates by utilizing these rules. Experimental results on all 3-bit reversible functions show that our simplification algorithm is effective, it can decrease the gate count as well as the number of control bits compared to some known results, which were yielded by two excellent heuristic methods. Because the proposed rules have the generality, our simplification algorithm can be easily extended to reversible functions with more number of input bits.