Search

Abstract 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.

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. [ABSTRACT FROM AUTHOR]

As cloud quantum computing gains broader acceptance, a growing quantity of researchers are directing their focus towards this domain. Nevertheless, the rapid surge in demand for cloud-based quantum computing resources has led to a scarcity, which in turn hampers users from achieving optimal satisfaction. Therefore, cloud quantum computing service providers require a unified analysis and scheduling framework for their quantumresources and user jobs to meet the ever-growing usage demands. This paper introduces a new multi-programming scheduling framework for quantum computing in a cloud environment. The framework addresses the issue of limited quantum computing resources in cloud environments and ensures a satisfactory user experience. It introduces three innovative designs: 1) Our framework automatically allocates tasks to different quantum backends while ensuring fairness among users by considering both the cloud-based quantum resources and the user-submitted tasks. 2)Multi-programmingmechanism is employed across different quantum backends to enhance the overall throughput of the quantum cloud. In comparison to conventional task schedulers, our proposed framework achieves a throughput improvement of more than two-fold in the quantum cloud. 3) The framework can balance fidelity and user waiting time by adaptively adjusting scheduling parameters. [ABSTRACT FROM AUTHOR]

As quantum computing devices increase in size with respect to the number of qubits, two-qubit interactions become more challenging, necessitating innovative and scalable qubit routing solutions. In this work, we introduce beSnake, a novel algorithm specifically designed to address the intricate qubit routing challenges in scalable spin-qubit architectures. Unlike traditional methods in superconducting architectures that solely rely on swap operations, beSnake also incorporates the shuttle operation to optimize the execution time and fidelity of quantum circuits and achieves fast computation times of the routing task itself. Employing a simple breadth-first search approach, beSnake effectively manages the restrictions created by diverse topologies and qubit positions acting as obstacles for up to 72% qubit density. It also has the option to adjust the level of optimization and to dynamically tackle parallelized routing tasks, all the while maintaining noise awareness. Our simulations demonstrate beSnake's advantage over an existing routing solution on random circuits and real quantum algorithms with up to 1000 qubits, showing an average improvement of up to 80% in gate overhead, 54% in depth overhead, and up to 8.33 times faster routing times.

The goal of qubit mapping is to map a logical circuit to a physical device by introducing additional gates as few as possible in an acceptable amount of time. We present an effective approach called Tabu Search Based Adjustment (TSA) algorithm to construct the mappings. It consists of two key steps: one is making use of a combined subgraph isomorphism and completion to initialize some candidate mappings, and the other is dynamically modifying the mappings by TSA. Our experiments show that, compared with state-of-the-art methods, TSA can generate mappings with a smaller number of additional gates and have better scalability for large-scale circuits. [ABSTRACT FROM AUTHOR]

To compile quantum circuits on the target processor, quantum circuits need to satisfy the nearest neighbor architecture constraint first. Therefore, quantum circuit compilation for nearest neighbor architecture is necessary for the near-term quantum compiler. In this paper, a novel compilation method based on reinforcement learning is proposed for nearest neighbor architecture of quantum circuits. Initially, quantum circuits should be decomposed based on NCV. To minimize the nearest neighbor cost of decomposed quantum circuits, a methodology to select the order of auxiliary qubits is proposed. Then, the nearest neighbor architecture mapping problem is formulated by model-based reinforcement learning. An initial mapping method of quantum lines based on quantum weights is proposed for decomposed quantum circuits, and three state space search strategies are designed to reduce state space of the mapping process. The policy iteration and value iteration algorithms are applied in the improved state space to obtain the optimal mapping of quantum circuits for nearest neighbor architecture. The proposed compilation method is generic and can easily be configured for future architectures. Experiments of the proposed compilation method are performed on the benchmark dataset Revlib, and experimental results show that the proposed method outperforms other available state-of-the-art methods. For SWAP usage, the reduction of the proposed method is up to 62.5% and 66.7% compared to the state-of-the-art exact reordering and heuristic methods, respectively. [ABSTRACT FROM AUTHOR]

