Reversible and Quantum Circuits

Robert Wille, Mathias Soeken, C. Otterstedt +1 more

The efficient 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 position 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.

Michael D. Miller, Mitchell Aaron Thornton

Mousum Handique, Aayush Sonkar

In recent years, quantum computing has gained a lot of importance due to its property of increasing computational power exponentially. In the current literature, it has observed that the quantum computing has potential to solve many complex problems with less complexity based on the theoretical analysis. But in contrast to hardware implementation of quantum technology, it expands in a linear way. Moreover, there is a close relation between quantum computing and reversible computing. More precisely, quantum computing operations are reversible. In this paper, we propose an extended approach of mapping flow for describing reversible circuits to its equivalent quantum circuits. Here, we consider the reversible circuits of n-inputs and n-outputs with NCT and GT library, which is mapped to the quantum circuits with the NCV-|v1〉 library. Finally, we provide our experimental results in terms of quantum costs for mapping the reversible circuits to quantum circuits.

Chia-Chun Lin

Colin P. Williams

Zahra Sasanian

Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits.