Timing-Aware Qubit Mapping and Gate Scheduling Adapted to Neutral Atom Quantum Computing

As a less developed but potential quantum technology, neutral atoms (NAs) can provide advantages, including higher qubit connectivity, longer-range interactions, and much more native multicontrol gates than superconductivity. Long-range interactions, however, prevent parallelism of interacting qubit pairs with their surrounding restriction zones. Therefore, the quantum program cannot be run directly on an NA quantum computer (NAQC) unless compiled. The recent compiling study of NAQC applies simple layer-by-layer scheduling and does not consider the difference in gate duration. To address the above issues, we focus on the qubit mapping and quantum gate scheduling (M&S) problem of quantum circuits to meet hardware constraints of superconductivity and even NAs. Our goal is to shorten the execution time to mitigate decoherence noise. We propose a block-game-like abstraction mechanism TETRIS which is an abstract model of the M&S problem and aware of the duration difference of gates and several other NA characteristics. Based on the abstraction, we propose a heuristic greedy algorithm (HGA) to solve the M&S problem efficiently. To further speed up the execution of the circuit, we embed HGA into a Monte Carlo tree search (MCTS) framework to solve the M&S problem, which consumes more compiling time but achieves a better result. Comparing our MCTS algorithm with the only recent M&S algorithm for NAQC, the average speedup ratio is $1.75\times $ for several quantum circuits collected from RevLib, and $1.18\times $ for circuits from Qiskit Lib.