International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV)

Optimization of reversible circuits using triple-gate templates at quantum gate level

Pyreddy Mary Arpita, Kamalika Datta, Rohith Vemula, Indranil Sengupta

Published Jan 1, 2015• 2 citations

Abstract

The paper presents an approach for optimizing a reversible netlist consisting of multiple-control Toffoli (MCT) gates with the objective of reducing quantum cost. The MCT gates are first decomposed into smaller gates with up to three control lines, and then a template matching method is applied on the netlist for optimization. The templates are constructed by considering all possible 3-gate sequences with up to four lines. This work constitutes an extension of a previous work by Dueck et al., where 2-gate sequences were considered in the templates. The input gate netlists are generated from the reversible benchmarks available in RevLib, followed by Barenco decomposition to produce Toffoli gates with at most three control connections. The proposed approach is applied on these netlists, and the final quantum cost calculated. Experimental results on standard benchmarks show that the method can lead to reductions in quantum cost.

DOI: 10.1109/edcav.2015.7060551

Related papers

Quantum Cost Reduction of Reversible Circuits Using New Toffoli Decomposition Techniques

Md. Belayet Ali, Takashi Hirayama, Katsuhisa Yamanaka +1 more

Quantum cost is the most important criteria to evaluate reversible and quantum circuits. Also the fundamental building blocks of reversible and quantum circuits are Multiple-Control Toffoli (MCT) gates. The synthesis of MCT based reversible circuits are usually conducted into two steps. First, MCT circuits are decomposed into quantum circuits and then they are optimized using various techniques such as template matching, moving rules to reduce the quantum cost of reversible circuits. In this paper, we propose new techniques to decompose the Toffoli gates, in which MCT based circuits are mapped into a corresponding quantum realization. The main improvement is that the resulting quantum realization of MCT based circuits makes significantly better realization than those achieved in the earlier approaches and further reduction is possible using some other optimization techniques. Experimental results show that our new techniques enable to get sub-optimal realization of the MCT based reversible circuits in decomposition stage and quantum cost reduction of the reversible circuits is achieved by using that sub-optimal realization.

International Conference on Computational Science and Computational Intelligence (CSCI)Dec 1, 201518 citations

Reversible circuit optimization using modified toffoli templates

Mridula J Deshpande, H. V. Jayashree, V.K. Agrawal

Reversible gates are gaining popularity in the field of circuit synthesis due to their property of having lower power loss and reduced dissipation of power as heat. These low power design models need to have better optimization properties. In this paper, we have ventured into the template and rule based optimization process. While most reversible netlists are built using the standard Toffoli gates, the proposed Modified Toffoli Gate has been used to achieve optimization. In this paper, the quantum realization of mixed control Modified Toffoli Gate and negative control Modified Toffoli Gates are proposed. Few templates and rules for transforming the original Toffoli network to the Modified Toffoli network are also proposed. This optimization yields a better quantum cost and gate count when compared to that of it's Toffoli counterpart.

International Conference on Advances in Computing, Communications and Informatics (ICACCI)Sep 1, 20170 citations

Improved NCV Gate Realization of Arbitrary Size Toffoli Gates

Abhoy Kole, Kamalika Datta

The problem of synthesis and optimization of reversible and quantum circuits have drawn the attention of researchers in recent years. The typical design flow for such circuits first carries out the step of synthesis in terms of reversible gates, and then maps (decomposes) each reversible gate into equivalent set of quantum gates (e.g. from the NCV library). Since its initial proposal in realizing a Toffoli gate using quantum gates, several structural modifications have been proposed in the literature in order to reduce the cost of the generated netlist. The most recently introduced approach produces improved NCV cascade successively by partitioning the control lines of the given Toffoli gate in all possible ways, and replacing intermediate Toffoli gates with optimized equivalent NCV cascades form a catalog. In this approach the complexity of decomposing large Toffoli gates is high. In the present paper an efficient heuristic for partitioning the control lines of a given Toffoli gate is proposed. This heuristic is used for decomposition of the Toffoli gate without using any NCV catalog, after applying a template based optimization step. The cost of resultant circuit is similar to or sometimes better than the one reported by previous approaches.

International Conference on VLSI DesignJan 1, 201711 citations

Systematic Optimization of Quantum Circuits via Toffoli Permutation and Local Search

GEORGE PAPAKONSTANTINOU

The synthesis of efficient reversible logic circuits is critical for fault-tolerant quantum computing. While standard libraries often treat the Toffoli gate as an atomic unit, its realization in the NCV library requires decomposition into 5 elementary gates. In this work, we propose a novel, systematic four-phase optimization methodology. First, we generate an optimal circuit in the strict NCT library (NOT, CNOT, Toffoli) using automated synthesis. Second, we replace each Toffoli gate with a specific NCV decomposition, permuting the control lines such that the final internal CNOT gate matches the subsequent linear gate in the circuit, allowing us to apply a cancellation rule (X ·X = I). Finally, post-synthesis local searches are applied using Mixed- Integer Non-Linear Programming (MINLP) techniques to further reduce the total gate count. Applying this method to the MIG, TSG, and MKG gates, we achieve Quantum Costs of 7, 14, and 12 respectively, matching or beating the best-known literature benchmarks.

Apr 19, 20261 citation

Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition

Po-Wei Chen, Sheng-Tan Huang, Shao‐Yun Fang

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

ACM Transactions on Design Automation of Electronic SystemsJun 16, 20251 citation

Reversible Logic Circuit Synthesis for Quantum Computing via a Gate Pattern-based Optimization Model

Jihye Jung, In-Chan Choi

Quantum computing is the latest computing concept that can substantially reduce the computational burden of some difficult NP problems. Boolean reversible logic is frequently used as a key component in many quantum algorithms. This study proposes an approach based on a mixed integer programming model for reversible circuit synthesis. The proposed optimization model maps a given reversible function into a multiple-control Toffoli (MCT) circuit with minimum quantum costs. Our model exploits the relationship between MCT gate patterns and the operations on qubit states. We also report our experience in computational experiments on the circuit synthesis of reversible benchmark problems.

Journal of Korean Institute of Industrial EngineersAug 25, 20201 citation