标题： CHARME：一种基于链的强化学习方法用于小嵌入问题 显示英文标题

标题： CHARME: A chain-based reinforcement learning approach for the minor embedding problem

摘要： 量子退火（QA）在高效解决组合优化问题方面具有巨大潜力。 然而，QA算法的有效性在很大程度上依赖于将问题实例（表示为逻辑图）嵌入到量子单元处理（QPU）中，其拓扑结构为有限连通图，这被称为次级嵌入问题。 现有的次级嵌入方法在面对较大问题规模时存在可扩展性问题。 在本文中，我们提出了一种利用强化学习（RL）技术来解决次级嵌入问题的新方法，称为CHARME。 CHARME包括三个关键组件：用于策略建模的图神经网络（GNN）架构、确保解决方案有效性的状态转移算法，以及用于有效训练的顺序探索策略。 通过在合成和现实世界实例上的全面实验，我们证明了我们提出的顺序探索策略以及我们的RL框架CHARME的效率。 具体来说， CHARME相比快速嵌入方法如Minorminer和ATOM产生了更优的解决方案。 此外，我们的方法在某些情况下超过了以运行时间较慢但解决方案质量高而闻名的基于OCT的方法。 此外，我们提出的探索方法通过提供比贪心策略更好的解决方案，提高了CHARME框架训练的效率。 显示英文摘要

摘要： 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.