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:2103.15695 · IEEE Transactions on Quantum Engineering

Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm

Matthew Steinberg, Sebastian Feld, Carmen G. Almudéver, Michael Marthaler, Jan-Michael Reiner

Published Jan 1, 2022• 17 citations
arXivHTMLPDF

Abstract

The qubit-mapping problem aims to assign and route qubits of a quantum circuit onto an noisy intermediate-scale quantum (NISQ) device in an optimized fashion, with respect to some cost function. Finding an optimal solution to this problem is known to scale exponentially in computational complexity; as such, it is imperative to investigate scalable qubit-mapping solutions for NISQ computation. In this work, a noise-aware heuristic qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on an NISQ device, but does not route qubits during the quantum algorithm’s execution) is presented and compared against the optimalbrute-forcesolution, as well as a trivial qubit assignment, with the aim to quantify the performance of our heuristic qubit-assignment algorithm. We find that for small, connected-graph algorithms, our heuristic-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms. Additionally, we find that the topological-graph properties of quantum algorithms with over six qubits play an important role in our heuristic qubit-assignment algorithm’s performance on NISQ devices. Finally, we investigate the scaling properties of our heuristic algorithm for quantum processors with up to 100 qubits; here, the algorithm was found to be scalable for quantum-algorithms that admit path-like graphs. Our findings show that as the size of the quantum processor in our simulation grows, so do the benefits from utilizing the heuristic qubit-assignment algorithm, under particular constraints for our heuristic algorithm. This work, thus, characterizes the performance of a heuristic qubit-assignment algorithm with respect to the topological-graph and scaling properties of a quantum algorithm that one may wish to run on a given NISQ device.

DOI
10.1109/tqe.2022.3160015

Related papers

A Noise-Aware Qubit Mapping Algorithm Evaluated via Qubit Interaction-Graph Criteria

Matthew Steinberg, Sebastian Feld, Carmen G. Almudéver +2 more

The qubit-mapping problem aims to assign qubits from a quantum circuit to a realistic NISQ device in order to maximize limited resources. Many algorithmic solutions for the qubit-mapping problem have been introduced, but much work remains in order to evaluate the effectiveness of a qubit-mapping algorithm with respect to mapping a circuit to devices while taking into account the noise characteristics of the device. In this work, we make progress on this question. Firstly, we introduce a noise-aware heuristic mapping algorithm which fares well when compared to brute-force and trivial mapping solutions for several benchmarks. This comparison serves to provide effective upper and lower bounds for our heuristic mapper in terms of an algorithm's success rate. Subsequently, we analyze how the performance of the mapping algorithm is affected by the characteristics of the interaction graph, which represents the interactions of qubits in a quantum circuit. We observe that as interaction-graph edges are added to benchmarks in either depth-first or breadth-first fashion, our heuristic algorithm's calculated success rate varies significantly, implying that both the amount of interaction-graph vertex degree and the distribution of edges in a quantum circuit's interaction graph play a significant role in the calculated success rate when our greedy heuristic maps to a quantum device's coupling graph. Lastly, we discovered that our heuristic algorithm provides substantial benefits over the trivial solution when mapping quantum circuits to QPUs, provided that less than approximately 75\% of the QPU is occupied. Lastly, as the size of the quantum processor in our simulation grows, so do the purported benefits from utilizing our heuristic mapper. This work takes the first steps towards the characterization of quantum algorithms with respect to efficient qubit-mapping solutions in NISQ-era devices.

•Mar 29, 2021•1 citation

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

Size optimization of CNOT circuits on NISQ

Anpeng Zhang, Xiutao Feng, Shengyuan Xu

