📚 课程目录第4章量子比特映射与初始布局

4. 量子比特映射与初始布局

在量子程序编译流程中，逻辑量子比特到物理量子比特的映射是连接“算法描述”与“硬件执行”的关键一步。量子程序通常以逻辑量子比特为单位编写，例如一个 5 量子比特的算法会声明 q[0] 到 q[4]；但真实量子处理器上的物理量子比特并非全连接，而是按照特定拓扑排列，例如 IBM 的 heavy-hex、Google 的 grid、Rigetti 的 ring 等。若两个逻辑量子比特在程序中频繁交互，却被映射到拓扑上距离很远的物理量子比特，那么每次两比特门都需要插入大量 SWAP 操作，导致线路深度和错误率急剧上升。因此，映射与初始布局直接决定了后续调度的可行性与执行质量。

映射问题的本质：交互图与拓扑图的嵌入

可以把量子程序抽象为一张交互图 G_L = (V_L, E_L)，其中每个顶点代表一个逻辑量子比特，每条边代表两个逻辑量子比特之间存在两比特门交互，边的权重可表示交互次数或关键路径权重。硬件则抽象为一张拓扑图 G_P = (V_P, E_P)，顶点是物理量子比特，边表示允许直接执行两比特门的耦合连接。映射问题就是寻找一个单射函数 f: V_L → V_P，使得交互图中高权重的边尽可能落在拓扑图的边上，或至少落在距离较近的物理量子比特之间。

这是一个典型的图嵌入问题，通常属于 NP 难。对于小规模程序可以精确求解，但实际量子程序动辄几十到上百个逻辑量子比特，必须依赖启发式算法。初始布局只决定“起点”，后续调度还会通过 SWAP 插入和路由来动态调整映射，但一个好的初始布局能显著减少后续 SWAP 数量。

初始布局对后续调度的影响

初始布局一旦确定，后续调度器就在此基础上进行路由和 SWAP 插入。影响主要体现在三个方面：

SWAP 数量：若交互图中权重最高的边被映射到拓扑上距离为 d 的两个物理比特，则每次该交互至少需要 d-1 次 SWAP 才能让两个量子比特相邻。SWAP 本身由 3 个 CNOT 组成，因此代价是 3(d-1) 个额外两比特门。
线路深度：SWAP 插入会串行化原本可以并行的门，增加关键路径长度。在含噪声的中等规模量子设备上，深度增加意味着退相干错误累积更多。
调度灵活性：好的初始布局为后续调度留出更多“空闲”物理比特作为路由中转站；差的布局可能让所有物理比特都处于高占用状态，导致路由时无路可走，只能强行长距离 SWAP。

以一个 5 逻辑比特、8 次两比特门交互的示例程序为例。假设交互次数分布为：q0-q1 交互 5 次，q1-q2 交互 3 次，q2-q3 交互 4 次，q3-q4 交互 2 次。若采用随机初始布局，平均每个高权重交互边在拓扑上的距离约为 2.5，预计需要插入约 18 次 SWAP；而采用启发式布局后，高权重边被优先放置在相邻物理比特上，SWAP 数量可降至约 6 次，线路深度减少约 40%。

交互图与拓扑图的匹配方法

匹配的核心思想是“让重要的边靠近”。常用方法包括：

度中心性匹配：计算交互图中每个逻辑量子比特的度（交互次数），以及拓扑图中每个物理量子比特的度（耦合数），将高度逻辑比特映射到高度物理比特，避免“热点”被放在拓扑边缘。
子图同构近似：寻找交互图在拓扑图中的最大公共子图，将匹配上的部分固定，剩余部分再分配。对于小规模交互图（≤10 节点），可用 VF2 等算法精确求解。
谱方法：分别计算交互图和拓扑图的拉普拉斯矩阵特征向量，将逻辑节点按第二小特征向量（Fiedler 向量）排序，物理节点同样排序，然后按序对应。这种方法能较好保持图的全局连通结构。
贪心增长：从交互图中权重最高的边开始，在拓扑图中找到一条边将其放置，然后逐步扩展相邻节点，每次选择使当前部分映射代价增量最小的物理位置。

启发式布局算法实战

下面给出一个可操作的贪心布局算法，适用于中等规模量子程序。算法输入为交互图 G_L（带边权）、拓扑图 G_P，输出为映射表。

输入：逻辑交互图 G_L = (V_L, E_L, w)，物理拓扑图 G_P = (V_P, E_P)
输出：映射 f: V_L → V_P

1. 计算 G_L 中每个逻辑节点的加权度 deg_L(v) = Σ w(v,u)
2. 计算 G_P 中每个物理节点的度 deg_P(p)
3. 将逻辑节点按 deg_L 降序排列，物理节点按 deg_P 降序排列
4. 取 deg_L 最大的逻辑节点 v0，将其映射到 deg_P 最大的物理节点 p0
5. 维护已映射集合 M 和候选物理节点集合 C = {p | p 与 M 中某节点相邻}
6. while 存在未映射逻辑节点：
     a. 在未映射逻辑节点中，选择与 M 中节点交互权重和最大的节点 v
     b. 在 C 中选择一个物理节点 p，使得将 v 映射到 p 后，
        新增的“距离代价”最小：cost(v,p) = Σ_{u∈M} w(v,u) · dist(p, f(u))
     c. 将 v 映射到 p，更新 M 和 C
7. 返回映射 f

以 5 逻辑比特、6 物理比特的示例为例。交互图边权为：q0-q1=5, q1-q2=3, q2-q3=4, q3-q4=2。拓扑图为 2×3 网格，物理节点 P0-P5，相邻关系为 P0-P1, P1-P2, P3-P4, P4-P5, P0-P3, P1-P4, P2-P5。

算法执行过程：deg_L(q0)=5, deg_L(q1)=8, deg_L(q2)=7, deg_L(q3)=6, deg_L(q4)=2。物理节点度均为 2 或 3（P1、P4 度为 3）。首先将 q1（度最大）映射到 P1（度最大）。然后候选物理节点为 P0, P2, P4。未映射节点中，q0 与 q1 交互权重 5，q2 与 q1 交互权重 3，因此选择 q0。计算 cost(q0, P0)=5×1=5，cost(q0, P2)=5×2=10，cost(q0, P4)=5×1=5。选择 P0 或 P4 均可，假设选 P0。接着 q2 与已映射的 q1 交互权重 3，与 q0 无直接交互，候选物理节点中 P2 距离 q1 为 1，距离 q0 为 2，cost=3×1=3；P4 距离 q1 为 1，距离 q0 为 1，cost=3×1=3。选择 P2。继续映射 q3 和 q4，最终得到映射：q0→P0, q1→P1, q2→P2, q3→P4, q4→P5。此时高权重边 q0-q1 在 P0-P1 上距离 1，q1-q2 在 P1-P2 上距离 1，q2-q3 在 P2-P4 上距离 2（需 1 次 SWAP），q3-q4 在 P4-P5 上距离 1。总距离代价为 5×1 + 3×1 + 4×2 + 2×1 = 18，相比随机布局的平均代价约 35，改善明显。

实践建议：在实际编译器中，初始布局通常与后续路由协同优化。可以先运行一次贪心布局，再执行轻量级路由模拟，统计 SWAP 数量；若 SWAP 过多，可对布局进行局部交换（如交换两个逻辑比特的映射）并重新评估，迭代若干次直到收敛。这种“布局-评估-微调”的循环在 Qiskit 的 SabreLayout 和 tket 的 Placement 中都有体现。

注意：初始布局不是一劳永逸的。当程序执行到中段，动态映射可能已经偏离初始布局。因此调度器需要持续跟踪当前映射状态，并在必要时触发重映射。初始布局的价值在于为整个执行过程提供一个良好的起点，降低早期阶段的 SWAP 压力。

总结来说，量子比特映射与初始布局是量子编译中“以空间换时间”的典型环节。通过将交互图与拓扑图进行结构化匹配，并采用贪心、谱方法或子图同构等启发式策略，可以在多项式时间内获得质量可观的布局方案，为后续调度和路由奠定基础。