Make It Reversible: Efficient Embedding of Non-reversible Functions
Alwin Zulehner1,a and Robert Wille1,2,b
1Institute for Integrated Circuits, Johannes Kepler University, Linz, Austria.
aalwin.zulehner@jku.at
brobert.wille@jku.at
2Cyber-Physical Systems, DFKI GmbH, Bremen, Germany
ABSTRACT
Reversible computation became established as a promising concept due to its application in various areas like quantum computation, energy-aware circuits, and further areas. Unfortunately, most functions of interest are non-reversible. Therefore, a process called embedding has to be conducted to transform a non-reversible function into a reversible one - a coNP-hard problem. Existing solutions suffer from the resulting exponential complexity and, hence, are limited to rather small functions only. In this work, an approach is presented which tackles the problem in an entirely new fashion. We divide the embedding process into matrix operations, which can be conducted efficiently on a certain kind of decision diagram. Experiments show that improvements of several orders of magnitudes can be achieved using the proposed method. Moreover, for many benchmarks exact results can be obtained for the first time ever.
