Quantum computing promises to solve certain problems more efficiently than classical computation. Realizing this potential on noisy, intermediate-scale quantum (NISQ) devices remains challenging. Among other things, hardware connectivity constraints necessitate additional routing operations that degrade circuit fidelity. The qubit mapping problem - assigning logical qubits to physical qubits while minimizing inserted SWAP gates - is thus critical in quantum circuit transpilation. Exact methods scale poorly, and heuristic approaches like the SABRE algorithm, though efficient, rely on local decisions that can miss globally optimal solutions. In this thesis, we propose K-SWAP SABRE that integrates bounded exhaustive search over sequences of up to k SWAPs into the SABRE algorithm. A modified heuristic ensures global progress while maintaining comparability between explored branches. Experiments on benchmark circuits show that increasing k reduces required SWAP gates, especially on highly connected devices, though at the cost of longer runtime. Our results demonstrate that K-SWAP SABRE can improve heuristic qubit mapping quality without sacrificing scalability, offering a practical approach for mapping circuits to near-term and emerging quantum architectures.
Quantum computing promises to solve certain problems more efficiently than classical computation. Realizing this potential on noisy, intermediate-scale quantum (NISQ) devices remains challenging. Among other things, hardware connectivity constraints necessitate additional routing operations that degrade circuit fidelity. The qubit mapping problem - assigning logical qubits to physical qubits while minimizing inserted SWAP gates - is thus critical in quantum circuit transpilation. Exact methods scale poorly, and heuristic approaches like the SABRE algorithm, though efficient, rely on local decisions that can miss globally optimal solutions. In this thesis, we propose K-SWAP SABRE that integrates bounded exhaustive search over sequences of up to k SWAPs into the SABRE algorithm. A modified heuristic ensures global progress while maintaining comparability between explored branches. Experiments on benchmark circuits show that increasing k reduces required SWAP gates, especially on highly connected devices, though at the cost of longer runtime. Our results demonstrate that K-SWAP SABRE can improve heuristic qubit mapping quality without sacrificing scalability, offering a practical approach for mapping circuits to near-term and emerging quantum architectures.
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.
Due to little considerations in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and control. To address these drawbacks mentioned above, this paper proposes a SWAP-based Bidirectional heuristic search algorithm (SABRE), which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt, globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.
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.
Qubit mapping is a critical aspect of implementing quantum circuits on real hardware devices. Currently, the existing algorithms for qubit mapping encounter difficulties when dealing with larger circuit sizes involving hundreds of qubits. In this article, we introduce an innovative qubit mapping algorithm, Duostra, tailored to address the challenge of implementing large-scale quantum circuits on real hardware devices with limited connectivity. Duostra operates by efficiently determining optimal paths for double-qubit gates and inserting SWAP gates accordingly to implement the double-qubit operations on real devices. Together with two heuristic scheduling algorithms, Limitedly Exhaustive Search and Shortest-Path Estimation, it yields results of good quality within a reasonable runtime, thereby striving toward achieving quantum advantage. Experimental results showcase our algorithm’s superiority, especially for large circuits beyond the NISQ era. For example, on large circuits with more than 50 qubits, we can reduce the mapping cost on an average 21.75% over the virtual best results among QMAP, t ∣ket⟩ , Qiskit, and SABRE. Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t ∣ket⟩ , Qiskit, and SABRE, respectively.
Quantum computing has already demonstrated great computational potential across multiple domains and has received more and more attention. However, due to the connectivity limitations of Noisy Intermediate-Scale Quantum (NISQ) devices, most of the quantum algorithms cannot be directly executed without the help of inserting SWAP gates. Nevertheless, more SWAP gates lead to a longer execution time and, inevitably, lower fidelity of the algorithm. To this end, this paper proposes an optimized qubit mapping algorithm based on a dynamic look-ahead strategy to minimize the number of SWAP gates inserted. Firstly, a heuristic algorithm is proposed based on maximizing physical qubit connectivity to generate the optimal initial qubit mapping, which reduces the need for logical qubit shifts during subsequent SWAP gate insertion. Secondly, in the form of directed acyclic graphs, we identify quantum gates that violate the constraints of physical coupling and insert SWAP gates to remap qubits, thereby overcoming the limitations of qubit interactions. Finally, the optimal SWAP gate insertion strategy is built by comparing the cost of different SWAP gate insertion strategies through a multi-window look-ahead strategy to reduce the number of SWAP gates inserted. The experimental results show that the strategy in this paper decreases the number of SWAP gate insertions and significantly reduces the depth of quantum circuits when performing qubit mapping compared with state-of-the-art methods.
In the past few years, several quantum computers realized by the noisy intermediate-scale quantum (NISQ) technology have been released. However, there exists a significant limitation to using such computers, i.e., the connectivity constraint between physical qubits. To perform a 2-qubit quantum operation on such NISQ computers, its two logical qubits have to be mapped to a pair of physical qubits that satisfy the connectivity constraint. This mapping procedure requires additional operations to be introduced into the original quantum circuit, reducing its fidelity. Therefore, it is of great significance to design an algorithm that is able to complete the mapping task with minimal additional operations. In this article, we propose an efficient algorithm to solve this problem. Our algorithm consists of two core components, an expansion-from-center scheme to determine the initial mapping and a SWAP-based heuristic search algorithm to update the mapping. We introduce the maximum consecutive positive effect of a SWAP operation as the heuristic cost function, allowing our search algorithm to look ahead dynamically. Our algorithm is evaluated on IBM Q 20. The experimental results show that our algorithm can complete the mapping task in a very short time even for large-scale benchmarks with hundreds of thousands of operations, and outperforms the state-of-the-art in terms of the number of additional operations for most benchmarks considered.