XQAOA level-1 limiting performance conjecture for the Binary Paint Shop Problem

Consider Binary Paint Shop Problem instances encoded as Ising models, and let ΔC\Delta_C be the number of paint swaps. Let XQAOA1_1 denote the level-1 XQAOA ansatz, with its parameters optimised by gradient-based methods. XQAOA level-1 performance conjecture. The limiting expected paint-swap ratio is approximately 0.3570.357:

limnE[ΔCn]0.357.\lim_{n\rightarrow\infty}\mathbb{E}\left[\frac{\Delta_C}{n}\right]\approx 0.357.

This conjecture is motivated by numerical experiments showing that the XQAOA1_1 distributions remain stationary across the tested problem sizes, but no asymptotic proof is given.

Sources & referencesView supporting material

Primary source

V Vijendran, Dax Enshan Koh, Ping Koy Lam and Syed M Assad, “Classical and Quantum Heuristics for the Binary Paint Shop Problem”, arXiv:2509.15294 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.