One approach to determining a quantum circuit is to first synthesize a circuit composed of binary reversible gates and to then map that circuit to an equivalent quantum gate realization. This paper considers the mapping phase with the goal of reducing the number of quantum gates required. Our method is based on novel line labeling and gate moving procedures. Results are presented for the quantum library: NOT, controlled-NOT, and the square-root-of-NOT gates (V and V+). The approach is applicable to other quantum gate libraries.
One approach to determining a quantum circuit is to first synthesize a circuit composed of binary reversible gates and to then map that circuit to an equivalent quantum gate realization. This paper considers the mapping phase with the goal of reducing the number of quantum gates required. Our method is based on novel line labeling and gate moving procedures. Results are presented for the quantum library: NOT, controlled-NOT, and the square-root-of-NOT gates (V and V+). The approach is applicable to other quantum gate libraries.
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.
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.
Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.
This paper reviews recent developments on mapping reversible circuits to libraries of elementary quantum gates. The emphasis is on optimization of both the initial reversible circuit and the resulting quantum circuit. At the quantum level, improved realizations of single mixed-polarity multiple-control Toffoli gates are presented as well as techniques for performing quantum gate optimizations across Toffoli gate boundaries. Experimental results show the effectiveness of the methods presented using circuits from the REVLIB benchmark suite.
Since non-permutative quantum gates have more complex rules than permutative quantum gates, it is very hard to synthesize quantum logic circuits using non-permutative quantum gates, such as controlled-square-root-of-NOT gates (CV∕CV+ gates). In the efficient synthesis algorithm, direct use of quantum non-permutative gates should be avoided. Rather, the key method is to use quantum gates to create new permutative quantum gates that then replace non-permutative quantum gates. This method assumes the library of quantum gate primitives are constructed so as to have the lowest possible quantum cost. In this paper, we first propose some new CV∕CV+-like gates, i.e. controlled-kth-root-of-NOT gates where k = 2,4,8,…, and give all corresponding matrixes. Further, we also present a novel generic method to quickly and directly construct this new optimal quantum logic gate library using CNOT and these non-permutative quantum gates. Our method introduces new means to find permutative quantum gates with lower quantum cost.
Motivated by the prospects of quantum computation, the design of quantum circuits received significant attention in the recent past. Due to the complex representation of the underlying quantum mechanical phenomena, a two-stage design flow was established in which the desired functionality is first realized in terms of a reversible circuit and, afterwards, mapped into an equivalent quantum circuit. This paper proposes a new metric for estimating nearest neighbor cost at the reversible circuit level. Research works are mostly carried out considering nearest neighbor constraints at the quantum circuit level. Various quantum gate libraries and mapping schemes have been reported in the literature to realize the circuit operation at quantum level. One such mapping scheme exploiting a well established quantum gate library (NCV) is explored in defining the cost metric. Experimental evaluations confirmed both the accuracy as well as the applicability of the proposed metric.