Minor Embedding for Quantum Annealing with Reinforcement Learning
作者: Riccardo Nembrini, Maurizio Ferrari Dacrema, Paolo Cremonesi
分类: quant-ph, cs.LG
发布日期: 2025-07-21
💡 一句话要点
提出基于强化学习的量子退火次嵌入方法，提升问题规模和硬件拓扑的泛化性
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 量子退火 次嵌入 强化学习 组合优化 近端策略优化
📋 核心要点
- 量子退火中的次嵌入步骤计算成本高昂，且现有启发式算法难以泛化到不同问题图和硬件拓扑。
- 利用强化学习将次嵌入视为序列决策过程，智能体通过迭代映射问题变量学习构建次嵌入。
- 实验表明，该方法在Chimera和Zephyr拓扑上均能生成有效次嵌入，尤其在Zephyr上表现更佳，并具备良好的扩展性。
📝 摘要（中文）
量子退火(QA)是一种量子计算范式，用于解决组合优化问题，这些问题被形式化为二次无约束二元优化(QUBO)问题。QA的一个关键步骤是次嵌入，它将问题图映射到量子处理器的稀疏拓扑结构上。这个过程计算开销大，并且随着问题规模和硬件复杂性的增加，扩展性较差。现有的启发式方法通常是为特定的问题图或硬件拓扑结构开发的，难以推广。强化学习(RL)提供了一种有前景的替代方案，它将次嵌入视为一个序列决策问题，其中智能体通过迭代地将问题变量映射到硬件量子比特来学习构建次嵌入。我们提出了一种基于近端策略优化(PPO)智能体的基于RL的次嵌入方法，测试了其在Chimera和Zephyr两种硬件拓扑结构上嵌入完全连接和随机生成的问题图的能力。结果表明，我们的智能体能够始终如一地产生有效的次嵌入，并且量子比特数量相当有效，特别是在更现代的Zephyr拓扑结构上。我们提出的方法还能够扩展到中等问题规模，并且能够很好地适应不同的图结构，突出了RL作为QA中次嵌入的灵活和通用框架的潜力。
🔬 方法详解
问题定义：论文旨在解决量子退火中次嵌入过程的计算开销大和泛化性差的问题。现有的启发式方法通常针对特定问题图和硬件拓扑设计，难以适应不同场景，限制了量子退火的应用范围。
核心思路：论文的核心思路是将次嵌入问题建模为一个序列决策过程，利用强化学习训练智能体，使其能够根据当前状态逐步选择最优的映射方案，从而构建有效的次嵌入。这种方法旨在提高次嵌入过程的灵活性和泛化能力，使其能够适应不同的问题图和硬件拓扑。
技术框架：整体框架包括一个强化学习智能体（基于近端策略优化PPO算法）和一个环境。环境模拟量子退火硬件拓扑，并根据智能体的动作（即变量到量子比特的映射）更新状态。智能体通过与环境交互，学习如何构建有效的次嵌入。具体流程如下：1. 初始化问题图和硬件拓扑；2. 智能体观察当前状态；3. 智能体根据策略选择动作；4. 环境执行动作，更新状态并返回奖励；5. 智能体根据奖励更新策略；6. 重复步骤2-5，直到达到终止条件。
关键创新：该方法最重要的创新点在于将强化学习引入到量子退火的次嵌入过程中，打破了传统启发式算法的局限性。通过强化学习，智能体能够自主学习最优的映射策略，从而提高次嵌入的效率和泛化能力。与现有方法相比，该方法不需要针对特定问题图或硬件拓扑进行专门设计，具有更强的适应性。
关键设计：论文使用近端策略优化（PPO）算法训练智能体。状态空间包括问题图的连接信息、已映射变量的信息以及硬件拓扑的可用资源信息。动作空间定义了将问题变量映射到硬件量子比特的所有可能方式。奖励函数的设计至关重要，它鼓励智能体生成有效的次嵌入，同时惩罚无效的映射。具体的奖励函数包括：1. 连接奖励：奖励成功连接问题变量的动作；2. 资源惩罚：惩罚使用过多量子比特的动作；3. 无效映射惩罚：惩罚导致无效次嵌入的动作。此外，论文还探索了不同的网络结构和超参数设置，以优化智能体的性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，基于强化学习的次嵌入方法在Chimera和Zephyr两种硬件拓扑上均能生成有效的次嵌入。尤其在更现代的Zephyr拓扑上，该方法表现出更高的效率，使用的量子比特数量更少。此外，该方法还能够扩展到中等问题规模，并能够很好地适应不同的图结构，验证了强化学习在量子退火次嵌入中的潜力。
🎯 应用场景
该研究成果可应用于各种组合优化问题的量子退火求解，例如金融建模、物流优化、机器学习等。通过提高次嵌入的效率和泛化能力，可以扩大量子退火的应用范围，并加速量子计算在实际问题中的应用。未来，该方法有望应用于更大规模、更复杂的优化问题，并推动量子计算技术的发展。
📄 摘要（原文）
Quantum Annealing (QA) is a quantum computing paradigm for solving combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. An essential step in QA is minor embedding, which maps the problem graph onto the sparse topology of the quantum processor. This process is computationally expensive and scales poorly with increasing problem size and hardware complexity. Existing heuristics are often developed for specific problem graphs or hardware topologies and are difficult to generalize. Reinforcement Learning (RL) offers a promising alternative by treating minor embedding as a sequential decision-making problem, where an agent learns to construct minor embeddings by iteratively mapping the problem variables to the hardware qubits. We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem graphs on two hardware topologies, Chimera and Zephyr. The results show that our agent consistently produces valid minor embeddings, with reasonably efficient number of qubits, in particular on the more modern Zephyr topology. Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL's potential as a flexible and general-purpose framework for minor embedding in QA.