Classical and Quantum Heuristics for the Binary Paint Shop Problem
The Binary Paint Shop Problem (BPSP) is an -hard optimisation problem in automotive manufacturing: given a sequence of cars, comprising 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 achieves a paint swap ratio of , outperforming the classical Recursive Greedy (RG) heuristic with an expected ratio of [Phys. Rev. A 104, 012403 (2021)]. More recently, the classical Recursive Star Greedy (RSG) heuristic was conjectured to achieve an expected ratio of . 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 (denoted XQAOA and RQAOA), against the strongest classical heuristics known to date. Across instances ranging from to cars, XQAOA achieves an average ratio of , 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 -car instances and all -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.