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.
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.
The recent advances in the physical realization of Noisy Intermediate Scale Quantum (NISQ) computers have motivated research on design automation that allows users to execute quantum algorithms on them. Certain physical constraints in the architectures restrict how logical qubits used to describe the algorithm can be mapped to physical qubits used to realize the corresponding functionality. Thus far, this has been addressed by inserting additional operations in order to overcome the physical constrains. However, all these approaches have taken the existing architectures as invariant and did not explore the potential of changing the quantum architecture itself-a valid option as long as the underlying physical constrains remain satisfied. In this work, we propose initial ideas to explore this potential. More precisely, we introduce several schemes for the generation of 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.
In the past years, quantum computers more and more have evolved from an academic idea to an upcoming reality. IBM's project IBM Q can be seen as evidence of this progress. Launched in March 2017 with the goal to provide access to quantum computers for a broad audience, this allowed users to conduct quantum experiments on a 5-qubit and, since June 2017, also on a 16-qubit quantum computer (called IBM QX2 and IBM QX3, respectively). Revised versions of these 5- and 16-qubit quantum computers (named IBM QX4 and IBM QX5, respectively) are available since September 2017. In order to use these, the desired quantum functionality (e.g., provided in terms of a quantum circuit) has to be properly mapped so that the underlying physical constraints are satisfied-a complex task. This demands solutions to automatically and efficiently conduct this mapping process. In this paper, we propose a methodology which addresses this problem, i.e., maps the given quantum functionality to a realization which satisfies all constraints given by the architecture and, at the same time, keeps the overhead in terms of additionally required quantum gates minimal. The proposed methodology is generic, can easily be configured for similar future architectures, and is fully integrated into IBM's SDK. Experimental evaluations show that the proposed approach clearly outperforms IBM's own mapping solution. In fact, for many quantum circuits, the proposed approach determines a mapping to the IBM architecture within minutes, while IBM's solution suffers from long runtimes and runs into a timeout of 1 h in several cases. As an additional benefit, the proposed approach yields mapped circuits with smaller costs (i.e., fewer additional gates are required). All implementations of the proposed methodology are publicly available at http://iic.jku.at/eda/research/ibm_qx_mapping.
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.
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.
Quantum computers have emerged as an alternative computer paradigm that will allow to solve some complex problems of large numbers that are not tractable for classical computers, e.g. factorization. Quantum computers also have the ability to simulate quantum mechanics in a real and direct way. The development of quantum computers faces many unique obstacles. In recent years, various quantum computer prototypes have been created by com- panies such as Google and IBM, on which we can run some quantum algorithms. But these prototypes are far from the quantum computers we envision and can function like today?s classical computers. It is said that we are in the time of Noisy Intermediate-Scale Quantum (NISQ) computers. This means that current quantum computers are very noisy and their size is very small compared to classical comput- ers. The challenge with small, noisy quantum devices running quantum algorithms is that due to the hardware limitations they face which must be respected, quantum algorithm needs to be modified before their execution on quantum devices. To solve this problem in quantum computers, a mapping process is needed, which is part of the compilation step that modifies the quantum algorithms to take into account all the limitations of the targeted quantum device. After mapping process, the resulting quantum circuit usually has a higher number of gates and (execution time) latency, decreasing the algorithm?s reliability. Different mapping solutions have been already proposed. Most of them are meant for a specific quan- tum processor and different in methodology, approach and features. In addition, they are usually only compared in terms of added gates (gate overhead) or added circuit execution time (latency overhead). No thorough comparative analysis of the different mapping solutions performance and features has been performed so far. In this thesis, we apply structured Design Space Exploration to the mapping of quantum circuits. By doing so, we will be able to have a deeper understanding of this process, make a thorough comparison of the mapper approaches and even develop optimized solutions for given applications and quantum devices. Moreover, we apply Design Space Exploration to the generation of quantum algorithms used as benchmarks and start to explore profiling them in a structured approach.
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.