Speaker
Description
The Binary Paint Shop Problem (BPSP) is an $\mathsf{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 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 QAOA at depth $p=7$ achieves a paint swap ratio of $0.393$, outperforming the Recursive Greedy (RG) heuristic with an expected ratio of $0.4$ . More recently, the 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 formal reduction of BPSP to weighted MaxCut, and use this framework to benchmark two SOTA low-depth QAOA variants---XQAOA and RQAOA---at depth $p=1$ against the strongest classical heuristics known to date. Across instances ranging from $2^7$ to $2^{12}$ cars, XQAOA$_1$ achieves an average ratio of $0.357$, surpassing RQAOA$_1$ and all known classical heuristics, including the conjectured performance of RSG. Surprisingly, RQAOA$_1$ shows diminishing performance: despite employing provably optimal QAOA$_1$ parameters at each recursive step, it is outperformed by RSG on most $2^{11}$-car instances and on all $2^{12}$-car instances. To our knowledge, this is the first study to report RQAOA$_1$’s performance degradation at scale. In contrast, XQAOA$_1$ stays robust across all sizes.
| Topic | Hybrid quantum-classical approaches for learning and optimization |
|---|