衡量的是每辆车换色次数，而非解的质量
二元喷漆车间问题（BPSP）的输入是一个由 2n 辆车组成的序列，包含 n 种不同车型，每种车型恰好出现两次。一个合法着色要让每种车型的两次出现涂上不同颜色，代价是相邻两辆车颜色不同的对数。喷漆换色比把这个计数除以车辆数，因此它是每辆车平均换色次数：越低越好，0.357 意味着平均每辆车约换色 0.357 次。
这个比值经过规模归一化，且不需要知道最优解，因此作者能够一致地评估到 2^12 辆车。它与 MaxCut 近似比不是同一个量：后者需要精确最优解，在这些规模上不可行。论文把 BPSP 归约到加权 MaxCut，在形式上把两个问题联系起来，但这里报告的基准数字是喷漆换色比，应当按此理解。
比较基准也很重要。Recursive Greedy 有已证明的渐近期望比值 0.4，而 Recursive Star Greedy（RSG）的期望比值 0.361 只是猜想，尚未证明。此前工作报告深度 p=7 的 QAOA 达到 0.393，但这一深度远超当前含噪设备能维持的水平，这正是转而测试深度 1 变体的动机。
精确的 Ising 表述把决策变量减半
为了运行 QAOA 类算法，作者先把 BPSP 改写为加权 MaxCut 实例，再改写为 Ising 自旋模型。关键手段是初始车辆颜色（Initial Car Colour）编码，它基于 Streif 等人提出的技术并加以形式化：固定每种车型第一次出现的颜色，只把第二次出现当作决策变量。相比朴素编码，这使决策变量数量减半。
该归约还从 BPSP 约束中推导出精确的相互作用强度，并证明了所得图的结构性质，包括最大度数上界，以及图总权重与喷漆换色代价之间的显式关系。由于该编码是计算基赋值与合法 BPSP 着色之间的一一对应，Ising 模型的最优赋值对应最优着色。正因如此，量子启发式算法才能在不改变所求解问题的前提下适用。
XQAOA1 与 RQAOA1 使用浅层电路的方式不同
两个被测变体都停留在 p=1，即最浅的非平凡深度。eXpressive QAOA（XQAOA）修改了拟设，使单层具有更多自由度，论文使用的是 X=Y 混合器。Recursive QAOA（RQAOA）则反复求解一个小的 QAOA1 子问题，用得到自旋变量之间的关联来挑选一对变量，然后永久固定这对变量的关联或反关联，再对更小的实例递归。
递归正是关键差异。XQAOA1 每次优化运行产生一个赋值，而 RQAOA1 要依次承诺一系列不可逆的约束，每个消除步骤一个。作者指出，在 p=1 时关联估计只依赖有界的局部邻域，因此每个决策都是在关于剩余实例全局结构信息有限的情况下做出的。
论文还表明，0.357 并不是 XQAOA1 拟设固有的上限。把所有问题酉算符角度设为零，并为每个量子比特选择 π/4 或 3π/4 的混合器角度，拟设就能制备任意计算基态，因此全局最优参数原则上可以表示 BPSP 的精确最优解。所以观测到的数值描述的是从随机初始化出发的梯度优化通常能达到什么，而不是电路能表达什么。
XQAOA1 在深度 1 上逐实例胜过全部四个经典基线
在 2^7 至 2^12 辆车的实例上，XQAOA1 取得了 0.357 的平均喷漆换色比。在逐实例基准中，它在几乎所有实例上优于 RQAOA1，并在每个实例上优于四种经典 BPSP 启发式算法，包括 RSG。这比比较平均值更强：胜利是逐实例的，而不只是总体上的。
与 RSG 的比较需要谨慎。RSG 的 0.361 是猜想的期望比值，而 0.357 是这些基准中的实测平均值。论文的主张针对被测实例，并未证明 XQAOA1 的渐近期望比值优于 RSG。
XQAOA1 在测试范围内表现稳定。对每个 n，随机初始化下优化解分布的中心都保持在 0.357 附近，且随着 n 增大分布更集中，均值基本不变。作者报告在模拟规模内没有发现随规模退化的证据，不过仅凭数值结果并不能确立渐近极限常数。
RQAOA1 尽管子问题近优，仍随规模退化
出人意料的结果在递归一侧。RQAOA1 的表现随问题规模增大而变差，尽管每个递归步骤都使用了可证明近优的 QAOA1 参数。随着 n 增大，核密度估计单调向更高的喷漆换色比移动，RQAOA1 最终在最大规模上落后于 RSG。作者称这是首次报告 RQAOA1 在大规模下随规模出现性能退化。
这与先前的保证形成对比：RQAOA1 能精确求解无权环、完全图和加权二部图；先前在无外场 MaxCut 和 Ising 模型上的大规模模拟也显示，在数百个量子比特内行为稳定。相关工作曾报告有外场 Ising 模型上表现不稳定、依赖具体实例，但这里的模式是随规模变化的清晰趋势，而不是实例间的不稳定。
作者提出了一个机制，但明确表示并未因果性地分离它。按他们的解释，p=1 关联估计的局部性可能产生不完美的局部决策，而递归消除使这些决策持续存在，随着消除步骤增多，其影响不断累积。他们指出，需要匹配的非递归基线或更深的关联估计，才能区分退化有多少来自 p=1 时信息有限，有多少来自它通过递归的传播。模拟并未分别测量这两个因素。
规模归一化指标让规模效应显现
退化之所以能被发现，很大程度上归功于所选指标。喷漆换色比经过规模归一化，且不需要访问最优解，因此可以在任意大的 n 上一致评估。MaxCut 近似比则需要精确最优解，在这些规模上不可行，可能掩盖随规模变化的病态。
作者对结论的适用范围很谨慎。他们的形式化归约表明，退化发生在由 BPSP 产生的一族带符号加权 MaxCut/Ising 实例上。类似退化是否更普遍地出现在 MaxCut 或 Ising 模型中，在论文中仍是开放问题。
对 XQAOA1 的解释还有一层范围限制。作者提出，先前为 XQAOA 发现的更强表达能力和有利优化景观，或许能解释其稳定行为，但他们表示当前结果与这一图景一致，并未确立是同一机制。他们还指出，BPSP 图具有独特的带符号权重结构，而他们并未分析优化参数与这些边权重如何相关。
深度 1 上 XQAOA1 占优，但结论仍是经验性的
对于要在 BPSP 类实例上选择浅层启发式算法的读者，论文最具决策相关性的结果是两个量子变体在相同深度上的分化。XQAOA1 保持在 0.357 附近，在 2^7 至 2^12 辆车的每个测试实例上都优于全部四个经典基线；而 RQAOA1 的优势随规模增大而削弱，在最大规模上相对 RSG 消失。证据支持的实践优先级是在这一浅层区间选择 XQAOA1 而非 RQAOA1，而不是笼统断言量子启发式优于经典启发式。
这一优先级受两个条件约束。XQAOA1 的结果是测试实例和随机初始化上的经验平均值，不是已证明的渐近比值；与 RSG 的 0.361 比较，是用实测平均值对比猜想的期望值。RQAOA1 的退化是在 BPSP 导出的带符号加权实例上展示的，所提出的局部性与递归机制仍只是未被分离的解释。在这些边界内，论文的独特贡献是 RQAOA1 随规模出现的失效模式，以及 XQAOA1 在相同深度上的稳定性，这才是读者应当带走的比较。
本文引用的文献
Classical and Quantum Heuristics for the Binary Paint Shop Problem
在 p=1 时，XQAOA1 的平均喷漆换色比为 0.357，在 2^7 至 2^12 辆车的每个测试实例上都优于四种经典 BPSP 启发式算法（包括 RSG）；而 RQAOA1 随规模退化，在最大规模上落后于 RSG。