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

Euromicro Conference on Digital System Design (DSD)

Combining SWAPs and Remote CNOT Gates for Quantum Circuit Transformation

Philipp Niemann, Luca Mueller, Rolf Drechsler

Published Sep 1, 2021• 2 citations
Publisher

Abstract

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.

DOI
10.1109/dsd53832.2021.00080

Related papers

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

Philipp Niemann, Chandan Bandyopadhyay, Rolf Drechsler

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.

Design, Automation, and Test in Europe•Feb 1, 2021•10 citations

Exploiting Quantum Teleportation in Quantum Circuit Mapping

Stefan Hillmich, Alwin Zulehner, Robert Wille

Quantum computers are constantly growing in their number of qubits, but continue to suffer from restrictions such as the limited pairs of qubits that may interact with each other. Thus far, this problem is addressed by mapping and moving qubits to suitable positions for the interaction (known as quantum circuit mapping). However, this movement requires additional gates to be incorporated into the circuit, whose number should be kept as small as possible since each gate increases the likelihood of errors and decoherence. State-of-the-art mapping methods utilize swapping and bridging to move the qubits along the static paths of the coupling map---solving this problem without exploiting all means the quantum domain has to offer. In this paper, we propose to additionally exploit quantum teleportation as a possible complementary method. Quantum teleportation conceptually allows to move the state of a qubit over arbitrary long distances with constant overhead---providing the potential of determining cheaper mappings. The potential is demonstrated by a case study on the IBM Q Tokyo architecture which already shows promising improvements. With the emergence of larger quantum computing architectures, quantum teleportation will become more effective in generating cheaper mappings.

arXiv:2011.07314•Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 18, 2021•34 citations

2D Qubit Placement of Quantum Circuits using LONGPATH

Ghosh, Mrityunjay, Nivedita Dey, Debdeep Mitra +1 more

In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.

arXiv:2007.06804•Jul 14, 2020•1 citation

CNOT Gate Mappings to Clifford+T Circuits in IBM Architectures

Alexandre A. A. de Almeida, Gerhard W. Dueck, Alexandre César Rodrigues da Silva

IBM architectures impose some restrictions the quantum circuits that can be implemented. Only gates from Clifford+T gate library can be used and not all of the CNOT gates are available. Some of the CNOT need to be mapped into a sequence of gates. In this paper we present a set of mappings to conform to the restrictions imposed by IBM's architectures. These mappings require fewer gates than SWAP gates. It is well known, that permuting the qubits will yield circuits with different number of gates. The design in this paper uses efficient mappings with qubit permutations to obtain circuits with a reduced number of gates. Results have shown that the proposed approach reduces circuits by up to 64% compared with Qiskit and up to 42% compared with another mapping algorithm.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2019•13 citations

Reducing the Overhead of Mapping Quantum Circuits to IBM Q System

Atsushi Matsuo, Wakaki Hattori, Shigeru Yamashita

We propose an efficient approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on IBM Q system. Our idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the subcircuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2019•36 citations

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
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.
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 are constantly growing in their number of qubits, but continue to suffer from restrictions such as the limited pairs of qubits that may interact with each other. Thus far, this problem is addressed by mapping and moving qubits to suitable positions for the interaction (known as quantum circuit mapping). However, this movement requires additional gates to be incorporated into the circuit, whose number should be kept as small as possible since each gate increases the likelihood of errors and decoherence. State-of-the-art mapping methods utilize swapping and bridging to move the qubits along the static paths of the coupling map---solving this problem without exploiting all means the quantum domain has to offer. In this paper, we propose to additionally exploit quantum teleportation as a possible complementary method. Quantum teleportation conceptually allows to move the state of a qubit over arbitrary long distances with constant overhead---providing the potential of determining cheaper mappings. The potential is demonstrated by a case study on the IBM Q Tokyo architecture which already shows promising improvements. With the emergence of larger quantum computing architectures, quantum teleportation will become more effective in generating cheaper mappings.
In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
IBM architectures impose some restrictions the quantum circuits that can be implemented. Only gates from Clifford+T gate library can be used and not all of the CNOT gates are available. Some of the CNOT need to be mapped into a sequence of gates. In this paper we present a set of mappings to conform to the restrictions imposed by IBM's architectures. These mappings require fewer gates than SWAP gates. It is well known, that permuting the qubits will yield circuits with different number of gates. The design in this paper uses efficient mappings with qubit permutations to obtain circuits with a reduced number of gates. Results have shown that the proposed approach reduces circuits by up to 64% compared with Qiskit and up to 42% compared with another mapping algorithm.
We propose an efficient approach to optimize the number of necessary SWAP gates when we perform a quantum circuit on IBM Q system. Our idea is to change the order of quantum gates (if possible) so that each sub-circuit has only gates performing on adjacent qubits. For each sub-circuit, we utilize a SAT solver to find the best qubit placement such that the subcircuit has only gates on adjacent qubits. Each sub-circuit may have a different qubit placement such that we do not need SWAP gates for the sub-circuit. Thus, we insert SWAP gates between two sub-circuits to change the qubit placement which is desirable for the following sub-circuit. To reduce the number of such SWAP gates between two sub-circuits, we utilize A* algorithm.
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.