Improving the Mapping of Reversible Circuits to Quantum Circuits Using Multiple Target Lines

Robert Wille; Mathias Soeken; Christian Otterstedt; Rolf Drechsler

In: 18th Asia and South Pacific Design Automation Conference. Asia and South Pacific Design Automation Conference (ASP-DAC-2013), 18th, January 22-25, Yokohama, Japan, IEEE, 2013.


The effcient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the po- sition of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence