The Binary Paint Shop Problem (BPSP) is an
APX-hard optimisation problem arising 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. Performance is measured by the paint swap ratio -- the average number of colour changes per car -- which directly affects production efficiency and cost. Prior work showed that the Quantum Approximate Optimisation Algorithm (QAOA) at depth
p=7 achieves a ratio of
0.393, outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of
0.4 [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of
0.361. Here, we formally reduce BPSP to weighted MaxCut, yielding an exact Ising formulation, and benchmark two state-of-the-art low-depth QAOA variants -- eXpressive QAOA and Recursive QAOA -- at
p=1 (denoted XQAOA
1 and RQAOA
1) against four classical BPSP heuristics. Across instances ranging from
27 to
212 cars, XQAOA
1 achieves an average paint-swap ratio of
0.357; in our instance-wise benchmarks, it outperforms RQAOA
1 on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA
1 deteriorates with problem size despite employing provably near-optimal QAOA
1 parameters at each recursive step, eventually falling behind RSG at the largest sizes. To our knowledge, this is the first report of size-dependent performance degradation of RQAOA
1 at scale. In contrast, XQAOA
1 remains stable across all tested sizes, with no evidence of size-dependent degradation.
The binary paint shop problem (BPSP) is an APX-hard optimization problem in which, given
n car models that occur twice in a sequence of length
2n, the objective is to find a colouring sequence such that each car model pair is painted differently while minimizing the number of times the paint is swapped along the sequence. A recent classical heuristic, known as the recursive star greedy (RSG) algorithm, is conjectured to achieve an expected paint swap ratio of
0.361, thereby outperforming the Quantum Approximate Optimization Algorithm (QAOA) with circuit depth
p=7. Since the performance of the QAOA with logarithmic circuit depth is instance independent, the average paint swap-ratio is upper-bounded by the QAOA. We provide an improved upper-bound of the BPSP by extending the QAOA to depth
p=17, outputting an expected paint swap ratio of
0.334 via an exact computation while numerical extrapolation suggests a further reduction to a value of
0.295. To provide hardware-relevant comparisons, we additionally implement the BPSP on a D-Wave Quantum Annealer Advantage 2, obtaining a minimum paint swap ratio of
0.329. Given that the QAOA with logarithmic circuit depth does not exhibit a quantum advantage for sparse optimization problems such as the BPSP, this implies the existence of a classical algorithm that outperforms both the RSG algorithm and logarithmic depth QAOA. We provide numerical evidence that the Mean-Field Approximate Optimization Algorithm (MF-AOA) is one such algorithm, yielding a paint swap ratio of approximately
0.280 beating all known classical and quantum algorithms for the BPSP.
The binary paint shop problem (BPSP) is an APX-hard optimization problem of the automotive industry. In this work, we show how to use the quantum approximate optimization algorithm (QAOA) to find solutions of the BPSP. We demonstrate that QAOA with constant depth is able to beat all known heuristics for the binary paint shop problem on average in the infinite size limit $n\ensuremath{\rightarrow}\ensuremath{\infty}$. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through Amazon Braket.
As customer demands become increasingly diverse, the colors and styles of vehicles offered by automotive companies have also grown substantially. It poses great challenges to design and management of automotive manufacturing system, among which is the proper sequencing of vehicles in everyday operation of the paint shop. With typically hundreds of vehicles in one shift, the paint shop sequencing problem is intractable in classical computing. In this paper, we propose to solve a general paint shop sequencing problem using state-of-the-art quantum computing algorithms. Most existing works are solely focused on reducing color changeover costs, i.e., costs incurred by different colors between consecutive vehicles. This work reveals that different sequencing of vehicles also significantly affects the quality performance of the painting process. We use a machine learning model pretrained on historical data to predict the probability of painting defect. The problem is formulated as a combinational optimization problem with two cost components, i.e., color changeover cost and repair cost. The problem is further converted to a quantum optimization problem and solved with Quantum Approximation Optimization Algorithm (QAOA). As a matter of fact, current quantum computers are still limited in accuracy and scalability. However, with a simplified case study, we demonstrate how the classic sequencing problem in paint shop can be formulated and solved using quantum computing and demonstrate the potential of quantum computing in solving real problems in manufacturing systems.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for near-term quantum advantage, yet its practical impact is hindered by limited performance on symmetric local Hamiltonians and the costly optimization of variational parameters. The recursive-QAOA (RQAOA) introduced by Bravyi [] addresses the first limitation while also reducing circuit size, and parameter transfer techniques can be used to bypass the optimization loop effectively. In this work, we combine these two ideas to develop an optimization-free RQAOA and evaluate its performance on the binary paint shop problem (BPSP)—an optimization problem found in manufacturing where a sequence of cars must be painted under constraints while minimizing the number of color changes. The BPSP can be formulated as an Ising ground state problem with a symmetric local Hamiltonian in the form of MAX-CUT and properties well suited for the application of QAOA parameter transfer. We benchmark QAOA and RQAOA with parameter transfer against classical solvers and heuristics, and investigate their resilience to suboptimal parameters. For circuit optimization, we use reverse-causal cones and introduce a method of trimming outer two-qubit gates. To estimate the classical resources needed to simulate these quantum algorithms, we compute entanglement entropy and bond dimensions using matrix product state methods. We also compare circuit sizes and measurement counts across implementations. Our results show that RQAOA is inherently robust to parameter deviations, maintaining near-optimal solutions without noticeable degradation under parameter transfer while substantially reducing quantum resource requirements compared to QAOA. This highlights a viable route toward scalable quantum optimization without the overhead of the classical optimization loop and its challenges with barren plateaus.