Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Design, Automation, and Test in Europe

Combining SWAPs and Remote Toffoli Gates in the Mapping to IBM QX Architectures

Philipp Niemann, Chandan Bandyopadhyay, Rolf Drechsler

Published Feb 1, 2021• 10 citations
Publisher

Abstract

Quantum computation received a steadily growing attention in recent years, especially supported by the emergence of publicly available quantum computers like the popular IBM QX series. In order to execute a reversible or quantum circuit on those devices, a mapping is required that replaces each reversible or quantum gate by an equivalent cascade of elementary, i.e. directly executable, gates-a task which tends to induce a significant mapping overhead. Several approaches have been proposed for this task which either rely on the swapping of physically adjacent qubits or the use of precomputed templates, so-called remote CNOT gates. In this paper, we show that combining both, swapping and remote gates, at the reversible circuit level has the prospect of significantly reducing the mapping overhead. We propose a methodology to compute the optimal combination of swaps and templates for Multiple-Controlled Toffoli gates. By using a formulation as a single-source shortest-path problem, a complete database of optimal combinations can be computed efficiently. Experimental results indicate that the mapping overhead can be significantly reduced.

DOI
10.23919/date51398.2021.9474217

Related papers

Combining SWAPs and Remote CNOT Gates for Quantum Circuit Transformation

Philipp Niemann, Luca Mueller, Rolf Drechsler

Quantum computers offer enormous speed advantages over their classical counterparts. Still, optimization on quantum circuits is necessary to further increase their potential. Additionally, physical realizations of quantum computers place restrictions on quantum circuits, regarding the available quantum gates. In order to satisfy these restrictions, non-native gates need to be expressed as an equivalent cascade of natively available quantum gates which induces a mapping overhead. Two complementary approaches to this problem are to move around the qubits (using SWAP gates) or to apply so-called remote gates, i.e. pre-computed cascades of native gates which keep the qubit placement.In this paper, we explore how combinations of movements and remote gates can be employed to reduce the required overhead regarding the number of native gates as well as the circuit depth. We also discuss ways to find out which qubits to address with the movements in order to optimize these metrics. Our general evaluation is supplemented by evaluations on two IBM quantum computer architectures to show how quantum circuits can be optimized by the presented patterns.

Euromicro Conference on Digital System Design (DSD)•Sep 1, 2021•2 citations

Design Space Exploration in the Mapping of Reversible Circuits to IBM Quantum Computers

Philipp Niemann, Alexandre A. A. de Almeida, Gerhard W. Dueck +1 more

With more and more powerful quantum computers becoming available, there is an increasing interest in the efficient mapping of a given quantum circuit to a particular quantum computer (so-called technology mapping). In most cases, the limitations of the targeted quantum hardware have not been taken into account when generating these quantum circuits in the first place. Thus, the technology mapping is likely to induce a considerable overhead for such circuits. In this paper, we consider the realization of reversible circuits consisting of multiple-controlled Toffoli gates on IBM quantum computers. We show that choosing different quantum-level decompositions can indeed have a significant impact on the mapping overhead. Based on this observation, we present an approach to perform design space exploration to obtain quantum circuits with reduced overhead by exploiting information about the targeted quantum hardware as well as the reversible circuit. An experimental evaluation shows that this approach often leads to considerable reductions of the technology mapping overhead with negligible runtime.

Euromicro Conference on Digital System Design (DSD)•Aug 1, 2020•10 citations

Metodologia para o mapeamento de circuitos quânticos e reversíveis para arquiteturas IBM Q

Alexandre Mendes de [UNESP] Almeida Junior

