A quantum algorithm beats classical methods for car painting puzzle

Researchers from the National University of Singapore, A*STAR, and the Australian National University have demonstrated a quantum algorithm that surpasses classical methods in solving a complex car painting puzzle. The team tackled the Binary Paint Shop Problem, an optimisation challenge mirroring the logistical constraints of painting a sequence of 2^n cars with two colours while minimising disruptive paint booth switchovers. Across instances ranging from 2^7 to 2^(12) cars, their XQAOA 1 algorithm achieved an average paint-swap ratio of 0.357, consistently outperforming four classical heuristics, including the recently proposed Recursive Star Greedy. This work marks the first report of size-dependent performance degradation of Recursive QAOA 1 at scale, while XQAOA 1 remains stable. The reduction of the Binary Paint Shop Problem (BPSP) to the weighted MaxCut problem allows…