QAP-Router: Tackling Qubit Routing as Dynamic Quadratic Assignment with Reinforcement Learning

📄 arXiv: 2605.12365v1 📥 PDF

作者: Kien X. Nguyen, Ankit Kulshrestha, Ilya Safro, Xiaoyuan Liu

分类: quant-ph, cs.AI

发布日期: 2026-05-12

💡 一句话要点

QAP-Router：利用强化学习和动态二次分配解决量子比特路由问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 量子计算 量子比特路由 二次分配问题 强化学习 Transformer网络

📋 核心要点

  1. 量子比特路由是量子计算中的关键瓶颈，现有方法难以在全局层面做出最优决策。
  2. QAP-Router将量子比特路由建模为动态二次分配问题，利用强化学习寻找最优解。
  3. 实验表明，QAP-Router在多个数据集上显著减少了CNOT门数量，优于现有编译器。

📝 摘要（中文）

量子比特路由是量子编译中的一个基本问题，已被证明是NP-hard问题。其动态特性使得局部路由决策随时间传播和复合，从而使全局高效的解决方案具有挑战性。现有的启发式方法依赖于具有有限前瞻性的局部规则，而最近基于学习的方法通常将路由视为通用的顺序决策问题，而没有充分利用其底层结构。本文介绍了一种名为QAP-Router的方法，该方法基于动态二次分配问题（QAP）公式来构建量子比特路由。通过将逻辑交互（或量子门）建模为流量矩阵，并将硬件拓扑建模为距离矩阵，我们的方法在一个统一的目标中捕获了交互-距离耦合，该目标定义了强化学习环境中的奖励。为了进一步利用这种结构，策略网络采用了一种解决方案感知的Transformer主干，该主干将流量矩阵和距离矩阵之间的交互编码到注意力机制中。我们还集成了一种前瞻机制，该机制自然地融入到QAP框架中，从而防止了短视决策。在来自MQTBench、AgentQ和QUEKO数据集的1,831个真实量子电路上的大量实验表明，相对于现有的工业编译器，我们的方法大大减少了路由电路的CNOT门数量，分别减少了15.7％，30.4％和12.1％。

🔬 方法详解

问题定义：量子比特路由问题旨在优化量子电路在物理量子比特上的映射和操作顺序，以最小化由于量子比特间的物理连接限制而引入的额外交换操作（SWAP门）。现有方法，如启发式算法，通常基于局部规则，缺乏全局视野，导致次优的路由方案。此外，将路由视为通用序列决策问题的方法，未能充分利用量子电路和硬件拓扑的内在结构。

核心思路：QAP-Router的核心思想是将量子比特路由问题建模为一个动态的二次分配问题（QAP）。通过将量子门操作的需求表示为“流量矩阵”，将量子比特之间的物理距离表示为“距离矩阵”，QAP的目标是找到一种分配方案，使得总的“流量”乘以“距离”最小。这种建模方式能够有效地捕捉量子电路的逻辑交互与硬件拓扑之间的耦合关系，从而指导路由决策。

技术框架：QAP-Router的整体框架是一个强化学习环境。环境状态包括当前的量子电路状态、物理量子比特的占用情况以及QAP的流量矩阵和距离矩阵。智能体（Agent）根据当前状态选择一个路由动作（例如，交换两个量子比特的位置）。环境根据该动作更新状态，并根据QAP的目标函数计算奖励。智能体通过与环境的交互学习到一个策略，该策略能够最大化累积奖励。

关键创新：QAP-Router的关键创新在于其将量子比特路由问题建模为动态QAP，并设计了一个解决方案感知的Transformer网络作为策略网络。该Transformer网络能够有效地编码流量矩阵和距离矩阵之间的交互信息，从而做出更明智的路由决策。此外，QAP-Router还集成了一个前瞻机制，允许智能体在做出决策前评估潜在的未来状态，从而避免短视行为。

关键设计：策略网络采用Transformer编码器结构，输入包括流量矩阵和距离矩阵的嵌入表示。注意力机制被设计为能够捕捉流量和距离之间的关系。奖励函数基于QAP的目标函数，鼓励减少总的“流量”乘以“距离”。前瞻机制通过模拟多个可能的未来动作来评估当前动作的潜在影响。

📊 实验亮点

QAP-Router在MQTBench、AgentQ和QUEKO三个真实量子电路数据集上进行了广泛的实验。实验结果表明，相对于现有的工业编译器，QAP-Router分别减少了15.7％，30.4％和12.1％的CNOT门数量。这些结果表明QAP-Router在量子比特路由问题上具有显著的优势。

🎯 应用场景

QAP-Router可应用于量子计算的编译优化流程，提高量子程序的执行效率。通过减少量子比特路由所需的交换操作，可以降低量子电路的深度和错误率，从而提升量子计算机的性能，加速量子算法的开发和应用，例如量子化学、材料科学、药物发现等领域。

📄 摘要（原文）

Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.