The metric is swaps per car, not solution quality
The Binary Paint Shop Problem starts with a sequence of 2n cars made of n distinct models, each appearing exactly twice. A valid colouring paints the two occurrences of every model in different colours, and the cost is the number of adjacent pairs that differ in colour. The paint-swap ratio divides that count by the number of cars, so it is an average number of colour changes per car: lower is better, and a ratio of 0.357 means roughly 0.357 swaps per car on average.
This ratio is scale-normalised and needs no access to the optimal solution, which is why the authors could evaluate it consistently up to 2^12 cars. It is not the same quantity as a MaxCut approximation ratio, which requires the exact optimum and becomes infeasible at these sizes. The paper's reduction to weighted MaxCut links the two problems formally, but the benchmark numbers reported here are paint-swap ratios, and they should be read as such.
The comparison baseline matters too. Recursive Greedy has a proven asymptotic expected ratio of 0.4, while Recursive Star Greedy (RSG) carries a conjectured expected ratio of 0.361 rather than a proven one. Earlier work reported QAOA at depth p=7 reaching 0.393, but that depth is far beyond what current noisy devices can sustain, which is the motivation for testing depth-1 variants instead.
An exact Ising formulation halves the decision variables
To run QAOA-style algorithms, the authors first rewrite BPSP as a weighted MaxCut instance and then as an Ising spin model. The key device is the Initial Car Colour encoding, formalised from a technique introduced by Streif et al., which fixes the colour of each model's first occurrence and treats only the second occurrence as a decision variable. That halves the number of decision variables relative to a naive encoding.
The reduction also derives exact interaction strengths from the BPSP constraints and proves structural properties of the resulting graphs, including a maximum degree bound and an explicit relation between total graph weight and paint swap cost. Because the encoding is a bijection between computational-basis assignments and valid BPSP colourings, an optimal assignment of the Ising model corresponds to an optimal colouring. This is what makes the quantum heuristics applicable without changing the problem being solved.
XQAOA1 and RQAOA1 differ in how they use shallow circuits
Both tested variants stay at p=1, the shallowest nontrivial depth. eXpressive QAOA (XQAOA) modifies the ansatz so that a single layer has more freedom, and the paper uses an X=Y mixer. Recursive QAOA (RQAOA) instead repeatedly solves a small QAOA1 subproblem, uses the resulting correlations between spin variables to pick a pair, and then permanently fixes that pair's correlation or anti-correlation before recursing on a smaller instance.
That recursion is the crucial difference. XQAOA1 produces one assignment per optimisation run, whereas RQAOA1 commits to a sequence of irreversible constraints, one per elimination step. The authors note that at p=1 the correlation estimates depend only on a bounded local neighbourhood, so each decision is made with limited information about the global structure of the remaining instance.
The paper also shows that 0.357 is not a ceiling built into the XQAOA1 ansatz. Setting all problem-unitary angles to zero and choosing per-qubit mixer angles of π/4 or 3π/4 lets the ansatz prepare any computational-basis state, so in principle the globally optimal parameters can represent an exact optimal BPSP solution. The observed value therefore describes what gradient-based optimisation from random initialisations typically reaches, not what the circuit can express.
XQAOA1 beat all four classical baselines instance by instance
Across instances ranging from 2^7 to 2^12 cars, XQAOA1 achieved an average paint-swap ratio of 0.357. In the instance-wise benchmarks it outperformed RQAOA1 on almost all instances and each of the four classical BPSP heuristics, including RSG, on every instance. This is a stronger statement than a comparison of averages: the win is per instance, not only in aggregate.
The comparison with RSG deserves care. RSG's 0.361 is a conjectured expected ratio, while the 0.357 figure is an empirical average from these benchmarks. The paper's claim is about the tested instances, not a proof that XQAOA1 has a better asymptotic expected ratio than RSG.
XQAOA1's behaviour was also stable across the tested range. For each n, the distribution of optimised solutions over random initialisations stayed centred near 0.357, and the distributions became more concentrated as n grew while their means stayed essentially unchanged. The authors report no evidence of size-dependent degradation within the sizes simulated, though their numerics alone do not establish an asymptotic limiting constant.
RQAOA1 deteriorates with size despite near-optimal subproblems
The surprising result is on the recursive side. RQAOA1's performance worsened as problem size increased, even though each recursive step used provably near-optimal QAOA1 parameters. Kernel density estimates shifted monotonically toward higher paint-swap ratios as n grew, and RQAOA1 eventually fell behind RSG at the largest sizes. The authors describe this as the first report of size-dependent performance degradation of RQAOA1 at scale.
This contrasts with prior guarantees that RQAOA1 exactly solves unweighted cycles, complete graphs, and weighted bipartite graphs, and with earlier large-scale simulations on MaxCut and Ising models without external fields that showed stable behaviour up to hundreds of qubits. Related work had reported erratic, instance-dependent performance for Ising models with external fields, but the pattern here is a clear trend with size rather than instance-to-instance instability.
The authors offer a mechanism but explicitly do not claim to have isolated it causally. In their account, the locality of p=1 correlation estimates can produce imperfect local decisions, and the recursive elimination makes those decisions persistent so their effects compound as the number of elimination steps grows. They note that a matched non-recursive baseline or deeper correlation estimates would be needed to separate how much degradation comes from limited information at p=1 and how much from its propagation through recursion. The simulations do not separately measure these two ingredients.
A scale-normalised metric made the size effect visible
The degradation could be detected largely because of the chosen metric. The paint-swap ratio is scale-normalised and requires no oracle access to the optimum, so it can be evaluated consistently at arbitrarily large n. A MaxCut approximation ratio would have required the exact optimum, which is infeasible at these sizes and could have masked a size-dependent pathology.
The authors are careful about how far this transfers. Their formal reduction shows the degradation occurs on a family of signed weighted MaxCut/Ising instances arising from BPSP. Whether analogous deterioration occurs more generally for MaxCut or Ising models remains an open question in the paper.
A further scope limit applies to the XQAOA1 explanation. The authors suggest that the increased expressiveness and favourable optimisation landscapes previously identified for XQAOA may explain its stable behaviour, but they state that the present results are consistent with that picture without establishing the same mechanism. They also note that BPSP graphs have a distinctive signed weight structure and that they did not analyse how optimised parameters correlate with those edge weights.
Depth one favours XQAOA1, but the claim stays empirical
For a reader deciding which shallow heuristic to try on BPSP-like instances, the paper's most decision-relevant result is the split between the two quantum variants at the same depth. XQAOA1 held near 0.357 and beat all four classical baselines on every tested instance from 2^7 to 2^12 cars, while RQAOA1's advantage eroded with size and disappeared against RSG at the largest sizes. The practical priority the evidence supports is XQAOA1 over RQAOA1 in this shallow regime, not a general claim that quantum heuristics beat classical ones.
Two conditions bound that priority. The XQAOA1 result is an empirical average over the tested instances and random initialisations, not a proven asymptotic ratio, and the comparison against RSG's 0.361 pits a measured average against a conjectured expectation. The RQAOA1 degradation is demonstrated on BPSP-derived signed weighted instances, with the proposed locality-and-recursion mechanism left as an unisolated explanation. Within those bounds, the paper's distinctive contribution is the size-dependent failure mode of RQAOA1 and the stability of XQAOA1 at the same depth, which is the comparison a reader should carry away.
Sources used in this answer
Classical and Quantum Heuristics for the Binary Paint Shop Problem
At p=1, XQAOA1 averaged a paint-swap ratio of 0.357 and beat four classical BPSP heuristics, including RSG, on every tested instance from 2^7 to 2^12 cars, while RQAOA1 degraded with size and fell behind RSG at the largest sizes.