精读笔记
Problem Setting
这篇论文处理的是 NCPO/NPA 层级在部分交换结构下的代数表示问题。标准 NPA 把变量看作自由非交换词，再把交换关系作为 moment 线性约束加入 SDP；这在概念上直接，但会把大量本应相同的 monomial 当成不同索引，造成变量和矩阵维度膨胀。
真正困难是 quotient algebra 的可计算表示。等式约束生成的是双边 *-ideal，正确压缩必须识别 modulo ideal 的等价类，而不是简单把每个等式写成一个替换规则。naive substitution 可能不合流，也可能漏掉由多个关系组合推出的等价，因此可能得到更松、更大的 relaxation。
论文聚焦的关键矛盾是：一般 equality quotient 很难，Groebner basis 可能巨大、无限甚至不可终止；但量子信息中大量结构恰好是 partial commutation，这个子类有 trace monoid 结构，可以被有效表示。
Motivation
已有路线不够的地方不在于不知道交换关系可以减少 SDP，而在于缺少一个严格且可实现的 quotient 层。很多 NPA 实现事实上已经在做 basis reduction，但它们通常依赖手写 substitution 或局部 canonicalization；这些规则在 CHSH 这种简单场景可行，在稍复杂的交换图或一般等式下就不保证正确。
作者的核心观察是：partial commutation 不是普通等式约束的一个随机子集，而是一个独立代数对象。它对应 partially commutative monoid / trace monoid，已有 normal form、projection、heap、Foata form、occurrence graph 等表示。也就是说，这里缺的不是新的 SDP 理论，而是把正确的 monoid representation 接到 moment hierarchy 上。
因此论文的动机是把“交换关系作为约束”改成“交换关系作为 monomial space 的定义”。这比在 SDP 后端加线性约束更接近问题本身，也避免了用不完备重写系统模拟 quotient algebra。
Core Idea
核心思想是：不要在 free algebra 里建大 moment matrix 再用线性约束压缩，而是直接在 quotient algebra P/<R_G> 里建 moment matrix。对于 partial commutation，quotient algebra 等价于 trace monoid algebra K[W_G]；moment 变量、矩阵行列、localizing matrix 都按 pc-monomials 索引。
这改变了建模方式。prior 的自由词表示默认所有变量彼此非交换，然后把部分交换作为额外约束修正；本文的 PCPO 表示默认变量之间的交换图已经内生在 monoid 乘法中。新的 inductive bias 是 locality / independence graph：可交换的操作天然共享同一个等价类，不再通过 SDP 求解器“学会”这些线性依赖。
本质区别在于信息流位置提前了：交换关系从数值优化层移到符号索引层。这样不仅减少变量，也可能让有限截断 relaxation 更强，因为完整 ideal 的某些后果不一定能被截断的 L(urv)=0 约束捕获。
Method
1. Quotient reduction：解决的是等式约束导致的冗余和不完备压缩问题。作者把 equality constraints 生成的双边 *-ideal I_R 显式引入，证明无限维 linear functional relaxation 可等价地写在 P/I_R 上。核心变化是 equality constraints 不再作为显式线性约束出现，而是被吸收到 basis 和乘法中。
2. 有限截断下的 quotient SDP：解决的是实际 SDP 构造问题。给定自由词截断 B，转为 quotient space [P_{B*B}] 的 basis，moment/localizing matrix 按 quotient basis 建。核心变化是矩阵被压缩为独立等价类上的矩阵；原始矩阵可由压缩矩阵经 Z^* M Z factorization 恢复，说明压缩不是 heuristic row dropping。
3. Partial commutation monoid：解决的是一般 quotient 难以表示的问题。对关系 x_i x_j = x_j x_i，作者下降到 monoid 层 W_G，而不是在 polynomial ideal 上跑一般 Groebner basis。核心变化是 quotient basis 变成 pc-monomials，等价测试变成 trace monoid word equivalence。
4. Circuit / wire representation：解决的是 pc-monomials 的工程可操作性。circuit 表示强调局部算子和并行层，wire representation 用 clique projections 把一个 pc-word 表成多条 wire words。核心变化是 multiplication 变成 wire-wise concatenation，involution 变成 wire-wise reverse/adjoint，equality testing 变成 tuple equality，避免反复 normal-form rewriting。
5. Tracial PCPO：解决 trace objective 下的 cyclicity。作者把 partial commutation quotient 和 cyclic equivalence 结合，但明确指出 cyclic quotient 只是 vector-space quotient，不是 monoid quotient；moment matrix 行列仍应按 ordinary pc-monomials 索引，只是在 entry lookup 时投影到 cyclic class。这是一个重要技术边界。
Key Insight / Why It Works
最核心的 insight 是：partial commutation 的正确抽象不是“一堆交换线性约束”，而是 trace monoid。只要把 monomial space 换成 W_G，所有由相邻可交换 swap 生成的等价都会自动合并，并且不会产生错误的额外线性关系。这是方法真正有效的原因。
最可能的核心贡献不是 PCPO 这个名字，而是把 quotient-based NPA 的 folklore 做成可验证的代数管线：先说明 naive substitution 为什么会错，再说明 quotient algebra 为什么对，再给 partial commutation 一个无需一般 Groebner basis 的 concrete representation。这对实现者很重要，因为很多数值包的“替换规则压缩”实际只在幸运场景下正确。
有限截断处有一个微妙但重要的点：quotient relaxation 不只是更小，也可能更紧。原因是 naive truncated formulation 只加入 supp(urv) 落在截断空间里的关系，而 quotient formulation 使用完整 ideal 后再截断。换言之，它可能识别一些需要经过高阶中间项才能推出、但最终落回低阶空间的等价。这不是单纯 engineering。
wire representation 的贡献更偏 representation engineering，但不是无意义工程。它把 pc-monomial 的 canonical key 做成 clique projections，使乘法和 involution 直接闭合，这会显著降低构造 SDP 时的符号处理成本。增益很可能主要来自 scaling：更少 moment variables、更小 PSD block、更少 explicit linear constraints，以及更便宜的 indexing。
这篇论文没有引入新的优化 relaxations strength 原理，仍然是 moment/SOS/NPA 体系；它的增益主要来自 better inductive bias 和 latent algebraic structure alignment，而不是新的 convex relaxation。若真实 benchmark 显著提升，归因大概率是 quotient indexing 降低规模和改善数值条件，而不是 SDP 层级本身变了。
Relation To Prior Work
最近的是 NPA / NCPO moment hierarchy、Lasserre-Parrilo commutative hierarchy、以及已有实现里的 equality substitution。本文不是替代这些层级，而是在它们的 monomial algebra 层做结构化 quotient。
和标准 NPA 的本质差异：标准 NPA 从 free monoid 出发，partial commutation 通过线性约束施加；本文从 trace monoid 出发，partial commutation 成为 monoid 定义。两者在无限维理想化情形等价，但有限截断和实现复杂度上不同。
和 commutative polynomial optimization 的关系也很清楚：CPO 是 commutation graph complete 的特殊情形，monoid 退化为 N^n，多项式 monomial 变成 exponent vector。本文把这个谱系补全：free monoid -> trace monoid -> commutative monoid。
看似新的 circuit representation，本质上重组了 Foata normal form、heaps、occurrence/dependency graph、clique projections 等 trace monoid 文献中的老工具；实质创新在于把这些工具翻译成 quantum information / SDP hierarchy 的可用接口。理论新意不是 trace monoid 本身，而是它和 quotient-based NPA construction 的系统连接。
Dataset / Evaluation
本文基本不是实验论文。CHSH 示例用于说明压缩效果：自由词 degree-2 relaxation 和 quotient 后的变量/矩阵规模差异很大，高阶增长从指数式自由词数量降到更低复杂度。这个例子能支持“partial commutation native indexing 会显著减少规模”的 claim，但不能充分支持普遍 runtime / numerical stability claim。
论文提到 PCPOP.jl 及另文 benchmark，但本文自身没有系统比较不同 commutation graphs、clique covers、relaxation orders、tracial cyclic merging 成本，也没有真实量子信息任务上的全面评估。因此 evidence 更像 algebraic correctness + illustrative scaling，而不是 empirical validation。
benchmark 是否验证核心 claim：验证了方向上的合理性，但不完整。核心 claim 如果是“构造正确且更 compact 的 SDP”，理论论证足够；如果 claim 是“更高效、更稳定、更适合实际大规模量子问题”，文中未充分说明，增益来源也未被系统拆解。
Limitation
第一，方法把一般 equality quotient 的难题转移到了结构化子类。partial commutation 可以漂亮解决，但对 projectors、unitaries、POVM completeness、idempotents、orthogonality 等量子信息常见约束，本文主要给 hybrid approach：部分 quotient，剩下仍作为线性约束。这并没有消除一般 Groebner/word problem 的困难。
第二，scalability 仍受 pc-monomial 数量控制。trace monoid 比 free monoid 小，但对稀疏交换图或复杂 non-commutation graph，basis 仍可能快速增长。wire representation 降低的是索引和等价测试成本，不改变 SDP PSD block 的根本增长规律。
第三，clique cover 选择可能是隐藏的关键工程变量。wire representation 依赖 non-commutation graph 的 edge clique cover；不同 cover 会改变 wire 数、tuple 长度、projection 成本和 storage layout。文中说明了 maximal clique cover 和 involution closure，但没有充分分析 cover choice 对实际性能的影响。
第四，tracial cyclic quotient 不是 monoid quotient，这使 TPCPO 实现更微妙。moment entry 需要先在 W_G 中乘法，再投影到 cyclic class；cyclic equivalence 的合并成本可能在高阶时明显上升。文中给出理论和已有算法线索，但实际瓶颈未充分说明。
第五，增益归因存在不清晰处。压缩来自 algebraic quotient 是确定的，但 runtime improvement、numerical stability、可扩展到更高 hierarchy level 的程度，需要和 solver bottleneck、PSD block structure、sparsity/symmetry 方法区分开。否则很容易把所有收益都归因于 PCPO 表示。
Takeaway
- 1. 对 NPA/NCPO 实现来说，最值得迁移的原则是：能在 monoid/algebra 层 quotient 的关系，不要留给 SDP 线性约束层处理。
- 2. partial commutation 应被视为一等结构，而不是 equality constraints 的特例。
- 它的正确数据结构是 trace monoid representation，尤其是 wire/clique projection，而不是 ad hoc word rewriting。
- 3. 有限截断 relaxation 的“正确压缩”不等于替换规则。
一句话总结
这篇论文把 NPA/NCPO 中的部分交换关系从后验 SDP 线性约束提升为 trace-monoid quotient 的原生索引结构，是一次以代数表示重构 scaling bottleneck 的方法演化，而不是新的 SDP relaxation 原理。