Improving Synthesis of Reversible Circuits: Exploiting Redundancies in Paths and Nodes of QMDDs
Sprache des Vortragstitels:
Conference on Reversible Computation
Sprache des Tagungstitel:
In recent years, reversible circuits have become an established
emerging technology through their variety of applications. Since
these circuits employ a completely different structure from conventional
circuitry, dedicated functional synthesis algorithms have been proposed.
Although scalability has been achieved by using approaches based on
decision diagrams, the resulting circuits employ a significant complexity
measured in terms of quantum cost. In this paper, we aim for a reduction
of this complexity. To this end, we review QMDD-based synthesis.
Based on that, we propose optimizations that allow for a substantial reduction
of the quantum costs by jointly considering paths and nodes in
the decision diagram that employ a certain redundancy. In fact, in our
experimental evaluation, we observe substantial improvements of up to
three orders of magnitudes in terms of runtime and up to six orders of
magnitudes (a factor of one million) in terms of quantum cost.