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 Symposium on Electronic System Design

Synthesis of Toffoli Networks: Status and Challenges

Gerhard W. Dueck

Published Dec 1, 2012• 3 citations
Publisher

Abstract

This paper gives a brief overview of the current trends in reversible logic synthesis. The basic building block for reversible circuits considered here is the multiple-control Toffoli gate. Some approaches to synthesis are reviewed and 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 were particular attention is devoted to the optimization phase via template matching.

DOI
10.1109/ised.2012.26

Related papers

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

Toffoli network synthesis with templates

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 24, 2005•228 citations

Simplification of Toffoli networks via templates

Dmitri Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with Ñ gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for Ñ � � are described in this paper. 1

Symposium on Integrated Circuits and Systems Design•Sep 8, 2003•44 citations

Templates for Toffoli Network Synthesis

Dmitri Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Tooli networks can be divided into two steps. First, nd a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for m 7a re described in this paper.

•Jan 1, 2003•11 citations

Simplification of Toffoli networks via templates

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired junction. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for m/spl les/7 are described in this paper.

Symposium on Integrated Circuits and Systems Design•Jan 23, 2004•35 citations

Fredkin/Toffoli templates for reversible logic synthesis

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.

International Conference on Computer Aided Design•May 13, 2004•23 citations
This paper gives a brief overview of the current trends in reversible logic synthesis. The basic building block for reversible circuits considered here is the multiple-control Toffoli gate. Some approaches to synthesis are reviewed and 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 were particular attention is devoted to the optimization phase via template matching.
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.
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with Ñ gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for Ñ � � are described in this paper. 1
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Tooli networks can be divided into two steps. First, nd a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for m 7a re described in this paper.
Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired junction. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the second step. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for m/spl les/7 are described in this paper.
Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.