In recent years, the advancement of quantum computers has been improving, with its use increasing in practical applications, including noisy intermediate-scale quantum (NISQ) technology. However, an obstacle that limits quantum computer usage is the connectivity restriction between logical and physical qubits. For performing quantum entanglement on NISQ machines, two logical qubits must be mapped to physical qubit pairs that much up to the connectivity constraint. This mapping process must insert additional operations into an initial quantum circuit. Many powerful algorithms have been proposed to solve the mapping problem, which also mitigate circuit size or depth and improve the fidelity of the quantum state. In this review paper, we present various studies for solving qubit mapping or allocation problems and analyze their time complexity and methods.
In recent years, the advancement of quantum computers has been improving, with its use increasing in practical applications, including noisy intermediate-scale quantum (NISQ) technology. However, an obstacle that limits quantum computer usage is the connectivity restriction between logical and physical qubits. For performing quantum entanglement on NISQ machines, two logical qubits must be mapped to physical qubit pairs that much up to the connectivity constraint. This mapping process must insert additional operations into an initial quantum circuit. Many powerful algorithms have been proposed to solve the mapping problem, which also mitigate circuit size or depth and improve the fidelity of the quantum state. In this review paper, we present various studies for solving qubit mapping or allocation problems and analyze their time complexity and methods.
Rapid progress in the physical implementation of quantum computers gave birth to multiple recent quantum machines implemented with superconducting technology. In these NISQ machines, each qubit is physically connected to a bounded number of neighbors. This limitation prevents most quantum programs from being directly executed on quantum devices. A compiler is required for converting a quantum program to a hardware-compliant circuit, in particular, making each two-qubit gate executable by mapping the two logical qubits to two physical qubits with a link between them. To solve this problem, existing studies focus on inserting SWAP gates to dynamically remap logical qubits to physical qubits. However, most of the schemes lack the consideration of time-optimality of generated quantum circuits, or are achieving time-optimality with certain constraints. In this work, we propose a theoretically time-optimal SWAP insertion scheme for the qubit mapping problem. Our model can also be extended to practical heuristic algorithms. We present exact analysis results by using our model for quantum programs with recurring execution patterns. We have for the first time discovered an optimal qubit mapping pattern for quantum fourier transformation (QFT) on 2D nearest neighbor architecture. We also present a scalable extension of our theoretical model that can be used to solve qubit mapping for large quantum circuits.
Noisy intermediate scale quantum (NISQ) computers are becoming a reality thanks to the recent advances made by researchers who physically build such systems. In order to execute corresponding quantum algorithms (usually provided in terms of quantum circuits), certain physical constraints in the architectures need to be satisfied. More precisely, physical constraints restrict the possible interactions between qubits which frequently result in cases where qubits which are supposed to interact in a quantum circuit are not allowed to interact on the physical device. Thus far, this is addressed by dedicated methods that map the logical quantum circuit to a physical realization and satisfy the constraints by inserting further operations. This leads to additional costs which harm the fidelity of the circuit and, hence, urgently need to be avoided. Unfortunately, current state-of-the-art approaches for this mapping process take the existing architectures as invariant and only try to reduce the number of additionally needed operations. In contrast, (slight) changes in the, respectively, given architectures (which still keep the underlying physical constraints satisfied) might be possible and may allow for even better (i.e., less costly) mappings. But this potential has not been investigated yet. In this work, we explore this potential. More precisely, we introduce several schemes for generating alternative coupling graphs (and, by this, quantum computing architectures) that still might be able to satisfy physical constraints but, at the same time, allow for a more efficient realization of the desired quantum functionality. Evaluations confirm the potential of those alternative coupling graphs and demonstrate that they can reduce the mapping overhead by up to 60% in the best case and up to almost 40% on average.
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 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.
In recent years, the emergence of the Noisy Intermediate-Scale Quantum (NISQ) era has led to the development of a wide variety of quantum devices, marking a dynamic phase in the field of quantum computing. Despite these advancements, practical applications of quantum computers still face significant challenges, one of the most prominent being the limited connectivity between physical quantum bits (qubits). This limitation requires quantum circuits to be recompiled through layout synthesis before they can be executed on quantum devices. Layout synthesis determines the specific placement of quantum gates within the circuit on the physical hardware. When gates do not align with the connectivity constraints of the device, additional quantum gates must be inserted to remap the qubits, which can negatively affect the circuit’s efficiency and performance. To address this issue, the primary goal of this paper is to enhance the mapping process within layout synthesis, aiming to optimize both the layout and the circuit depth. Experimental results demonstrate that the proposed method effectively reduces the quantum circuit depth, outperforming other existing approaches in terms of efficiency.
Rapid advancement in the domain of quantum technologies have opened up researchers to the real possibility of experimenting with quantum circuits, and simulating small-scale quantum programs. Nevertheless, the quality of currently available qubits and environmental noise pose a challenge in smooth execution of the quantum circuits. Therefore, efficient design automation flows for mapping a given algorithm to the Noisy Intermediate Scale Quantum (NISQ) computer becomes of utmost importance. State-of-the-art quantum design automation tools are primarily focused on reducing logical depth, gate count and qubit counts with recent emphasis on topology-aware (nearest-neighbour compliance) mapping. In this work, we extend the technology mapping flows to simultaneously consider the topology and gate fidelity constraints while keeping logical depth and gate count as optimization objectives. We provide a comprehensive problem formulation and multi-tier approach towards solving it. The proposed automation flow is compatible with commercial quantum computers, such as IBM QX and Rigetti. Our simulation results over 10 quantum circuit benchmarks, show that the fidelity of the circuit can be improved up to 3.37 × with an average improvement of 1.87 ×.