Abstract Quantum computers in practice today require strict memory constraints, where 2-qubit operations can only be performed between the qubits closest to each other in a graph structure. So a quantum circuit must undergo a transformation to the graph before it can be implemented. In this paper, we study the optimization of the CNOT circuits on some noisy intermediate-scale quantum(NISQ) devices. Compared with previous works, we decompose it into two sub-problems: optimization with a given initial qubit distribution and optimization without limitations of initial qubit distribution. We find that most of the previous researches focused on the first sub-problem, and ignored the influence of different distribution of qubits in the same topology structure on the optimization results. In this paper, we take both sub-problems into account and give some new optimization algorithms. In short, our method is divided into two steps: matrix optimization and routing optimization. We implement matrix optimization with the algorithm in [1 ] and put forward a new heuristic algorithm with MILP method which can solve the second step. We implement our algorithm on IBM20 and some other NISQ devices, the results are better than most other methods in our experiment.

arXiv:2210.05184•Jan 17, 2024•0 citations

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

Optimization of CNOT circuits under topological constraints.

Bujiao Wu, Xiaoyu He, Shuai Yang +4 more

CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any $n$-qubit CNOT circuit to less than $2n^2$ on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves $O(n^2/\log \delta)$ size on a graph with the minimum degree $\delta$, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any $n$-qubit CNOT circuit can be optimized to be linear in $n$ with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.

•Oct 31, 2019•5 citations

Algorithm-Aware Qubit Mapping

Yanjun Ji, Ilia Polian

Algorithm-Aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although the exact method provides a high-quality solution, its compilation time grows exponentially with the circuit size. To improve its scalability, we propose the AlgAw qubit mapping. The main idea is to first determine the subcircuits in an algorithm to be mapped, then analyze the optimal solutions of small-scale subcircuits found by exact methods to obtain solutions of large-scale subcircuits, and finally reconstruct the entire circuit and assign parameters. Applying AlgAw to the Quantum Approximate Optimization Algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on Noisy Intermediate-Scale Quantum (NISQ) computers. Compared to Qiskit, Tket, and SWAP-Network, AlgAw produces the least number of CNOT gates and the lowest circuit depth. Furthermore, AlgAw takes only a few seconds to obtain a circuit with a hundred qubits that satisfies the connectivity constraints. The benchmarking results on Quantum Processing Units (QPUs) show that AlgAw qubit mapping yields higher values of approximation ratio than others. AlgAw can also be applied to other algorithms such as the Variational Quantum Eigensolver (VQE).

