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”.
References
If you use the synthesis approach for your research, we will be thankful if you refer to it by citing the following publication:
@article{zulehner2018one,
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},
year={2018},
volume= {37},
number={5},
pages={996--1008},
year={2018}
}
Contact
In case you have any problems with or questions feel free to contact us via quantum.cda@xcit.tum.de.