Research in the field of quantum circuits has increased as technology advances in the development of quantum computers. IBM offers access to quantum computers via the cloud service called IBM Q. However, these architectures have some restrictions regarding the types of quantum gates that can be realized. This work proposes a methodology for the mapping of quantum and reversible circuits to the architectures made available by the IBM Q project. The methodology consists in finding CNOT mappings using a set of defined qubits movements to satisfy the architectures constraints by adding as few gates as possible. In order to reduce the number of CNOT gates needing mapping, the permutation of the circuit can be changed. One alternative to find this permutation is trough exhaustive search. However, is not feasible as the number of qubit increases. To solve this problem, the permutation problem was formulated as an Integer Linear Programming problem. The mapping of quantum circuits realized with non-implementable gates and reversible Toffoli circuits to the IBM quantum architectures were proposed in this work as well. This was done by adapting the developed CNOT mappings along with the Integer Linear Programming formulation. The proposed methodology was evaluated by mapping quantum and reversible circuits to an IBM quantum architectures with 5 and 16 qubits. The results were compared with two algorithms that map quantum circuits to IBM architectures. The cost metric used in the evaluation were the number of quantum gates and the number of levels (depth) of the circuits. Experimental results have shown that the proposed methodology outperforms the other approaches regarding the circuits' size. The results of the methodology used to implement quantum (with non-implementable gates) and Toffoli circuits to IBM architectures have shown that the mapping targeting a specific architecture constraints results in a smaller mapped circuit. The methodology developed can be easily adapted to any quantum architecture. Also, the proposed Integer Linear Programming formulation can be used in any reversible circuit and can be applied in other research areas.

•Aug 23, 2019•0 citations

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 Systems•Jun 16, 2025•1 citation

Improved Mapping of Quantum Circuits to IBM QX Architectures

Abhoy Kole, Stefan Hillmich, Kamalika Datta +2 more

