Great progress has been made in the development of computing machines. The tremendous achievements in the last 20-30 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 low-power technology where reversible circuits are particularly suited for, (3) encoding/decoding and encryption/decryption devices, which always realize one-to-one 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 two-level descriptions such as Exclusive Sum of Products (ESOPs) or graph-based 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 two-level AND/XOR representations and graph-based 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 domain-specific cost metrics such as quantum cost
- Development of synthesis/optimization approaches based on probabilistic methods such as simulated annealing or evolutionary algorithms