Publication
Synthesis of Reversible Circuits with Minimal Lines for Large Functions
Mathias Soeken; Robert Wille; Christoph Hilken; Nils Przigoda; Rolf Drechsler
In: Conference Proceedings. Asia and South Pacific Design Automation Conference (ASP-DAC-12), 17th, January 30 - February 2, Sydney, New South Wales, Australia, 2012.
Abstract
Reversible circuits are an emerging technology
where all computations are performed in an invertible manner.
Motivated by their promising applications, e.g. in the domain of
quantum computation or in the low-power design, the synthesis
of such circuits has been intensely studied. However, how to automatically
realize reversible circuits with the minimal number of
lines for large functions is an open research problem.
In this paper, we propose a new synthesis approach which relies
on concepts that are complementary to existing ones. While “conventional”
function representations have been applied for synthesis
so far (such as truth tables, ESOPs, BDDs), we exploit Quantum
Multiple-valued Decision Diagrams (QMDDs) for this purpose.
An algorithm is presented that performs transformations
on this data-structure eventually leading to the desired circuit.
Experimental results show the novelty of the proposed approach
through enabling automatic synthesis of large reversible functions
with the minimal number of circuit lines. Furthermore, the quantum
cost of the resulting circuits is reduced by 50% on average
compared to an existing state-of-the-art synthesis method.