In order to implement a quantum circuit on an NISQ device, it must be transformed into a functionally equivalent circuit that satisfies the device's connectivity constraints. However, NISQ devices are inherently noisy, and minimizing the number of SWAP gates added to the circuit is crucial for reducing computation errors. To achieve this, we propose a subgraph isomorphism algorithm based on the timing weight priority of quantum gates, which provides a better initial mapping for a specific two-dimensional quantum architecture. Additionally, we introduce a heuristic swap sequence selection optimization algorithm that uses a distance optimization measurement function to select the ideal sequence and reduce the number of SWAP gates, thereby optimizing the circuit transformation. Our experiments demonstrate that our proposed algorithm is effective for most benchmark quantum circuits, with a maximum optimization rate of up to 43.51% and an average optimization rate of 13.51%, outperforming existing related methods. [ABSTRACT FROM AUTHOR]

The qubit mapping approach serves to transform a quantum logical circuit (LC) into a physical one that satisfies the connectivity constraints imposed by the noisy intermediate-scale quantum (NISQ) devices. The quality of the physical circuit generated by a mapping approach depends largely on the initial mapping, which specifies the correspondence between the qubits in the LC and the qubits on the NISQ device. There are a total of $n!$ different initial mappings for a qubit mapping problem with $n$ qubits, and among them, there is at least one initial mapping corresponding to the smallest physical circuit that this mapping approach can output. Finding such an initial mapping is very important for reliable computations on the NISQ device. To this end, we propose an iterated local search framework as well as a heuristic circuit mapper. In this framework, we perform multiple local searches on the space of initial mappings, and during each local search, several promising neighborhoods of the current initial mapping are generated and evaluated by invoking the circuit mapper in a forward or a backward manner. This framework provides a way for the qubit mapping approach to find the best physical circuit that it can produce, allowing it to trade time for circuit quality, which is necessary in the NISQ era. The experimental results demonstrate the stability, scalability, and effectiveness of this approach in reducing the number of additional gates. Moreover, although this approach is a multipass circuit mapping process, it can generate a good-quality physical circuit within half an hour, even for the circuit with more than 10 000 gates. [ABSTRACT FROM AUTHOR]

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 useful swap combination 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. [ABSTRACT FROM AUTHOR]

Due to several physical limitations in the realization of quantum hardware, today's quantum computers are qualified as noisy intermediate-scale quantum (NISQ) hardware. NISQ hardware is characterized by a small number of qubits (50 to a few hundred) and noisy operations. Moreover, current realizations of superconducting quantum chips do not have the ideal all-to-all connectivity between qubits but rather at most a nearest-neighbor connectivity. All these hardware restrictions add supplementary low-level requirements. They need to be addressed before submitting the quantum circuit to an actual chip. Satisfying these requirements is a tedious task for the programmer. Instead, the task of adapting the quantum circuit to a given hardware is left to the compiler. In this article, we propose a hardware-aware (HA) mapping transition algorithm that takes the calibration data into account with the aim to improve the overall fidelity of the circuit. Evaluation results on IBM quantum hardware show that our HA approach can outperform the state of the art, both in terms of the number of additional gates and circuit fidelity.

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Rapid development has taken place in quantum algorithms, but few of them can be implemented directly on the quantum computer because of the coupling constraint and high error rates of quantum computer operations. Transforming a circuit into an executable one on the quantum computer with the highest fidelity is an NP problem. Therefore, the algorithm tackling the mapping and routing problem of qubits is needed. Following the policy of VQA, a heuristic algorithm to solve the problem is proposed. The algorithm uses the error score derived from quantum operation’s error rate as the heuristic cost. Combining SWAP gates, physical CNOT gates, remote CNOT gates and inverse CNOT gates, the algorithm transforms the input circuit into an executable output circuit on the quantum computer with lower error score in acceptable execution time and moves forward from local optimal to global optimal. [ABSTRACT FROM AUTHOR]