Classical and Quantum Heuristics for the Binary Paint Shop Problem
The Binary Paint Shop Problem (BPSP) involves coloring cars to minimize color swaps between identical models. This study benchmarks two quantum algorithms, XQAOA1 and RQAOA1, against classical heuristics like Recursive Star Greedy. XQAOA1 achieved a stable average swap ratio of 0.357 across all problem sizes, outperforming its competitors and showing no performance degradation with scale.