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 executable, a circuit transformation process is necessary to transform it into a functionally equivalent one so that the connectivity constraints imposed by the QPU are satisfied. Due to the high branching factor and vast search space, almost all existing algorithms search very shallowly and thus, very often, can reach (at most) locally optimal solutions. We propose a Monte Carlo Tree Search framework to tackle this problem, which enables the search process to go deeper. In particular, we design, by taking both short- and long-term rewards into consideration, a scoring mechanism, and propose to use a fast random strategy for simulation. The thus designed search algorithm is polynomial in all relevant parameters and empirical results on extensive realistic circuits show that it can reduce, in average, the size of the output circuits by at least 30% when compared with the state-of-the-art algorithms on IBM Q20.
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 executable, a circuit transformation process is necessary to transform it into a functionally equivalent one so that the connectivity constraints imposed by the QPU are satisfied. Due to the high branching factor and vast search space, almost all existing algorithms search very shallowly and thus, very often, can reach (at most) locally optimal solutions. We propose a Monte Carlo Tree Search framework to tackle this problem, which enables the search process to go deeper. In particular, we design, by taking both short- and long-term rewards into consideration, a scoring mechanism, and propose to use a fast random strategy for simulation. The thus designed search algorithm is polynomial in all relevant parameters and empirical results on extensive realistic circuits show that it can reduce, in average, the size of the output circuits by at least 30% when compared with the state-of-the-art algorithms on IBM Q20.
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.
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.
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.
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.
Hamiltonian simulation is one of the most promising paths toward quantum advantage. Most prior approaches to Hamiltonian simulation circuit synthesis focus on local rewrite rules and low-level optimizations, and give limited attention to high-level scheduling of Pauli terms under varying constraints. In practice, different simulation algorithms require different orderings of the Pauli terms, yet many prior IR-based methods assume a fixed commutation structure, which limits their flexibility.
We present MonteQ, a novel quantum circuit synthesis framework for Hamiltonian simulation. MonteQ leverages a two-level design that combines low-level synthesis heuristics with an upper-level tree structure to explore sequences of Pauli rotations. To avoid enumerating this factorially large tree, the Monte Carlo Tree Search algorithm serves as workhorse for judiciously exploring promising paths to leaf nodes. With this two-level design, MonteQ supports both logical-level and hardware-aware synthesis by selecting different low-level heuristics. It also supports different ordering constraints on the Pauli rotations by adjusting the high-level tree structure. For example, MonteQ can preserve the target unitary by using a directed acyclic graph that records the commutation relations among the Pauli rotations, or it can relax unitary preservation constraint to uncover additional optimization options. Our experimental results show that MonteQ can achieve an improvement, as measured in CNOT gate counts, of up to 53% (30% on average) against state-of-the-art compilers like Rustiq on a set of representative synthesis tasks.
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 ofn!different initial mappings for a qubit mapping problem withnqubits, 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.