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

arXiv:2004.07138 · IEEE Transactions on Computers

Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search

Sanjiang Li, Xiangzhen Zhou, Yuan Feng

Published Sep 10, 2020• 53 citations
arXivHTMLPDF

Abstract

Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most usefulswapcombination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.

DOI
10.1109/tc.2020.3023247

Related papers

Subgraph-based Qubit Mapping for Noisy Intermediate-Scale Quantum Computing

Junyi Gao, Wei‐Hsiang Tseng, Yao‐Wen Chang

The noisy intermediate-scale quantum (NISQ) computer significantly advances quantum computing technology. Due to the physical connectivity constraints of the NISQ device, its induced qubit mapping problem becomes more challenging. Recent works employ heuristics to achieve promising outcomes. However, they are limited to using only one type of center for graph matching, and their exhaustive traversal of the coupling graph results in high computation time. This paper strategically generates specific subgraphs during the initial mapping stage to reduce the solution space for the coupling graph. Then, we employ a bidirectional graph isomorphism search to improve initial mapping. In the main mapping stage, we develop an efficient search algorithm to minimize the number of inserted gates. Experimental results show that our method significantly outperforms the state-of-the-art work in reducing the number of inserted CNOT gates by 13.22% and the runtime by 19.61%.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 19, 2026•0 citations

Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search

Xiangzhen Zhou, Sanjiang Li, Yuan Feng

Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom, and arbitrarily long coherence time. In noisy intermediate-scale quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and, therefore, cause further decay of the performance of a quantum circuit. Thus, it is crucial to minimize the number of added gates. In this article, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best-selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters, including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. The experimental results on extensive realistic circuits confirm that the proposed method is efficient and the number of added gates of our algorithm is, on average, only 57% of that of state-of-the-art algorithms on IBM Q20 (Tokyo), the most recent IBM quantum device.

arXiv:1908.08853•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Feb 2, 2020•76 citations

A fast and scalable qubit-mapping method for noisy intermediate-scale quantum computers

Sunghye Park, Daeyeon Kim, Minhyuk Kweon +2 more

This paper presents an efficient qubit-mapping method that redesigns a quantum circuit to overcome the limitations of qubit connectivity. We propose a recursive graph-isomorphism search to generate the scalable initial mapping. In the main mapping, we use an adaptive look-ahead window search to resolve the connectivity constraint within a short runtime. Compared with the state-of-the-art method [15], our proposed method reduced the number of additional gates by 23% on average and the runtime by 68% for the three largest benchmark circuits. Furthermore, our method improved circuit stability by reducing the circuit depth and thus can be a step forward towards fault tolerance.

ACM/IEEE Design Automation Conference (DAC)•Jul 10, 2022•22 citations

Quantum Circuit Transformation Based on Subgraph Isomorphism and Tabu Search

Hui Jiang, Yuxin Deng, Ming Qian Xu

The goal of quantum circuit transformation is to construct mappings from logical quantum circuits to physical ones in an acceptable amount of time, and in the meantime to introduce as few auxiliary gates as possible. We present an effective approach to constructing the mappings. It consists of two key steps: one makes use of a combined subgraph isomorphism and complement (CSIC) to initialize a mapping, the other dynamically adjusts the mapping by using Tabu search-based adjustment (TSA). Our experiments show that, compared with the very recent method wghtgraph considered in the literature, CSIC can save 22.43% of auxiliary gates and reduce the depth of output circuits by 8.46% on average in the initialization of the mapping, and TSA has a better scalability than many state-of-the-art algorithms for adjusting mappings.

•Apr 12, 2021•3 citations

Towards Fidelity-Optimal Qubit Mapping on NISQ Computers

Sri Khandavilli, Indu Palanisamy, Manh V. Nguyen +3 more

Quantum computing is gaining momentum in revolutionizing the way we approach complex problem-solving. However, the practical implementation of quantum algorithms remains a significant challenge due to the error-prone and hardware limits of near-term quantum devices. For instance, physical qubit connections are limited, which necessitates the use of quantum SWAP gates to dynamically transform the logical topology during execution. In addition, to optimize fidelity, it is essential to ensure that 1) the allocated hardware has a low error rate and 2) the number of SWAP gates injected into the circuit is minimized. To address these challenges, we propose a suite of algorithms: the Fidelity-aware Graph Extraction Algorithm (FGEA) is used to identify the hardware region with the lowest probability of error, the Frequency-based Mapping Algorithm (FMA) allocates logical-physical qubits that reduce the potential distance of topological transformation, and the Heuristic Routing Algorithm (HRA) searches for an optimal swapping injection strategy. We evaluate the proposed algorithms on the IBM-provided Noisy Intermediate-Scale Quantum (NISQ) computer, using a dataset consisting of 17 different quantum circuits of various sizes. The circuits are executed on the IBM Toronto Falcon processor. The three proposed algorithms outperform the existing SABRE algorithm in reducing the number of SWAP gates required. Therefore, our proposed algorithms hold significant promise in enhancing the fidelity and reducing the number of SWAP gates required in implementing Quantum algorithms.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•8 citations

