Open AccessChallenges and advances in Toffoli network optimisation
Author(s) -
Dueck Gerhard W.
Publication year - 2014
Publication title -
iet computers and digital techniques
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.219
H-Index - 46
ISSN - 1751-861X
DOI - 10.1049/iet-cdt.2013.0055
Subject(s) - template , toffoli gate , computer science , heuristics , matching (statistics) , combinatory logic , computer engineering , theoretical computer science , algorithm , quantum gate , programming language , mathematics , quantum computer , quantum , statistics , physics , quantum mechanics , operating system
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.