Quantum Annealing (QA) holds great potential for solving combinatorial
optimization problems efficiently. However, the effectiveness of QA algorithms
heavily relies on the embedding of problem instances, represented as logical
graphs, into the quantum unit processing (QPU) whose topology is in form of a
limited connectivity graph, known as the minor embedding Problem. Existing
methods for the minor embedding problem suffer from scalability issues when
confronted with larger problem sizes. In this paper, we propose a novel
approach utilizing Reinforcement Learning (RL) techniques to address the minor
embedding problem, named CHARME. CHARME includes three key components: a Graph
Neural Network (GNN) architecture for policy modeling, a state transition
algorithm ensuring solution validity, and an order exploration strategy for
effective training. Through comprehensive experiments on synthetic and
real-world instances, we demonstrate that the efficiency of our proposed order
exploration strategy as well as our proposed RL framework, CHARME. In details,
CHARME yields superior solutions compared to fast embedding methods such as
Minorminer and ATOM. Moreover, our method surpasses the OCT-based approach,
known for its slower runtime but high-quality solutions, in several cases. In
addition, our proposed exploration enhances the efficiency of the training of
the CHARME framework by providing better solutions compared to the greedy
strategy.

通过使用强化学习等技术解决量子退火中的 “次嵌入问题”，该研究提出了一种名为 CHARME 的方法，包括用于策略建模的图神经网络架构、确保解的有效性的状态转换算法和有效的训练顺序探索策略。实验证明，CHARME 的效率优于 Minorminer 和 ATOM 等嵌入方法，并在某些情况下超过 OCT-based 方法。此外，提出的探索策略还提高了 CHARME 框架的训练效率。