Researchers Propose A Monte Carlo Tree Search Framework for Quantum Circuit Transformation

(QuantumPhysicsArchive) A team of scientists from China and Australia have proposed a A Monte Carlo tree search framework for quantum circuit transformation in noisy intermediate-scale quantum (NISQ).
Quantum processing units (QPUs) suffer from ighly 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. 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. Onem ajor 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 bereached.
In their recently published paper, the scientists propose propose a Monte Carlo Tree Search (MCTS) framework to tackle this problem, which enables the search process to go much deeper. In particular, we carefully 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 often reduce the size of output circuits by at least30% when compared with the state-of-the-art algorithms on IBM Q20.
The researchers are Xiangzhen Zhou, Yuan Fengm and Sanjiang.  Their  institutions are: State Key Lab of Millimeter Waves, Southeast University, Nanjing 211189, China2Centre for Quantum Software and Information, Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia