4. 量子比特映射与路由

量子程序在编译前端通常以逻辑量子比特为单位书写，例如 q[0]、q[1]、q[2]。但真实超导量子处理器上的物理量子比特并不是全连接的：它们按固定拓扑排布，常见有线性链、T 型、重六边形（heavy-hex）等结构。若逻辑线路中某个双比特门作用在两个逻辑比特上，而它们被映射到的物理比特之间没有直接耦合边，这个门就无法直接执行。量子比特映射与路由要解决的核心问题就是：为逻辑比特选择物理位置（初始布局），并在必要时通过插入 SWAP 门把参与交互的量子态搬运到相邻位置，使所有双比特门都能在硬件允许的边上执行。

这一过程不是简单的“找位置”，而是要在保真度、深度、门数、串扰等多个目标之间权衡。下面按初始布局、SWAP 插入、Steiner 树路由、噪声感知映射和评估指标五个层面展开。

初始布局：把逻辑比特放到哪里

初始布局（initial layout）是一个从逻辑比特到物理比特的单射映射。最简单的策略是“按编号顺序放置”，即 q[i] → Q[i]。它实现简单，但完全忽略线路的交互结构：如果逻辑线路中 q[0] 与 q[7] 交互频繁，而物理上 Q[0] 与 Q[7] 相距很远，后续路由代价会很高。

更合理的做法是交互感知布局：先统计逻辑线路中双比特门的交互频次，构造交互图（interaction graph），再把它嵌入到硬件耦合图中，使高频交互的逻辑比特尽量落在相邻或近邻的物理比特上。常用方法包括：

• 贪心放置：按交互度从高到低依次为逻辑比特选择“与已放置邻居距离最小”的物理比特。
• 图嵌入/子图同构：寻找交互图在耦合图中的近似嵌入，适合交互图较小的情况。
• 启发式与元启发式：如模拟退火、遗传算法，在大规模线路中搜索更优布局。

以一个 5 比特线性链 Q0—Q1—Q2—Q3—Q4 为例，若逻辑线路中 q0 与 q1、q1 与 q2 交互最频繁，则把 q0,q1,q2 依次放到 Q0,Q1,Q2 上，可让这三个高频门全部落在相邻边上，几乎不需要路由。

SWAP 插入：把量子态搬到相邻位置

当某个双比特门的两端在物理上不相邻时，需要沿耦合图的一条路径，把其中一个量子态逐步“交换”到目标比特旁边。SWAP 门交换两个物理比特的量子态，连续插入 SWAP 等价于沿路径搬运量子态。例如要把 Q0 上的态搬到 Q3，路径为 Q0—Q1—Q2—Q3，可依次执行 SWAP(Q0,Q1)、SWAP(Q1,Q2)、SWAP(Q2,Q3)，共 3 个 SWAP。

SWAP 插入的关键决策是：选哪条路径、搬哪个量子态、插入多少 SWAP。常见策略有：

• 最短路径优先：在耦合图上用 BFS 找两端间最短路径，沿路径插入 SWAP。实现简单，但可能忽略噪声差异。
• 最少 SWAP 数：在多个候选路径中选择 SWAP 数最少的，减少门数和深度。
• 前瞻式路由：不仅看当前门，还看后续若干门，避免“搬过去又搬回来”的反复交换。

SWAP 本身由 3 个 CNOT 实现，代价较高，因此路由质量直接影响线路的最终保真度。一个实用的优化是：若后续门恰好需要被交换的量子态，则这次 SWAP 可能“顺路”有用，应优先保留而非撤销。

Steiner 树路由：一次搬运服务多个门

当多个逻辑比特需要与同一个逻辑比特交互，或一组门共享相同的物理区域时，逐门做最短路径会重复搬运。Steiner 树路由的思想是：在耦合图上构造一棵连接所有相关物理比特的最小 Steiner 树，树的总边数尽量少，然后沿树的边集中插入 SWAP，使多个交互一次性满足。

例如逻辑比特 a 需要分别与 b、c、d 交互，而 b、c、d 在物理上分散。若分别路由，可能要走三条独立路径；若先构造连接 a、b、c、d 的 Steiner 树，再沿树边搬运，可共享公共路径，减少总 SWAP 数。Steiner 树路由特别适合交互呈“星型”或“局部聚集”的线路。

实现上，通常先用最短路径或最小生成树近似构造 Steiner 树，再在树的边上安排 SWAP 顺序，使每个目标门在其两端相邻时执行。需要注意：Steiner 树路由并不总是最优，当交互分散且无共享路径时，其收益有限，此时逐门最短路径反而更简单。

噪声感知映射：不只看距离，还要看质量

真实硬件的每条耦合边、每个物理比特的保真度并不相同。某些边 CNOT 错误率明显更高，某些比特读取错误率或退相干时间更差。噪声感知映射（noise-aware mapping）在布局和路由时把噪声指标纳入代价函数，而不是只最小化 SWAP 数或深度。

常见做法是给每条边赋一个“代价权重”，例如：

edge_cost(u, v) = -log( F_CNOT(u, v) ) + λ · T_gate

其中 F_CNOT 是该边 CNOT 保真度，T_gate 是门时间，λ 是权重系数。路由时选择总代价最小的路径，而非边数最少的路径。布局阶段也可优先把高频交互的逻辑比特放到高保真度边上。

噪声感知映射的典型收益是：在 SWAP 数略增的情况下，整体线路保真度反而更高。例如某条 2 跳路径的 CNOT 保真度分别为 0.995 和 0.996，而一条 1 跳路径保真度仅 0.97，则走 2 跳可能更优。因此评估映射算法时，不能只看 SWAP 数，还要看最终保真度。

评估指标：如何判断映射与路由的好坏

评估映射与路由质量，常用以下指标：

指标	含义	观察方式
SWAP 数	插入的 SWAP 门总数	编译后线路统计
线路深度	关键路径上的门层数	调度后 DAG 深度
CNOT 总数	含 SWAP 展开后的双比特门数	门计数
估计保真度	各门保真度乘积或噪声模型估计	噪声模型仿真
路由开销比	插入 SWAP 数 / 原始双比特门数	比值越小越好

实际评估时，建议同时报告 SWAP 数、深度和估计保真度，避免单一指标误导。例如某算法 SWAP 数最少，但把门集中到低质量边上，最终保真度可能反而更差。

综合来看，映射与路由是一个多目标优化问题：初始布局决定起点，SWAP 插入决定搬运代价，Steiner 树路由在共享路径时降低开销，噪声感知映射把硬件质量纳入决策，评估指标则用于量化比较。实际编译中，通常先做交互感知布局，再结合噪声权重做路由，最后用 SWAP 数、深度和估计保真度共同判断方案优劣。