A Beam Search Framework for Quantum Circuit Mapping

Cheng Qiu, Pengcheng Zhu, Lihua Wei

In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.

Entropy•Feb 24, 2025•1 citation
Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most usefulswapcombination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.
The noisy intermediate-scale quantum (NISQ) computer significantly advances quantum computing technology. Due to the physical connectivity constraints of the NISQ device, its induced qubit mapping problem becomes more challenging. Recent works employ heuristics to achieve promising outcomes. However, they are limited to using only one type of center for graph matching, and their exhaustive traversal of the coupling graph results in high computation time. This paper strategically generates specific subgraphs during the initial mapping stage to reduce the solution space for the coupling graph. Then, we employ a bidirectional graph isomorphism search to improve initial mapping. In the main mapping stage, we develop an efficient search algorithm to minimize the number of inserted gates. Experimental results show that our method significantly outperforms the state-of-the-art work in reducing the number of inserted CNOT gates by 13.22% and the runtime by 19.61%.
Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom, and arbitrarily long coherence time. In noisy intermediate-scale quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and, therefore, cause further decay of the performance of a quantum circuit. Thus, it is crucial to minimize the number of added gates. In this article, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best-selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters, including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. The experimental results on extensive realistic circuits confirm that the proposed method is efficient and the number of added gates of our algorithm is, on average, only 57% of that of state-of-the-art algorithms on IBM Q20 (Tokyo), the most recent IBM quantum device.
This paper presents an efficient qubit-mapping method that redesigns a quantum circuit to overcome the limitations of qubit connectivity. We propose a recursive graph-isomorphism search to generate the scalable initial mapping. In the main mapping, we use an adaptive look-ahead window search to resolve the connectivity constraint within a short runtime. Compared with the state-of-the-art method [15], our proposed method reduced the number of additional gates by 23% on average and the runtime by 68% for the three largest benchmark circuits. Furthermore, our method improved circuit stability by reducing the circuit depth and thus can be a step forward towards fault tolerance.
The goal of quantum circuit transformation is to construct mappings from logical quantum circuits to physical ones in an acceptable amount of time, and in the meantime to introduce as few auxiliary gates as possible. We present an effective approach to constructing the mappings. It consists of two key steps: one makes use of a combined subgraph isomorphism and complement (CSIC) to initialize a mapping, the other dynamically adjusts the mapping by using Tabu search-based adjustment (TSA). Our experiments show that, compared with the very recent method wghtgraph considered in the literature, CSIC can save 22.43% of auxiliary gates and reduce the depth of output circuits by 8.46% on average in the initialization of the mapping, and TSA has a better scalability than many state-of-the-art algorithms for adjusting mappings.
Quantum computing is gaining momentum in revolutionizing the way we approach complex problem-solving. However, the practical implementation of quantum algorithms remains a significant challenge due to the error-prone and hardware limits of near-term quantum devices. For instance, physical qubit connections are limited, which necessitates the use of quantum SWAP gates to dynamically transform the logical topology during execution. In addition, to optimize fidelity, it is essential to ensure that 1) the allocated hardware has a low error rate and 2) the number of SWAP gates injected into the circuit is minimized. To address these challenges, we propose a suite of algorithms: the Fidelity-aware Graph Extraction Algorithm (FGEA) is used to identify the hardware region with the lowest probability of error, the Frequency-based Mapping Algorithm (FMA) allocates logical-physical qubits that reduce the potential distance of topological transformation, and the Heuristic Routing Algorithm (HRA) searches for an optimal swapping injection strategy. We evaluate the proposed algorithms on the IBM-provided Noisy Intermediate-Scale Quantum (NISQ) computer, using a dataset consisting of 17 different quantum circuits of various sizes. The circuits are executed on the IBM Toronto Falcon processor. The three proposed algorithms outperform the existing SABRE algorithm in reducing the number of SWAP gates required. Therefore, our proposed algorithms hold significant promise in enhancing the fidelity and reducing the number of SWAP gates required in implementing Quantum algorithms.
In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.