Quantum computers are becoming a reality today due to the rapid progress made by researchers in the last years. In the process of building quantum computers, IBM has developed several versions-starting from 5-qubit architectures like IBM QX2 and IBM QX4 to larger 16- or 20-qubit architectures. These architectures support arbitrary rotations of a single qubit and a controlled negation (CNOT) involving two qubits. The two qubit operations come with added coupling-map restrictions that only allow specific physical qubits to be the control and target qubits of the operation. In order to execute a quantum circuit on the IBM QX architecture, CNOT gates must satisfy the so-called coupling constraints of the architecture. Previous works addressed this issue with the objective of reducing the number of gates and the circuit depth. However, in this article, we show that further improvements are possible. To this end, we present a general approach for further improving the number of gate operations and depth of the mapped circuit. The proposed approach encompasses the selection of physical qubits, determining initial and local permutations efficiently to obtain the final circuit mapped to the given IBM QX architecture. Through experiments, improvements are observed over existing methods in terms of the number of gates and circuit depth.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Dec 27, 2019•39 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 Design•Jan 1, 2017•11 citations
Quantum computation received a steadily growing attention in recent years, especially supported by the emergence of publicly available quantum computers like the popular IBM QX series. In order to execute a reversible or quantum circuit on those devices, a mapping is required that replaces each reversible or quantum gate by an equivalent cascade of elementary, i.e. directly executable, gates-a task which tends to induce a significant mapping overhead. Several approaches have been proposed for this task which either rely on the swapping of physically adjacent qubits or the use of precomputed templates, so-called remote CNOT gates. In this paper, we show that combining both, swapping and remote gates, at the reversible circuit level has the prospect of significantly reducing the mapping overhead. We propose a methodology to compute the optimal combination of swaps and templates for Multiple-Controlled Toffoli gates. By using a formulation as a single-source shortest-path problem, a complete database of optimal combinations can be computed efficiently. Experimental results indicate that the mapping overhead can be significantly reduced.
Quantum computers offer enormous speed advantages over their classical counterparts. Still, optimization on quantum circuits is necessary to further increase their potential. Additionally, physical realizations of quantum computers place restrictions on quantum circuits, regarding the available quantum gates. In order to satisfy these restrictions, non-native gates need to be expressed as an equivalent cascade of natively available quantum gates which induces a mapping overhead. Two complementary approaches to this problem are to move around the qubits (using SWAP gates) or to apply so-called remote gates, i.e. pre-computed cascades of native gates which keep the qubit placement.In this paper, we explore how combinations of movements and remote gates can be employed to reduce the required overhead regarding the number of native gates as well as the circuit depth. We also discuss ways to find out which qubits to address with the movements in order to optimize these metrics. Our general evaluation is supplemented by evaluations on two IBM quantum computer architectures to show how quantum circuits can be optimized by the presented patterns.
With more and more powerful quantum computers becoming available, there is an increasing interest in the efficient mapping of a given quantum circuit to a particular quantum computer (so-called technology mapping). In most cases, the limitations of the targeted quantum hardware have not been taken into account when generating these quantum circuits in the first place. Thus, the technology mapping is likely to induce a considerable overhead for such circuits. In this paper, we consider the realization of reversible circuits consisting of multiple-controlled Toffoli gates on IBM quantum computers. We show that choosing different quantum-level decompositions can indeed have a significant impact on the mapping overhead. Based on this observation, we present an approach to perform design space exploration to obtain quantum circuits with reduced overhead by exploiting information about the targeted quantum hardware as well as the reversible circuit. An experimental evaluation shows that this approach often leads to considerable reductions of the technology mapping overhead with negligible runtime.
Research in the field of quantum circuits has increased as technology advances in the development of quantum computers. IBM offers access to quantum computers via the cloud service called IBM Q. However, these architectures have some restrictions regarding the types of quantum gates that can be realized. This work proposes a methodology for the mapping of quantum and reversible circuits to the architectures made available by the IBM Q project. The methodology consists in finding CNOT mappings using a set of defined qubits movements to satisfy the architectures constraints by adding as few gates as possible. In order to reduce the number of CNOT gates needing mapping, the permutation of the circuit can be changed. One alternative to find this permutation is trough exhaustive search. However, is not feasible as the number of qubit increases. To solve this problem, the permutation problem was formulated as an Integer Linear Programming problem. The mapping of quantum circuits realized with non-implementable gates and reversible Toffoli circuits to the IBM quantum architectures were proposed in this work as well. This was done by adapting the developed CNOT mappings along with the Integer Linear Programming formulation. The proposed methodology was evaluated by mapping quantum and reversible circuits to an IBM quantum architectures with 5 and 16 qubits. The results were compared with two algorithms that map quantum circuits to IBM architectures. The cost metric used in the evaluation were the number of quantum gates and the number of levels (depth) of the circuits. Experimental results have shown that the proposed methodology outperforms the other approaches regarding the circuits' size. The results of the methodology used to implement quantum (with non-implementable gates) and Toffoli circuits to IBM architectures have shown that the mapping targeting a specific architecture constraints results in a smaller mapped circuit. The methodology developed can be easily adapted to any quantum architecture. Also, the proposed Integer Linear Programming formulation can be used in any reversible circuit and can be applied in other research areas.
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.
Quantum computers are becoming a reality today due to the rapid progress made by researchers in the last years. In the process of building quantum computers, IBM has developed several versions-starting from 5-qubit architectures like IBM QX2 and IBM QX4 to larger 16- or 20-qubit architectures. These architectures support arbitrary rotations of a single qubit and a controlled negation (CNOT) involving two qubits. The two qubit operations come with added coupling-map restrictions that only allow specific physical qubits to be the control and target qubits of the operation. In order to execute a quantum circuit on the IBM QX architecture, CNOT gates must satisfy the so-called coupling constraints of the architecture. Previous works addressed this issue with the objective of reducing the number of gates and the circuit depth. However, in this article, we show that further improvements are possible. To this end, we present a general approach for further improving the number of gate operations and depth of the mapped circuit. The proposed approach encompasses the selection of physical qubits, determining initial and local permutations efficiently to obtain the final circuit mapped to the given IBM QX architecture. Through experiments, improvements are observed over existing methods in terms of the number of gates and circuit depth.
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.