Hierarchical Synthesis of Quantum and Reversible Architectures

Reversible hardware finds application in emerging areas such as low power circuit design, quantum computing, optical computing, and DNA computing. Intensive research has recently focused on the synthesis of quantum and reversible architectures. Quantum architectures often take advantage of reversible circuit synthesis methods but in general they require dedicated synthesis approaches because they represent a more general computing paradigm. Most of these quantum and reversible synthesis approaches derive efficient or even optimal circuits with scalability being their major drawback: they can only handle small circuits (up to a few hundred inputs for the most promising ones). In this paper, we propose a graph-based hierarchical synthesis method for large reversible and quantum architectures which can be combined with any of the existing synthesis methods to deliver unlimited scalability in synthesizing arbitrary large and irregular architectures. The specification of any complex function is provided in the form of a sequential algorithm consisting of primitive pre-synthesized operations available in a library. The components of the library may have been designed by ad-hoc methods or synthesized by the known methods in the literature or even by the proposed synthesis procedure. The synthesized architecture is represented as a dependence graph whose nodes correspond to the available components of the library and their respective inverses so as no garbage remains at the output. The method can be recursively applied at multiple levels to build any complex reversible or quantum architecture.