•Dec 30, 2022•1 citation
The qubit-mapping problem aims to assign and route qubits of a quantum circuit onto an noisy intermediate-scale quantum (NISQ) device in an optimized fashion, with respect to some cost function. Finding an optimal solution to this problem is known to scale exponentially in computational complexity; as such, it is imperative to investigate scalable qubit-mapping solutions for NISQ computation. In this work, a noise-aware heuristic qubit-assignment algorithm (which assigns initial placements for qubits in a quantum algorithm to qubits on an NISQ device, but does not route qubits during the quantum algorithm’s execution) is presented and compared against the optimalbrute-forcesolution, as well as a trivial qubit assignment, with the aim to quantify the performance of our heuristic qubit-assignment algorithm. We find that for small, connected-graph algorithms, our heuristic-assignment algorithm faithfully lies in between the effective upper and lower bounds given by the brute-force and trivial qubit-assignment algorithms. Additionally, we find that the topological-graph properties of quantum algorithms with over six qubits play an important role in our heuristic qubit-assignment algorithm’s performance on NISQ devices. Finally, we investigate the scaling properties of our heuristic algorithm for quantum processors with up to 100 qubits; here, the algorithm was found to be scalable for quantum-algorithms that admit path-like graphs. Our findings show that as the size of the quantum processor in our simulation grows, so do the benefits from utilizing the heuristic qubit-assignment algorithm, under particular constraints for our heuristic algorithm. This work, thus, characterizes the performance of a heuristic qubit-assignment algorithm with respect to the topological-graph and scaling properties of a quantum algorithm that one may wish to run on a given NISQ device.
The qubit-mapping problem aims to assign qubits from a quantum circuit to a realistic NISQ device in order to maximize limited resources. Many algorithmic solutions for the qubit-mapping problem have been introduced, but much work remains in order to evaluate the effectiveness of a qubit-mapping algorithm with respect to mapping a circuit to devices while taking into account the noise characteristics of the device. In this work, we make progress on this question. Firstly, we introduce a noise-aware heuristic mapping algorithm which fares well when compared to brute-force and trivial mapping solutions for several benchmarks. This comparison serves to provide effective upper and lower bounds for our heuristic mapper in terms of an algorithm's success rate. Subsequently, we analyze how the performance of the mapping algorithm is affected by the characteristics of the interaction graph, which represents the interactions of qubits in a quantum circuit. We observe that as interaction-graph edges are added to benchmarks in either depth-first or breadth-first fashion, our heuristic algorithm's calculated success rate varies significantly, implying that both the amount of interaction-graph vertex degree and the distribution of edges in a quantum circuit's interaction graph play a significant role in the calculated success rate when our greedy heuristic maps to a quantum device's coupling graph. Lastly, we discovered that our heuristic algorithm provides substantial benefits over the trivial solution when mapping quantum circuits to QPUs, provided that less than approximately 75\% of the QPU is occupied. Lastly, as the size of the quantum processor in our simulation grows, so do the purported benefits from utilizing our heuristic mapper. This work takes the first steps towards the characterization of quantum algorithms with respect to efficient qubit-mapping solutions in NISQ-era devices.
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.
Abstract Quantum computers in practice today require strict memory constraints, where 2-qubit operations can only be performed between the qubits closest to each other in a graph structure. So a quantum circuit must undergo a transformation to the graph before it can be implemented. In this paper, we study the optimization of the CNOT circuits on some noisy intermediate-scale quantum(NISQ) devices. Compared with previous works, we decompose it into two sub-problems: optimization with a given initial qubit distribution and optimization without limitations of initial qubit distribution. We find that most of the previous researches focused on the first sub-problem, and ignored the influence of different distribution of qubits in the same topology structure on the optimization results. In this paper, we take both sub-problems into account and give some new optimization algorithms. In short, our method is divided into two steps: matrix optimization and routing optimization. We implement matrix optimization with the algorithm in [1 ] and put forward a new heuristic algorithm with MILP method which can solve the second step. We implement our algorithm on IBM20 and some other NISQ devices, the results are better than most other methods in our experiment.
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%.
CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any nnn-qubit CNOT circuit to less than 2n22n^22n2 on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves O(n2/log⁡δ)O(n^2/\log \delta)O(n2/logδ) size on a graph with the minimum degree δ\deltaδ, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any nnn-qubit CNOT circuit can be optimized to be linear in nnn with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.
Algorithm-Aware (AlgAw) qubit mapping aims at directly providing the solutions to qubit mapping of algorithms with regular structures based on the algorithm’s features. Although the exact method provides a high-quality solution, its compilation time grows exponentially with the circuit size. To improve its scalability, we propose the AlgAw qubit mapping. The main idea is to first determine the subcircuits in an algorithm to be mapped, then analyze the optimal solutions of small-scale subcircuits found by exact methods to obtain solutions of large-scale subcircuits, and finally reconstruct the entire circuit and assign parameters. Applying AlgAw to the Quantum Approximate Optimization Algorithm (QAOA) on linear and T-shaped subtopologies produces optimal and scalable solutions for arbitrary numbers of qubits and depths, which is critical to the algorithm’s performance on Noisy Intermediate-Scale Quantum (NISQ) computers. Compared to Qiskit, Tket, and SWAP-Network, AlgAw produces the least number of CNOT gates and the lowest circuit depth. Furthermore, AlgAw takes only a few seconds to obtain a circuit with a hundred qubits that satisfies the connectivity constraints. The benchmarking results on Quantum Processing Units (QPUs) show that AlgAw qubit mapping yields higher values of approximation ratio than others. AlgAw can also be applied to other algorithms such as the Variational Quantum Eigensolver (VQE).