Abstract
The Binary Paint Shop Problem (BPSP) is an APX-hard optimisation problem in automotive manufacturing: given a sequence of 2n cars, comprising n distinct models each appearing twice, the task is to decide which of two colours to paint each car so that the two occurrences of each model are painted differently, while minimising consecutive colour swaps. The key performance metric is the paint swap ratio, the average number of colour changes per car, which directly impacts production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth p=7 achieves a paint swap ratio of 0.393, outperforming the classical Recursive Greedy (RG) heuristic with an expected ratio of 0.4 [Phys. Rev. A 104, 012403 (2021)]. More recently, the classical Recursive Star Greedy (RSG) heuristic was conjectured to achieve an expected ratio of 0.361. In this study, we develop the theoretical foundations for applying QAOA to BPSP through a reduction of BPSP to weighted MaxCut, and use this framework to benchmark two state-of-the-art low-depth QAOA variants, eXpressive QAOA (XQAOA) and Recursive QAOA (RQAOA), at p=1 (denoted XQAOA₁ and RQAOA₁), against the strongest classical heuristics known to date. Across instances ranging from 2⁷ to 2¹² cars, XQAOA₁ achieves an average ratio of 0.357, surpassing RQAOA₁ and all classical heuristics, including the conjectured performance of RSG. Surprisingly, RQAOA₁ shows diminishing performance as size increases: despite using provably optimal QAOA₁ parameters at each recursion, it is outperformed by RSG on most 2¹¹-car instances and all 2¹²-car instances. To our knowledge, this is the first study to report RQAOA₁'s performance degradation at scale. In contrast, XQAOA₁ remains robust, indicating strong potential to asymptotically surpass all known heuristics.