Qubit Routing Using Graph Neural Network Aided Monte Carlo Tree Search

• Published in: Proceedings of the ... AAAI Conference on Artificial Intelligence 2022-06, Vol.36 (9), p.9935-9943
• Main Authors: Sinha, Animesh, Azad, Utkarsh, Singh, Harjinder
• Format: Article
• Language: English
• ISSN: 2159-5399; 2374-3468
• DOI: 10.1609/aaai.v36i9.21231

Near-term quantum hardware can support two-qubit operations only on the qubits that can interact with each other. Therefore, to execute an arbitrary quantum circuit on the hardware, compilers have to first perform the task of qubit routing, i.e., to transform the quantum circuit either by inserting additional SWAP gates or by reversing existing CNOT gates to satisfy the connectivity constraints of the target topology. The depth of the transformed quantum circuits is minimized by utilizing the Monte Carlo tree search (MCTS) to perform qubit routing by making it both construct each action and search over the space of all actions. It is aided in performing these tasks by a Graph neural network that evaluates the value function and action probabilities for each state. Along with this, we propose a new method of adding mutex-lock like variables in our state representation which helps factor in the parallelization of the scheduled operations, thereby pruning the depth of the output circuit. Overall, our procedure (referred to as QRoute) performs qubit routing in a hardware agnostic manner, and it outperforms other available qubit routing implementations on various circuit benchmarks.