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

Jisuanji gongcheng yu sheji

Improved reversible logic synthesis algorithm based on weighted directed graph

Zhijin Guan

Published Jan 1, 2012• 0 citations
OpenAlex

Abstract

To reduce the number of reversible gates used in the reversible logic synthesis,by analyzing the reversible logic synthesis algorithm based on the weighted direction gragh(WDG),the number of transitional gates in the process of function transformation is more and the optimization algorithm is simple,so the concept of efficient complexity-equal primitive output transformation(POT) is proposed,the moving and simplification rules for Toffoli gate sequence are expanded and proven,and the improved synthesis algorithm based on WDG is given.Experimental results show that the improved algorithm can not only reduce the number of reversible gates during circuit generation,but also optimize the generated circuit effectively,the number of gates and control bits is reduced greatly,and the circuit cost is decreased.

Related papers

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

Reversible Logic Synthesis Algorithm Based on Decreasing Complexity

Xueyun Cheng, Zhijin Guan, Zhu, Lingling

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...

ASME Press eBooks•Jan 1, 2012•0 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

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

The Analysis and Metric Algorithm of Delay in Reversible Network

Haibao Zhang, Zhijin Guan, Lu Cangang

Delay is an important parameter that needs to be considered in the reversible logic designs, but not much work on delay in reversible network has been done at present. This paper presents an algorithm to calculate delay of reversible network. In the process of calculating delay, we not only take the complexity of different logic gates into consideration, but also the relationship between the output delay of the target bits and all inputs delay of the controlled reversible logic gates is considered. We use the algorithm to calculate the delay in reversible logic circuits synthesized and optimized by several different reversible logic synthesis methods. Then we analyze the performance of these reversible logic synthesis methods in delay level. Through the comparative analysis, we prove that these reversible logic synthesis methods for some function in reducing quantum cost have a good effect, but not in delay level. The quantum cost of some reversible logic circuits which have the same function is less, however the delay may not.

International Conference on Digital Manufacturing & Automation•Jul 1, 2012•0 citations

An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition

Hochang Lee, Kyung Chul Jeong, Daewan Han +1 more

An algorithm for reversible logic synthesis is proposed. The task is, for a given n -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with m control bits, where \(m \in \lbrace 0, \ldots , n-1\rbrace\) . Controlled gates with large m (> 2) are then further decomposed into smaller gates ( \(m \le 2\) ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal. The main idea is to view an n -bit substitution map as a rank-2 n tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2 n -2) tensor and the 2× 2 identity matrix. It can then be seen that the transformed map acts nontrivially on n -1 bits only, meaning that the map to be synthesized becomes ( n -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2× 2 matrices. The time complexity of the algorithm is exponential in n , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large n , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.

arXiv:2107.04298•ACM Transactions on Quantum Computing•Jun 18, 2024•5 citations
To reduce the number of reversible gates used in the reversible logic synthesis,by analyzing the reversible logic synthesis algorithm based on the weighted direction gragh(WDG),the number of transitional gates in the process of function transformation is more and the optimization algorithm is simple,so the concept of efficient complexity-equal primitive output transformation(POT) is proposed,the moving and simplification rules for Toffoli gate sequence are expanded and proven,and the improved synthesis algorithm based on WDG is given.Experimental results show that the improved algorithm can not only reduce the number of reversible gates during circuit generation,but also optimize the generated circuit effectively,the number of gates and control bits is reduced greatly,and the circuit cost is decreased.
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.
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.
Delay is an important parameter that needs to be considered in the reversible logic designs, but not much work on delay in reversible network has been done at present. This paper presents an algorithm to calculate delay of reversible network. In the process of calculating delay, we not only take the complexity of different logic gates into consideration, but also the relationship between the output delay of the target bits and all inputs delay of the controlled reversible logic gates is considered. We use the algorithm to calculate the delay in reversible logic circuits synthesized and optimized by several different reversible logic synthesis methods. Then we analyze the performance of these reversible logic synthesis methods in delay level. Through the comparative analysis, we prove that these reversible logic synthesis methods for some function in reducing quantum cost have a good effect, but not in delay level. The quantum cost of some reversible logic circuits which have the same function is less, however the delay may not.
An algorithm for reversible logic synthesis is proposed. The task is, for a given n -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with m control bits, where m∈{0,…,n−1}m \in \lbrace 0, \ldots , n-1\rbracem∈{0,…,n−1} . Controlled gates with large m (> 2) are then further decomposed into smaller gates ( m≤2m \le 2m≤2 ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal. The main idea is to view an n -bit substitution map as a rank-2 n tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2 n -2) tensor and the 2× 2 identity matrix. It can then be seen that the transformed map acts nontrivially on n -1 bits only, meaning that the map to be synthesized becomes ( n -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2× 2 matrices. The time complexity of the algorithm is exponential in n , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large n , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.