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 Dallas Circuits and Systems Conference (DCAS)

Exact Toffoli Network Synthesis of Reversible Logic Using Boolean Satisfiability

Daniel J. Grosse, Xiaobo Chen, Rolf Drechsler

Published Oct 1, 2006• 10 citations
Publisher

Abstract

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.

DOI
10.1109/dcas.2006.321031

Related papers

Exact sat-based toffoli network synthesis

Daniel J. Grosse, Xiaobo Chen, Gerhard W. Dueck +1 more

Compact realizations of reversible logic functions are of interest in the design of quantum computers. 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 Toffoligates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable if there exists a network representation with d gates. Thus, we can guarantee minimality. In addition to fully specified reversible functions, the algorithm can be applied to incompletely specified functions. For a set of benchmarks experimental results are given.

ACM Great Lakes Symposium on VLSI (GLSVLSI)•Mar 11, 2007•50 citations

Fast exact toffoli network synthesis of reversible logic

Robert Wille, Daniel J. Grosse

The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude.

•Nov 1, 2007•21 citations

Fast exact Toffoli network synthesis of reversible logic

Robert Wille, Daniel J. Grosse

Abstract—The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude. I.

International Conference on Computer Aided Design•Nov 5, 2007•39 citations

Quantified synthesis of reversible logic

Robert Wille, Hoang M. Le, Gerhard W. Dueck +1 more

In the last years synthesis of reversible logic functions has emerged as an important research area. Other fields such as low-power design, optical computing and quantum computing benefit directly from achieved improvements. Recently, several approaches for exact synthesis of Toffoli networks have been proposed. They all use Boolean satisfiability to solve the underlying synthesis problem. In this paper a new exact synthesis approach based on Quantified Boolean Formula (QBF) satisfiability - a generalization of Boolean satisfiability - is presented. Besides the application of QBF solvers, we propose Binary Decision Diagrams to solve the quantified problem formulation. This allows to easily support different gate libraries during synthesis. In addition, all minimal networks are found in a single step and the best one with respect to quantum costs can be chosen. Experimental results confirm that the new technique is faster than the best previously known approach and leads to cheaper realizations in terms of quantum costs.

Design, Automation, and Test in Europe•Mar 10, 2008•42 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
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.
Compact realizations of reversible logic functions are of interest in the design of quantum computers. 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 Toffoligates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable if there exists a network representation with d gates. Thus, we can guarantee minimality. In addition to fully specified reversible functions, the algorithm can be applied to incompletely specified functions. For a set of benchmarks experimental results are given.
The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude.
Abstract—The research in the field of reversible logic is motivated by its application in low-power design, optical computing and quantum computing. Hence synthesis of reversible logic has become a very important research area in the last years. In this paper exact algorithms for the synthesis of generalized Toffoli networks are considered. We present an improvement of an existing synthesis approach that is based on Boolean Satisfiability. Furthermore, the principle limits of the original and the improved approach are shown. Then, we propose a new method using problem specific knowledge during the synthesis process to overcome these limits. Experimental results demonstrate improvements of the overall synthesis time up to four orders of magnitude. I.
In the last years synthesis of reversible logic functions has emerged as an important research area. Other fields such as low-power design, optical computing and quantum computing benefit directly from achieved improvements. Recently, several approaches for exact synthesis of Toffoli networks have been proposed. They all use Boolean satisfiability to solve the underlying synthesis problem. In this paper a new exact synthesis approach based on Quantified Boolean Formula (QBF) satisfiability - a generalization of Boolean satisfiability - is presented. Besides the application of QBF solvers, we propose Binary Decision Diagrams to solve the quantified problem formulation. This allows to easily support different gate libraries during synthesis. In addition, all minimal networks are found in a single step and the best one with respect to quantum costs can be chosen. Experimental results confirm that the new technique is faster than the best previously known approach and leads to cheaper realizations in terms of quantum costs.
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.