GraMA: 一种梯度矩阵引导的量子比特映射问题求解分配方法

《Future Generation Computer Systems》：GraMA: A Gradient Matrix-Guided Assignment Method for Solving Qubit Mapping Problems

　　

量子比特映射是关键的编译过程，它将量子电路中的逻辑量子比特分配给量子硬件上的物理量子比特，确保在噪声中等规模量子（NISQ）计算机上高效可靠地执行。然而，随着量子计算机规模和电路复杂性的增加，现有映射方法面临显著的计算复杂性和次优的映射质量。本研究将逻辑到物理的量子比特映射问题形式化为矩阵形式的优化问题，以应对可扩展性和计算效率的挑战。提出的方法通过一次矩阵微分计算该矩阵形式问题的梯度，并将其作为指导来确定增强的量子比特分配，无需迭代组合探索和优化求解器。仿真结果表明，即使对于多编程场景和大规模量子计算机，该方法在实现相当执行可靠性的同时，显著减少了编译时间。

### 论文解读：GraMA——基于梯度矩阵引导的量子比特映射方法

#### 研究背景与问题
量子计算利用量子力学原理（如叠加和纠缠）进行计算，有望解决经典计算机难以处理的复杂问题。当前量子计算机处于噪声中等规模量子（NISQ）时代，包含数十到数百个量子比特（qubit），并通过云平台（如IBM、Intel、Google）供用户远程访问。量子程序通常表示为量子电路，由一系列量子门（如Hadamard、Pauli-X、CNOT）组成。为了在硬件上执行，需要编译过程将高级量子程序转换为低级量子电路，其中量子比特映射（qubit mapping）是关键环节，它决定逻辑量子比特到物理量子比特的最优分配，需考虑NISQ硬件固有的连接限制和错误率。此外，量子多编程（multi-programming）技术被提出以提高资源利用率，它将多个量子电路同时映射到同一硬件的不同物理量子比特子集，但引入了不重叠分配和连通性约束等挑战。

现有映射方法分为启发式方法（如SABRE、NASSC）和数学建模方法（如整数线性规划（ILP）、可满足性模理论（SMT）、二次分配问题（QAP））。启发式方法依赖搜索或贪婪策略，可能陷入局部最优；数学建模方法虽能保证全局最优，但随问题规模增大面临巨大计算复杂度，难以扩展到数百个物理量子比特。这些挑战在多编程场景中更加突出。因此，需要一种实用、可扩展且计算高效的编译方法，能在不断增长的硬件和程序复杂度下提供高可靠性映射。

本研究聚焦于初始布局（initial layout）阶段，旨在确定最优逻辑到物理量子比特分配，以最大化整体执行可靠性并提高计算效率。研究人员提出了GraMA（Gradient Matrix-guided Assignment Method），一种利用矩阵形式化高效确定增强量子比特分配的方法。该方法将逻辑量子比特需求和物理量子比特约束表示为矩阵，通过单次矩阵微分计算梯度，并以此指导分配，避免了迭代优化和穷举组合搜索。仿真实验表明，即使对于多编程场景和大规模量子硬件，GraMA能在保持相当执行可靠性的同时显著降低编译时间。该研究发表在《Future Generation Computer Systems》。

#### 主要关键技术方法
研究人员使用了以下关键技术方法（忽略试剂和具体操作步骤，样本队列来自IBM量子计算机模拟环境）：（1）**矩阵构建**：构建加权距离矩阵（W），通过Floyd-Warshall算法计算物理量子比特对间的最短路径，边权重为两量子比特门错误率的负对数；构建单量子比特成本矩阵（S），基于读取错误率和单量子比特门错误率；构建逻辑邻接矩阵（A），表示各电路中逻辑量子比特间的交互关系。（2）**梯度计算**：将映射问题形式化为矩阵形式的QAP目标函数，利用连续分配矩阵（X_c）替代离散矩阵，通过矩阵微分计算梯度（?X_cf = 2WX_cA + γS），其中梯度项编码了物理量子比特中心性与逻辑量子比特连通性的交互信息。（3）**梯度引导分配过程**：按电路大小降序处理电路，对每个电路内的逻辑量子比特按度数（降序）和梯度最大值（降序）排序，然后根据梯度矩阵为每个逻辑量子比特选择具有最小梯度值的有效物理量子比特，并施加邻域约束以避免重复分配。

#### 研究结果
**单编程场景（Single-programming）**：在Toronto（27量子比特）、Brooklyn（65量子比特）和Torino（133量子比特）三个IBM量子计算机上测试。GraMA在Toronto和Brooklyn上实现了比SABRE-layout、noise-adaptive mapping和QuCloud+更高的成功试验概率（PST），例如使用NASSC路由时，PST分别最高提升16.0%、6.0%和3.6%（Toronto），以及8.3%、2.5%和1.2%（Brooklyn）。在Torino上，GraMA的PST（84.4%）与QuCloud+（84.6%）和noise-adaptive mapping（85.4%）相当。SWAP门数量和电路深度方面，GraMA与现有方法相当或更优，表明其在高执行可靠性下保持了可比的SWAP开销。

**多编程场景（Multi-programming）**：在双编程实验中，GraMA使用NASSC路由在Toronto、Brooklyn和Torino上分别实现了54.58%、82.35%和88.61%的PST，优于QuCloud+的54.36%、81.12%和86.89%。随着并发电路数量增至4、6、8个，GraMA在Brooklyn上使用NASSC路由时，PST始终最高（约80.2%–80.5%），在Torino上仅次于noise-adaptive mapping。GraMA的SWAP门数量和电路深度与其他基线方法相当或更优，表明该方法在多电路放置下仍保持编译质量。

**执行时间（Execution time）**：从单编程到8编程，GraMA的执行时间始终最低（低于10毫秒）。与SABRE-layout和noise-adaptive mapping相比，GraMA在所有硬件上平均计算加速5.51倍（Toronto上3.19倍，Brooklyn上4.18倍，Torino上7.76倍），最大加速达14.29倍（Torino单编程场景）。相比之下，SABRE-layout和noise-adaptive mapping的执行时间随电路数和硬件规模显著增长。

#### 总结与结论
本文解决了量子编译中高效可扩展的量子比特映射挑战，提出了基于梯度矩阵的GraMA方法。该方法利用矩阵形式的二次分配问题（QAP）建模映射问题，并通过矩阵计算高效识别增强的逻辑到物理量子比特分配，无需迭代组合搜索。仿真结果表明，GraMA在实现相当执行可靠性的同时，显著降低编译时间（最高14.29倍，平均5.51倍），即使对于多编程场景和大规模量子硬件。随着量子计算从实验演示转向实际应用，该工作为未来量子计算机的编译挑战提供了可扩展且理论扎实的方法论。研究结论翻译如下：本文解决了量子编译中高效可扩展的量子比特映射挑战，提出了基于梯度矩阵的GraMA方法以确定增强的逻辑到物理量子比特分配。该方法利用矩阵形式的二次分配问题（QAP）建模映射问题，并通过矩阵计算高效识别增强分配，无需迭代组合搜索。仿真结果表明，GraMA在实现相当执行可靠性的同时，显著降低编译时间（最高14.29倍，平均5.51倍），即使对于多编程场景和大规模量子硬件。随着量子计算从实验演示转向实际应用，该工作为未来量子计算机的编译挑战提供了可扩展且理论扎实的方法论。