A quantum circuit transformation (QCT) is required when executing a quantum program in a real quantum processing unit (QPU). By inserting auxiliary SWAP gates, a QCT algorithm transforms a quantum circuit to one that satisfies the connectivity constraint imposed by the QPU. Due to the nonnegligible gate error and the limited qubit coherence time of the QPU, QCT algorithms that minimize gate number or circuit depth or maximize the fidelity of output circuits are in urgent need. Unfortunately, finding optimized transformations often involve exhaustive searches, which are extremely time consuming and not practical for most circuits. In this article, we propose a framework that uses a policy artificial neural network (ANN) trained by supervised learning on shallow circuits to help existing QCT algorithms select the most promising SWAP gate. ANNs can be trained offline in a distributed way and the trained ANN can be easily incorporated into QCT algorithms to enable them to search deeper without bringing too much overhead in time complexity. Exemplary embeddings of the trained ANNs into target QCT algorithms demonstrate that the transformation performance can be consistently improved on QPUs with various connectivity structures and random or realistic quantum circuits.
A quantum circuit transformation (QCT) is required when executing a quantum program in a real quantum processing unit (QPU). By inserting auxiliary SWAP gates, a QCT algorithm transforms a quantum circuit to one that satisfies the connectivity constraint imposed by the QPU. Due to the nonnegligible gate error and the limited qubit coherence time of the QPU, QCT algorithms that minimize gate number or circuit depth or maximize the fidelity of output circuits are in urgent need. Unfortunately, finding optimized transformations often involve exhaustive searches, which are extremely time consuming and not practical for most circuits. In this article, we propose a framework that uses a policy artificial neural network (ANN) trained by supervised learning on shallow circuits to help existing QCT algorithms select the most promising SWAP gate. ANNs can be trained offline in a distributed way and the trained ANN can be easily incorporated into QCT algorithms to enable them to search deeper without bringing too much overhead in time complexity. Exemplary embeddings of the trained ANNs into target QCT algorithms demonstrate that the transformation performance can be consistently improved on QPUs with various connectivity structures and random or realistic quantum circuits.
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.
In Noisy Intermediate-Scale Quantum (NISQ) era, quantum processing units (QPUs) suffer from, among others, highly limited connectivity between physical qubits. To make a quantum circuit effectively executable, a circuit transformation process is necessary to transform it, with overhead cost the smaller the better, into a functionally equivalent one so that the connectivity constraints imposed by the QPU are satisfied. While several algorithms have been proposed for this goal, the overhead costs are often very high, which degenerates the fidelity of the obtained circuits sharply. One major reason for this lies in that, due to the high branching factor and vast search space, almost all these algorithms only search very shallowly and thus, very often, only (at most) locally optimal solutions can be reached. In this paper, we propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit transformation problem, which enables the search process to go much deeper. The general framework supports implementations aiming to reduce either the size or depth of the output circuit through introducing SWAP or remote CNOT gates. The algorithms, called MCTS-Size and MCTS-Depth, are polynomial in all relevant parameters. Empirical results on extensive realistic circuits and IBM Q Tokyo show that the MCTS-based algorithms can reduce the size (depth, resp.) overhead by, on average, 66% (84%, resp.) when compared with tket, an industrial level compiler.
The design of quantum circuits is often idealized, however, executing these circuits on quantum devices necessitates meeting the connectivity constraints imposed on physical devices by inserting SWAP gates. Various methods based on exact and heuristic solutions have been proposed to address the challenge of minimizing the degradation of quantum circuit performance due to factors such as circuit depth and the number of inserted SWAP gates while solving the qubit mapping problem. However, exact methods suffer from long runtime, lack of flexibility, and difficulty in scaling to larger circuits, while heuristic methods struggle to find the global optimum. Recently, solving the qubit mapping problem using machine learning approaches has emerged as a novel and promising solution. This paper studies qubit mapping optimization techniques based on machine learning, optimizing a model that solves the qubit mapping problem using the Deep Q-Network (DQN) algorithm, resulting in a SA-DQN model with superior performance in terms of circuit depth. The optimization efforts include improving the SWAP insertion strategy during the qubit mapping process and optimizing the model's initial mapping. Our SA-DQN model, tested on the IBM QX5 architecture and Rigetti 19Q Acorn architecture with a set of test circuits, achieved an improvement of 7.62% to 8.51% and 8.37% to 9.17% in circuit depth ratio compared to the original DQN model, respectively.
In the noisy intermediate-scale quantum era, quantum processing units suffer from, among others, highly limited connectivity between physical qubits. To make a quantum circuit effectively executable, a circuit transformation process is necessary to transform it, with overhead cost the smaller the better, into a functionally equivalent one so that the connectivity constraints imposed by the quantum processing unit are satisfied. Although several algorithms have been proposed for this goal, the overhead costs are often very high, which degenerates the fidelity of the obtained circuits sharply. One major reason for this lies in that, due to the high branching factor and vast search space, almost all of these algorithms only search very shallowly, and thus, very often, only (at most) locally optimal solutions can be reached. In this article, we propose a Monte Carlo Tree Search (MCTS) framework to tackle the circuit transformation problem, which enables the search process to go much deeper. The general framework supports implementations aiming to reduce either the size or depth of the output circuit through introducing SWAP or remote CNOT gates. The algorithms, called MCTS-Size and MCTS-Depth , are polynomial in all relevant parameters. Empirical results on extensive realistic circuits and IBM Q Tokyo show that the MCTS-based algorithms can reduce the size (respectively, depth) overhead by, on average, 66% (respectively, 84%) when compared with t ∣ket⟩ , an industrial-level compiler.
The design of quantum algorithms typically assumes the availability of an ideal quantum computer, characterized by full connectivity, noiseless operation, and unlimited coherence time. However, Noisy Intermediate-Scale Quantum (NISQ) devices present a stark contrast, with a limited number of qubits, non-negligible quantum operation errors, and stringent constraints on the connectivity of physical qubits within a Quantum Processing Unit (QPU). This necessitates the dynamic remapping of logical qubits to physical qubits within the compiler to facilitate the execution of two-qubit gates in the algorithm. However, this introduces additional operations, consequently reducing the fidelity of the algorithm. Therefore, minimizing the number of added gates becomes crucial. Finding such an optimal routing problem is NP-hard, and the task is conventionally addressed using human-crafted heuristics to search for SWAP sequences, but these lack performance guarantees. In this study, we employ a Seq2Seq machine learning model for the qubit routing task, incorporating a Transformer neural network to learn the routing information in the gate and SWAP sequence. Compared to heuristic search-based algorithms, our approach significantly reduces the overhead of quantum computing resources required to adapt logical circuits to physical circuits executable on specific quantum backend hardware.
Recently, deep neural networks have been proven capable of predicting output expectation values of certain random quantum circuits via a supervised learning approach. Here we investigate the potential of this possible approach to the emulation of quantum circuits, testing both its limitations and the successful applications where it might outperform conventional direct simulation methods. The testbeds we consider are circuits often employed in variational quantum algorithms, featuring layers of cnot gates alternated with single-qubit random rotations. On the one hand, we find that the computational cost of supervised learning scales exponentially with the interlayer variance of the random angles. This allows for entering a promising regime for quantum advantage, where quantum computers could easily outperform classical neural networks. On the other hand, circuits featuring only interqubit angle variations are easily emulated. In fact, thanks to a suitable scalable design, the trained networks accurately predict the expectation values of larger and deeper circuits than those used for training, even reaching circuit sizes, which, as we numerically show, are computationally intractable for the most common simulation libraries of state-vector and tensor-network algorithms. A repository of test data in the intractable regime is provided. We also analyze the most common metrics for the entanglement content, the expressibility, and the classical computational cost of quantum circuits, finding that they do not distinguish the easy from the hard circuit configurations.