Technical University of Munich
School of Computation, Information and Technology
Chair for Design Automation
Prof. Dr. Robert Wille
Arcisstrasse 21
80333 Munich | Germany
Tel: +49 89 289 23551

Google Maps Navigation

The Chair for Design Automation is supported by the Bavarian State Ministry for Science and Arts through the Distinguished Professorship Program.

Der Lehrstuhl für Design Automation wird durch das Bayerische Staatsministerium für Wissenschaft und Kunst im Rahmen des Spitzenprofessurenprogramms gefördert.

Bavarian Coat of Arms

↑ Quantum Computing

One Pass Design of Reversible Circuits

Reversible computation is a heavily investigated emerging technology due to its promising characteristics in low-power design, its application in quantum computations, and several further application areas. The currently established functional synthesis flow for reversible circuits is composed of two distinct steps. First, an embedding process is conducted which makes non-unique output patterns distinguishable by adding further variables. Then, this function is passed to a synthesis method which eventually yields a reversible circuit. However, the separate consideration of the embedding and synthesis tasks leads to significant drawbacks: In fact, embedding is not necessarily conducted in a fashion which is suited for the following synthesis process. In addition, embedding adds further variables to the function to be synthesized which exponentially increases its corresponding representation in the worst case.

Here, we propose one-pass design of reversible circuits, which combines embedding and synthesis. This allows for conducting synthesis with a high degree of freedom, since the embedding that suits best is inherently chosen during synthesis. We propose two solutions (an exact an a heuristic one) following this scheme that improve the currently established synthesis flow by magnitudes in terms of runtime – allowing to synthesize a reversible circuit with a minimum number of lines for some of the frequently considered benchmark functions for the first time. Furthermore, a significant reduction of the costs of the resulting circuits (up to several orders of magnitude) is achieved with this new design flow.

With this package we aim for demonstrating the potential of the newly introduced one-pass design flow for reversible circuits, rather than for a fully-optimized synthesized method. While our implementation is based on QMDD-based synthesis, we encourage users of this package to incorporated the one-pass design flow for further functional synthesis approaches.

The implementation (including a README with instructions) can be downloaded by clicking on this link (5.2 MB).

Details of the approach are summarized in the paper entitled “One-pass Design of Reversible Circuits: Combining Embedding and Synthesis of Reversible Logic”.


If you use the synthesis approach for your research, we will be thankful if you refer to it by citing the following publication:

  title={One-pass Design of Reversible Circuits: Combining Embedding and Synthesis for Reversible Logic},
  author={Zulehner, Alwin and Wille, Robert},
  journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
  volume= {37},


In case you have any problems with or questions feel free to contact us via