MF-AOA asymptotic performance conjecture for the binary paint shop problem
Let denote the size of a binary paint shop problem (BPSP) instance, let denote the performance function for the MF-AOA at the relevant variational parameters, and let AMP denote approximate message-passing algorithms. The normalized paint swap ratio is written as .
MF-AOA asymptotic performance conjecture. In the limit , AMP algorithms such as the MF-AOA achieve a performance of approximately
This conjecture extrapolates the observed QAOA and MF-AOA performance to the large-instance limit. The authors caution that the fitted value may be an overestimate; numerical simulations report an expected normalized paint swap ratio of approximately for , while a rigorous asymptotic analysis remains to be established.
References
- Mark Goh, Lara Caroline Pereira dos Santos and Matthias Sperl, “No quantum advantage implies improved bounds and classical algorithms for the binary paint shop problem”, arXiv:2604.00607 (2026).
Progress summary
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.