
Great progress has been made in the development of computing machines. The tremendous achievements in the last 2030 years yield a design flow which enables the design of circuits and systems composed of millions of components. However, from the beginning researchers and engineers narrowed the investigation of computing machines down to a preponderantly irreversible computing paradigm. While mainly relying on this conventional way of computation, alternative paradigms and their applications have hardly been considered and exploited yet.
A promising alternative is based on reversible computation, a computing paradigm which only allows bijective operations. Although not so well established yet, reversible computation enables several promising applications and, indeed, superiors conventional computation paradigms in many domains. Examples include (1) low power computation, where the fact that no information is lost in reversible computation can be exploited, (2) adiabatic circuits, a special lowpower technology where reversible circuits are particularly suited for, (3) encoding/decoding and encryption/decryption devices, which always realize onetoone mappings, (4) quantum computation, which enables to solve many relevant problems significantly faster than conventional circuits and is inherently reversible, and (5) program inversion.
With this motivation, design and synthesis of reversible circuits received significant attention and led to initial solutions  many of them relying on functional descriptions. Examples include twolevel descriptions such as Exclusive Sum of Products (ESOPs) or graphbased descriptions such as Binary Decision Diagrams (BDDs). However, compared with the power of corresponding approaches aiming at the synthesis of conventional circuits, the design of reversible circuits is at a very nascent stage.
In this project, this gap is closed by conducting joint research on the following issues:
 Development of improved function descriptions such as twolevel AND/XOR representations and graphbased representations that explicitly exploit the reversibility
 Development of synthesis approaches for reversible circuits utilizing the newly developed function descriptions
 Development of functional decomposition techniques for reversible functions considering domainspecific cost metrics such as quantum cost
 Development of synthesis/optimization approaches based on probabilistic methods such as simulated annealing or evolutionary algorithms
