Alwin Zulehner, Robert Wille,
"Make It Reversible: Efficient Embedding of Non-reversible Functions"
: Design, Automation and Test in Europe (DATE), Seite(n) 458-463, 2017
Make It Reversible: Efficient Embedding of Non-reversible Functions
Sprache des Titels:
Design, Automation and Test in Europe (DATE)
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.