Determining the minimal number of lines for large reversible circuits

Robert Wille, Oliver Keszöcze, Rolf Drechsler

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

40 Scopus citations

Abstract

Synthesis of reversible circuits is an active research area motivated by its applications e.g. in quantum computation or low-power design. The number of used circuit lines is thereby a crucial criterion. In this paper, we introduce several methods (including a theoretical upper bound) for the efficient computation or at least approximation of the minimal number of lines needed to realize a given function in reversible logic. While the proposed exact approach requires a significant amount of run-time (exponential in the worst case), the heuristic methods lead to very precise approximations in very short run-time. Using this, it can be shown that current synthesis approaches for large functions are still far away from producing optimal circuits with respect to the number of lines.

Original languageEnglish
Title of host publicationProceedings - Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Pages1204-1207
Number of pages4
StatePublished - 2011
Externally publishedYes
Event14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011 - Grenoble, France
Duration: 14 Mar 201118 Mar 2011

Publication series

NameProceedings -Design, Automation and Test in Europe, DATE
ISSN (Print)1530-1591

Conference

Conference14th Design, Automation and Test in Europe Conference and Exhibition, DATE 2011
Country/TerritoryFrance
CityGrenoble
Period14/03/1118/03/11

Fingerprint

Dive into the research topics of 'Determining the minimal number of lines for large reversible circuits'. Together they form a unique fingerprint.

Cite this