技术摘要：用于量子同构与同态不可区分性的 NPA 层级结构

1. 问题陈述与动机

本文研究了图的量子同构（quantum isomorphism）的计算与结构特征。两个图 $G$ 和 $H$ 是量子同构的（记作 $G \cong_q H$），如果存在一个完美的量子策略来完成图同构博弈，该策略涉及共享纠缠和局部测量。

虽然经典图同构是可判定的（可在拟多项式时间内解决），但 Mančinska 和 Roberson [FOCS'20] 证明了判定量子同构在一般情况下是不可判定的。这促使人们研究量子同构的松弛形式，特别是 NPA 层级结构（以 Navascués, Pironio 和 Acín 命名），它提供了一系列半正定规划（SDP）松弛，用以近似量子相关性。

一个新兴的同态不可区分性理论中的核心问题是：这些 SDP 松弛的每一层级的可行性是否可以通过组合数学进行刻画？具体而言，作者探讨：第 $k$ 层 NPA 层级对于 $(G, H)$-同构博弈的可行性，是否等价于 $G$ 和 $H$ 在特定类图上的同态不可区分性？

2. 方法论与证明技术

本文综合运用了代数组合数学、算子理论和图论。其核心方法论依赖于双标签图（bilabelled graphs）与同态张量（homomorphism tensors）之间的对应关系。

关键工具

• 双标签图与同态张量： 一个 $(k, l)$-双标签图 $F = (F, u, v)$ 与一个张量 $F^G \in \mathbb{C}^{V(G)^k \times V(G)^l}$ 相关联，其中条目计数了将输入标签 $u$ 映射到 $x$ 且输出标签 $v$ 映射到 $y$ 的同态数量。双标签图的组合操作（串联组合、并联组合、标签的循环置换）对应于这些张量的代数操作（矩阵乘法、Schur 积、置换）。
• NPA 层级结构重构： 作者将存在第 $k$ 层 NPA 层级证书的存在性，重构为存在一个第 $k$ 层量子同构映射。这是一个在保持与同态张量相关的特定结构属性的矩阵代数之间的完全正映射。
• 代数 $k$-等价性： 他们引入了代数 $k$-等价性的概念，定义为由特定原子图的同态张量生成的子代数之间的代数同构，并满足迹保持（trace-preserving）和单位化（unital）条件。

证明结构

主定理的证明通过一系列等价关系展开：

1. NPA 可行性 $\iff$ 量子同构映射： NPA 证书的一个主子矩阵被解释为完全正映射的 Choi 矩阵。NPA 层级的约束被证明等价于第 $k$ 层量子同构映射的公理（定理 3.6）。
2. 量子同构映射 $\iff$ 代数 $k$-等价性： 量子同构映射被证明限制为特定原子图集合 $Q_k$ 生成的同态张量代数之间的同构（定理 3. 9）。
3. 代数 $k$-等价性 $\iff$ 同态不可区分性： 利用图操作与张量代数之间的对应关系，证明了这种代数同构的存在性等价于 $G$ 和 $H$ 对构造出的图类 $P_k$ 具有相等的同态计数（定理 4.4）。

3. 主要贡献与结果

主定理 (Theorem 1.1)

对于图 $G$、$H$ 和整数 $k \ge 1$，以下各项是等价的：

1. $(G, H)$-同构博弈的第 $k$ 层 NPA 层级是可行的。
2. 存在从 $G$ 到 $H$ 的第 $k$ 层量子同构映射。
3. $G$ 和 $H$ 是代数 $k$-等价的。
4. $G$ 和 $H$ 在图类 $P_k$ 上是同态不可区分的。

此处，$P_k$ 是一个平面双标签图类，通过使用串联组合、与特定原子图的并联组合以及循环标签置换，从原子图 $Q_k$ 归纳构造而成。

图类 $P_k$ 的性质

• 平面性： $P_k$ 中的每个图都是平面的（引理 4.7）。
• 有界树宽： $P_k$ 的底层图的树宽至多为 $3k-1$（引理 4.5）。
• 小类封闭性： 类 $P_k$ 对取 minor 操作是封闭的（引理 4.8）。
• 并集： 所有 $P_k$（对于 $k \in \mathbb{N}$）的底层无标签图的并集恰好是所有平面图的集合（推论 4.12）。

算法结果 (Theorem 1.2)

本文提出了一个随机多项式时间算法，用于判定固定 $k$ 时第 $k$ 层 NPA 层级的精确可行性。

• 运行时间： $n^{O(k)} k^{O(1)}$，其中 $n = \max\{|V(G)|, |V(H)|\}$。
• 方法： 该算法并非求解 SDP，而是检查在随机选择的素数 $p$ 下对 $P_k$ 的同态不可区分性。它计算在有限域上由 $P_k$ 中图的同态张量所张成的向量空间的基。
• 意义： 这避免了标准 SDP 求解器（如椭球法）固有的近似问题，并提供了针对固定层级的精确判定程序。

对 Mančinska 和 Roberson [FOCS'20] 的替代证明

通过结合主定理与 NPA 层级的收敛性，以及 $\bigcup_k P_k$ 是所有平面图这一事实，作者推导出了一个新的证明：$G \cong_q H$ 当且仅当 $G$ 和 $H$ 在所有平面图上是同态不可区分的。

• 区别： 与 [FOCS'20] 原本依赖于紧致量子群（compact quantum groups）和截断子（intertwiners）理论的证明不同，本证明是纯粹组合与代数的，利用了 NPA 层级结构和同态张量。

4. 重要性与主张

本文声称提供了一个针对 NPA 层级的同态不可区分性刻画，将量子同构松弛置于同态不可区分性关系的更广泛理论框架内。

• 理论统一： 它弥合了非交换 NPA 层级与经典 Lasserre 层级之间的鸿沟（后者此前由 Roberson 和 Seppelt [ICALP'23] 使用图类 $L_k$ 进行刻画）。
• 计算优势： 它确立了对于固定的 $k$，NPA 层级的精确可行性是可判定的，这一结果从 SDP 公式本身来看并非显而易见。
• 简化量子同构理论： 本文通过利用 NPA 约束的组合结构，提供了一个关于量子同构（通过平面图）基本特征的证明，从而避开了使用“重型工具”（heavy machinery）的量子群理论。

作者指出，虽然 $P_k$ 是具有有界树宽的平面图子类，但 $P_k$ 与用于经典同构松弛的图类 $L_k$ 之间的精确结构关系仍是一个开放问题（问题 6.1）。他们还提出了这样一个问题：是否存在一个图类，其量子同构由固定层级的 NPA 层级决定，但与经典同构不同（问题 6.2）。