Quantum computing is gaining more and more attention due to its huge potential and the constant progress in quantum computer development. IBM and Google have released quantum architectures with more than 50 qubits. However, in these machines, the physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of the physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. It consists of two steps, initial mapping and qubit routing. Here we propose a reinforcement learning-based model to solve the initial mapping problem. Initial mapping is formulated as sequence-to-sequence learning and self-attention network is used to extract features from a circuit. For qubit routing, a DEAR (Dynamically-Extract-and-Route) framework is proposed. The framework iteratively extracts a subcircuit and uses A* search to determine when and where to insert additional gates. It helps to preserve the lookahead ability dynamically and to provide more accurate cost estimation efficiently during A* search. The experimental results show that our RL-model generates better initial mappings than the best known algorithms with 12% fewer additional gates in the qubit routing stage. Furthermore, our DEAR-framework outperforms the state-of-the-art qubit routing approach with 8.4% and 36.3% average reduction in the number of additional gates and execution time starting from the same initial mapping.
Quantum computing is gaining more and more attention due to its huge potential and the constant progress in quantum computer development. IBM and Google have released quantum architectures with more than 50 qubits. However, in these machines, the physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of the physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. It consists of two steps, initial mapping and qubit routing. Here we propose a reinforcement learning-based model to solve the initial mapping problem. Initial mapping is formulated as sequence-to-sequence learning and self-attention network is used to extract features from a circuit. For qubit routing, a DEAR (Dynamically-Extract-and-Route) framework is proposed. The framework iteratively extracts a subcircuit and uses A* search to determine when and where to insert additional gates. It helps to preserve the lookahead ability dynamically and to provide more accurate cost estimation efficiently during A* search. The experimental results show that our RL-model generates better initial mappings than the best known algorithms with 12% fewer additional gates in the qubit routing stage. Furthermore, our DEAR-framework outperforms the state-of-the-art qubit routing approach with 8.4% and 36.3% average reduction in the number of additional gates and execution time starting from the same initial mapping.
In current quantum devices, physical qubits are not fully connected so that two-qubit interaction can only be performed between specific pairs of physical qubits. To execute a quantum circuit, it is necessary to transform it into a functionally equivalent one that respects the constraints imposed by the target architecture. Quantum circuit transformation inevitably introduces additional gates which reduces the fidelity of the circuit. Therefore, it is important that the transformation method completes the transformation with minimal overheads. Quantum circuit transformation consists of two steps, initial mapping and qubit routing, and here we propose a DEAR (Dynamically-Extract-and-Route) framework to solve the qubit routing problem. A key insight of DEAR is that by maintaining a sufficient lookahead ability all the time, we can make much better routing decisions while effectively controlling the runtime. In our DEAR framework, we periodically extract a subcircuit by identifying a set of remaining gates that should be executed earlier than the others, and then applies A* search to determine how to insert a sequence of additional SWAP and BRIDGE operations into the subcircuit to obtain a high quality routing solution with minimum number of additional gates. In this work, we consider the insertion of both SWAP and BRIDGE operations while most previous works deal with SWAP insertion only. We evaluate our approach with four benchmark sets with different characterization on IBM Tokyo. The experimental results show that our approach outperforms the state-of-the-art work utilizing SWAP and BRIDGE insertion with 19.1% and 77.5% average reduction in the number of additional gates and runtime, respectively, starting from the same initial mapping. We also performed experiments on larger quantum devices such as Google Sycamore and IBM Rochester both with 53 physical qubits that have largely different architectures from one another and from IBM Tokyo. Again, DEAR was much faster and required significantly less amount of additional gates.
Qubit routing is the process of transforming quantum circuits to ensure that all two-qubit operations obey the connectivity constraints of a target architecture. The severe limitations of NISQ computers make qubit routing a vital compilation step. We propose a method to route quantum circuits based on deep reinforcement learning (RL). Moreover, we augment our approach with device calibration data to enable routing decisions based on the reliability of individual gates and we improve upon a previous technique for encoding circuits as a numerical matrix. We also implement enhancements such as BRIDGE operations, qubit embeddings, and commutation analysis. Using proximal policy optimization (PPO), we trained agents for five IBM topologies with between 5 and 27 qubits. For random circuits, the proposed strategy reduced the number of additional two-qubit gates by up to 37.3% and improved estimated success probability by up to 26.8% compared to the best algorithm from the Qiskit framework. For a dataset of realistic circuits, we achieved up to 27.5% and 15.2% improvements in gate count and circuit fidelity, respectively. We found no significant advantage from using calibration-aware models for IBM architectures, which deserves further exploration. Our work helps cement RL as a valuable qubit routing strategy, serving as another stepping stone toward practical applications for quantum computing.
A quantum compiler is a critical piece in the quantum computing pipeline since it allows an abstract quantum circuit to be run on a physical quantum computer. One extremely important subproblem in quantum compilation is the generation of a logical to physical qubit mapping. Typically in quantum compilers this step is either implemented as a random or a heuristic based assignment that aims to minimize additional (SWAP) gate overhead in the quantum circuit.
In this paper, we present an alternative approach to solving the qubit mapping problem. Specifically, we formulate the qubit mapping problem with a combinatorial optimization (CO) objective. We then present a method to find a solution to the CO problem by training a reinforcement learning (RL) policy. We also propose a local search based post-processing algorithm to further reduce the overhead. Our results show a dramatic improvement over conventional techniques in reducing the number of SWAPs. On different real world datasets like MQTBench and Queko circuits, our trained policy achieves a \textbf{65-85\%} reduction in SWAP overhead when compared to existing quantum compilers.
Abstract Quantum circuit optimization is an inevitable task with the current noisy quantum backends. This task is considered non-trivial due to the varying circuits’ complexities in addition to hardware-specific noise, topology, and limited connectivity. The currently available methods either rely on heuristics for circuit optimization tasks or reinforcement learning with complex unscalable neural networks such as transformers. In this paper, we are concerned with optimizing the initial logical-to-physical mapping selection. Specifically, we investigate whether a reinforcement learning agent with simple scalable neural network is capable of finding a near-optimal logical-to-physical mapping, that would decrease as much as possible additional CNOT gates, only from a fixed-length feature vector. To answer this question, we train a Maskable Proximal Policy Optimization agent to progressively take steps towards a near-optimal logical-to-physical mapping on a 20-qubit hardware architecture. Our results show that our agent coupled with a simple routing evaluation is capable of outperforming other available reinforcement learning and heuristics approaches on 12 out of 19 test benchmarks, achieving geometric mean improvements of 2.2% and 15% over the best available related work and two heuristics approaches, respectively. Additionally, our neural network model scales linearly as the number of qubits increases.
Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.
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.