Quantum Heuristics Achieve 0.2 Paint Swap Ratio for Binary Paint Shop Problem, Outperforming Classical Methods

The Binary Paint Shop Problem, a challenging optimisation task central to automotive manufacturing, concerns the efficient colouring of cars to minimise disruptive paint swaps, and researchers are continually seeking improved solutions to this complex issue. V Vijendran, Dax Enshan Koh from A*STAR’s Quantum Innovation Centre, Ping Koy Lam from the National University of Singapore’s Centre for Quantum Technologies, and Syed M Assad, now present a comprehensive analysis of both classical and quantum approaches to this problem. Their work establishes a theoretical framework for applying quantum algorithms to the Binary Paint Shop Problem and benchmarks two advanced quantum algorithms, eXpressive (XQAOA) and Recursive (RQAOA), against leading classical heuristics. The team demonstrates that XQAOA consistently outperforms all known methods across a range of problem sizes, achieving an average ratio of, while RQAOA exhibits unexpected performance limitations at larger scales, representing a significant new insight into the behaviour of this quantum algorithm and highlighting the potential for quantum approaches to optimise complex industrial processes.

The goal is to determine the optimal colour order, minimising the number of colour changes required during painting to improve efficiency and reduce costs. Researchers have addressed this problem using a combination of theoretical analysis and advanced algorithmic development, seeking solutions that are both effective and computationally feasible. This work contributes to a deeper understanding of the problem’s complexity and provides new algorithms with improved performance compared to existing methods, offering significant benefits for automotive manufacturers.

BPSP Reduction to MaxCut via Ising Model

Scientists have demonstrated a connection between the BPSP and the MaxCut problem, a well-known challenge in graph theory. This connection was established through a mathematical reduction, transforming instances of the BPSP into equivalent instances of MaxCut. The team then expressed the problem using an Ising model, a framework from statistical physics, allowing them to apply tools and insights from this field to analyse and potentially solve the problem. This approach provides a new perspective on the BPSP and opens up possibilities for utilising techniques from physics to find effective solutions.

The research involved formalising the problem with specific notation, defining variables to represent the graph structure and the desired partition. A cost function was derived to capture the BPSP objective, demonstrating that minimising the BPSP cost is equivalent to maximising a related function in the MaxCut problem. The Ising model formulation expresses the number of colour swaps in terms of Ising variables and the graph’s structure. The team reduced the BPSP to a weighted MaxCut problem and then formulated it as an Ising spin model, enabling its application to quantum optimisation algorithms. They developed a technique, called Initial Car Colour (ICC) encoding, that halves the number of decision variables required, streamlining the computational process. Experiments revealed that the eXpressive Quantum Approximate Optimisation Algorithm (XQAOA) consistently outperformed all tested classical heuristics, achieving an average paint swap ratio of 0.

1. This result surpasses the previously conjectured performance of the Recursive Star Greedy (RSG) heuristic, which stands at 0. 361. Notably, the Recursive Quantum Approximate Optimisation Algorithm (RQAOA) exhibited diminishing performance as the problem size increased. Despite utilising optimally tuned parameters, RQAOA was outperformed by RSG on instances of 211 cars and larger, marking the first reported demonstration of RQAOA’s performance degradation at scale. In contrast, XQAOA maintained robust performance across all tested sizes, suggesting its potential to surpass all known heuristics as the problem scales further. By establishing a theoretical link between the problem and weighted MaxCut, the team benchmarked two quantum algorithms, eXpressive QAOA and Recursive QAOA, against established classical heuristics. Across problem instances ranging from small to moderately sized, eXpressive QAOA consistently outperformed all classical approaches, including the previously conjectured best classical solution. The robustness of eXpressive QAOA, in contrast, suggests its potential to surpass all known heuristics as problem sizes continue to grow. Future work could explore modifications to Recursive QAOA to address its scaling limitations, or investigate the application of these quantum algorithms to other optimisation problems in manufacturing and beyond.