4. 拓扑映射问题定义与复杂度
在量子芯片上执行一个量子线路，并不是把逻辑线路里的量子门逐条“翻译”成脉冲那么简单。真实芯片的量子比特只与物理邻居直接耦合，而逻辑线路中的两比特门可以作用在任意一对逻辑比特上。拓扑映射（Topological Mapping）要解决的，就是如何把逻辑线路中的比特和门，安排到物理芯片的耦合图上，使得所有两比特门都能在允许的连边上执行。本节围绕这个问题的形式化定义、三个核心子问题、复杂度来源以及评价指标展开。
一、问题的形式化定义
给定一个逻辑量子线路 L，它包含 n 个逻辑量子比特 q0…qn-1 和按时间排序的门序列；再给定物理芯片的耦合图 G = (V, E)，其中 V 是物理量子比特集合，E 是允许执行两比特门的连边集合。拓扑映射的目标是构造一个映射关系 π: 逻辑比特 → 物理比特，并允许在必要时插入 SWAP 门改变映射，使得线路中每个两比特门作用的两端在物理图上相邻，同时使总代价（通常是新增 SWAP 数或线路深度）尽可能小。
这里有一个关键约束：映射不是一次性的静态分配。随着线路推进，逻辑比特之间的交互关系不断变化，初始映射可能很快“失效”，因此需要在执行过程中动态调整映射，这就是 SWAP 插入的由来。初始映射、SWAP 插入、约束满足三者共同构成了拓扑映射问题的完整闭环。
二、初始映射：决定起点质量
初始映射 π₀ 把逻辑比特分配到物理比特上。它不改变线路语义，但会显著影响后续需要插入多少 SWAP。一个直观的启发式是：统计逻辑线路中每个逻辑比特参与两比特门的次数（交互度），把交互度高的逻辑比特优先放到物理图中度较高、位置较中心的物理比特上；同时尽量让交互频繁的逻辑比特对在物理图上距离较近。
例如，假设逻辑线路中 q0 与 q1、q2、q3 都有 CNOT，交互度为 3；而 q4 只与 q5 交互，交互度为 1。在 4×4 网格上，可以把 q0 放到中心位置（如 (1,1) 或 (2,2)），把 q4 放到边缘。这样后续执行 CNOT(q0,q1) 时，两端更可能已经相邻，减少 SWAP。需要说明的是，初始映射本身也是一个组合优化问题：把 n 个逻辑比特分配到 N 个物理比特上，候选方案数为 N!/(N-n)!，当 n 较大时无法穷举，因此实际工具多采用贪心、模拟退火或子图同构近似。
三、SWAP 插入：动态调整映射
当某个两比特门的两端在物理图上不相邻时，必须通过插入 SWAP 门来“搬运”逻辑比特。SWAP 门交换两个相邻物理比特上的逻辑状态，因此它既改变了映射，也消耗了额外的门和深度。SWAP 插入的核心是：在物理图上找到一条从一端到另一端的路径，沿路径逐步交换，直到两端相邻。
以 4×4 网格为例，假设当前 q0 在物理比特 P5，q3 在 P10，二者不相邻。若 P5 与 P6 相邻、P6 与 P10 相邻，则可以插入 SWAP(P5,P6)，再插入 SWAP(P6,P10)，使 q0 到达 P10 附近，从而让 CNOT(q0,q3) 可执行。这里有一个重要细节：SWAP 会同时改变路径上其他逻辑比特的位置，可能影响后续门，因此选择哪条路径、在什么时机插入，需要结合后续门的分布做前瞻判断。常见策略包括最短路径优先、考虑后续门权重的启发式，以及基于 A* 或强化学习的搜索方法。
四、约束满足与 NP 难特性
拓扑映射必须同时满足多类约束：连边约束——两比特门只能作用在物理图的边上；唯一性约束——每个物理比特最多承载一个逻辑比特；顺序约束——SWAP 不能改变原线路中门的因果顺序；资源约束——SWAP 数量、线路深度、保真度损失都在可接受范围内。这些约束相互耦合，使得问题难以分解。
从复杂度角度看，拓扑映射的判定版本可以归约为图嵌入或子图同构问题，而子图同构是 NP 完全问题；即使只考虑 SWAP 插入，在给定初始映射下最小化 SWAP 数，也等价于在动态图上做多阶段最短路径规划，具有 NP 难特性。这意味着不存在已知的多项式时间精确算法能对所有输入都给出最优解。实际编译器中普遍采用启发式或近似算法，在可接受时间内给出“足够好”的解，并用评价指标衡量质量。
五、评价指标：如何判断映射好坏
评价一个拓扑映射方案，通常关注以下指标：
- SWAP 数量：新增 SWAP 门的总数，直接决定额外开销。
- 线路深度：插入 SWAP 后线路的关键路径长度，影响执行时间与退相干。
- 门保真度损失：每个 SWAP 由三个 CNOT 实现，会引入额外错误，需估算总保真度。
- 映射成功率：在给定约束下能否完成全部门的映射，是否存在无法满足的连边。
- 编译时间：算法运行时间，对大规模线路尤其重要。
这些指标之间存在权衡。例如，追求最少 SWAP 可能导致线路深度增加；追求低深度可能插入更多并行 SWAP。实际评估时，通常先保证约束满足和成功率，再在 SWAP 数与深度之间取折中。一个可参考的示例判断标准是：若某方案 SWAP 数比基线少 20% 以上，且深度增加不超过 10%，则可认为该方案在综合代价上更优。
综上，拓扑映射问题可以概括为：在物理耦合图约束下，为逻辑线路寻找初始映射并动态插入 SWAP，使所有两比特门合法执行，同时优化 SWAP 数、深度和保真度等指标。由于问题具有 NP 难特性，实际求解依赖启发式与近似算法，而评价指标则帮助我们在多个可行方案中做出选择。