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

International Conference on Computer Supported Cooperative Work in Design (CSCWD)

Application of Semi-Template in Reversible Logic Circuit

Wenqian Li, Hanwu Chen, Zhiqiang Li

Published Apr 1, 2007• 1 citation
Publisher

Abstract

To improve the technique of optimizing reversible logic circuit and reduce the cost of reversible logic circuit, the template technology is analyzed, finding that Maslov's templates are incomplete in that the control lines are incomplete. By introducing the library of template control lines concept, templates are reconstructed and named semi-template. The semi-templates do not realize the identity function, but more valid templates can be produced dynamically using template producing rule. And based on this method, an algorithm is provided to optimize reversible logic circuit. Experimental data show that this method is more efficient and has higher rate of matching success in optimizing reversible logic circuit.

DOI
10.1109/cscwd.2007.4281457

Related papers

Algorithm of Optimizing Quantum Reversible Logic Synthesis

Zhiqiang Li, Wenqian Li, Hanwu Chen

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.

Journal of Software•Nov 13, 2009•0 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

Improved reversible logic synthesis algorithm based on weighted directed graph

Zhijin Guan

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.

Jisuanji gongcheng yu sheji•Jan 1, 2012•0 citations

Post synthesis optimization of reversible logic functions with extended template matching

H. V. Jayashree, V.K. Agrawal, N Shishir Bharadwaj

Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.

International Conference on Circuits, Control, Communication and Computing (I4C)•Nov 1, 2014•1 citation

Complete synthesis of identity templates for quantum and reversible logic MCT circuits using SAT-solvers and proposal of suboptimality witness notion

Adam Jagielski

In this study, we introduce a procedural generation technique for Identity Templates applicable to quantum and reversible logic circuits. These templates are recognized for their significant role in enhancing the efficiency of quantum and reversible logic optimization. Our approach enables the exhaustive synthesis of all potential templates up to a specified size. Leveraging the power of SAT-solver technology, we have verified the comprehensiveness of our template collections by confirming the full exploration of the search space. Additionally, we propose an innovative concept of Suboptimality Witnesses, which we anticipate will be instrumental in streamlining the search process in formal methods, akin to SAT-solvers, for the synthesis of reversible logic circuits.

International Journal of Electronics and Telecommunications•Jul 25, 2024•0 citations

Challenges and advances in Toffoli network optimisation

Gerhard W. Dueck

This study gives a brief overview of the current trends in reversible logic synthesis with emphasis on template matching. The basic building block for reversible circuits considered here is the multiple‐control Toffoli gate. Some approaches to synthesis are reviewed and the challenges are explained. Since many practical functions are not reversible, they must be embedded into reversible ones, if they are to be implemented using reversible logic. The complexity of such embeddings is expounded. A two phase synthesis is described where particular attention is devoted to the optimisation phase via template matching. Insights into the properties of the templates, have led to algorithms that aid the generation of templates. Until recently, the application of templates has been guided by different heuristics. A review of an exact template matching algorithm with a discussion of the implications of such an algorithm is given. Exact matching affects both the generation as well as the application of templates. Results from a prototype implementation are encouraging.

IET Computers & Digital Techniques•Sep 21, 2013•3 citations
To improve the technique of optimizing reversible logic circuit and reduce the cost of reversible logic circuit, the template technology is analyzed, finding that Maslov's templates are incomplete in that the control lines are incomplete. By introducing the library of template control lines concept, templates are reconstructed and named semi-template. The semi-templates do not realize the identity function, but more valid templates can be produced dynamically using template producing rule. And based on this method, an algorithm is provided to optimize reversible logic circuit. Experimental data show that this method is more efficient and has higher rate of matching success in optimizing reversible logic circuit.
最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.;The key of optimizing quantum reversible logic lies in automatically constructing quantum reversible logic circuits with the minimal quantum cost. In order to improve the efficiency of an automatic synthesis and optimization of the reversible logic, a semi-template technique and a fast algorithm was proposed. Template is an efficient optimizing tool, and the semi-template technique can significantly improve the matching efficiency in optimization. R-M synthesis arithmetic is a good iterative method in reversible logic synthesis. Based on the original idea of R-M arithmetic, by constructing an optimal and collision-free Hash function, a new fast algorithm for synthesizing the quantum reversible logic circuits was proposed. This algorithm can construct optimal quantum reversible logic circuits with various types of gates and quantum cost. The experimental results show that to the best of the knowledge in the same testing environment, the results are much better than others.
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.
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.
Research affinity towards Reversible Computing is increasing day to day due to its lower energy dissipation computing capability. To evaluate any reversible function it is necessary to build the system with reversible gates. In view of this there are many new reversible logic gates proposed by many authors. Quantum cost of few reversible gates are unpublished. Simplified version of transformation technique to synthesize new reversible gates with Fredkin and Toffoli gates network are presented in this paper. Post synthesis optimization with the new set of templates are carried out to reduce the Quantum cost.
In this study, we introduce a procedural generation technique for Identity Templates applicable to quantum and reversible logic circuits. These templates are recognized for their significant role in enhancing the efficiency of quantum and reversible logic optimization. Our approach enables the exhaustive synthesis of all potential templates up to a specified size. Leveraging the power of SAT-solver technology, we have verified the comprehensiveness of our template collections by confirming the full exploration of the search space. Additionally, we propose an innovative concept of Suboptimality Witnesses, which we anticipate will be instrumental in streamlining the search process in formal methods, akin to SAT-solvers, for the synthesis of reversible logic circuits.
This study gives a brief overview of the current trends in reversible logic synthesis with emphasis on template matching. The basic building block for reversible circuits considered here is the multiple‐control Toffoli gate. Some approaches to synthesis are reviewed and the challenges are explained. Since many practical functions are not reversible, they must be embedded into reversible ones, if they are to be implemented using reversible logic. The complexity of such embeddings is expounded. A two phase synthesis is described where particular attention is devoted to the optimisation phase via template matching. Insights into the properties of the templates, have led to algorithms that aid the generation of templates. Until recently, the application of templates has been guided by different heuristics. A review of an exact template matching algorithm with a discussion of the implications of such an algorithm is given. Exact matching affects both the generation as well as the application of templates. Results from a prototype implementation are encouraging.