论文标题
量子电路转换：蒙特卡洛树搜索框架
Quantum Circuit Transformation: A Monte Carlo Tree Search Framework
论文作者
论文摘要
在嘈杂的中间量子量子（NISQ）时代，量子处理单元（QPU）遭受了物理Qubits之间的高度有限的连通性。为了使量子电路有效地可执行，需要一个电路转换过程才能将其转换为转换，而开销的成本越小，将其变成功能等效的过程，以便满足QPU施加的连接性约束。尽管已经为此目标提出了几种算法，但间接费用通常很高，这使获得的电路的保真度急剧下降。这样做的一个主要原因在于，由于较高的分支因素和庞大的搜索空间，几乎所有这些算法仅搜索非常浅，因此，通常只能（最多）（最多）（最多）可以达到最佳的最佳解决方案。在本文中，我们提出了一个蒙特卡洛树搜索（MCT）框架来解决电路转换问题，这使搜索过程可以更深入。一般框架支持旨在通过引入交换或远程CNOT门来减少输出电路的大小或深度的实现。在所有相关参数中，称为MCTS-Size和MCT-Depth的算法均为多项式。广泛的现实电路和IBM Q Nokyo的经验结果表明，与工业水平的编译器相比，基于MCTS的算法平均可以降低66％（84％，分别）的大小（深度，分别）。
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.
