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.
Recent results on the Quantum Approximate Optimization Algorithm (QAOA) have cast pessimism on its potential to exhibit practical quantum speedups. For instance, QAOA’s locality limits its performance on tasks such as coloring bipartite graphs—which is easy for classical methods. Motivated by these limitations, the Recursive QAOA was introduced to overcome the locality and symmetry of QAOA. Despite being more powerful than QAOA, RQAOA is fully classically simulable at level-1 depth (p = 1). We report results on RQAOA in this classically simulable regime, benchmarked on random Quantum Unconstrainted Binary Optimization (QUBO) problems with up to 100 variables. We find that RQAOA generally matches the performance of classical simulated annealing and significantly outperforms ordinary QAOA.
Abstract Quantum approximate optimization algorithm (QAOA) is a quantum–classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the noisy intermediate-scale quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of the standard level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the standard level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights.
We present a generalization of the binary paint shop problem (BPSP) to tackle an automotive industry application, the multi-car paint shop (MCPS) problem. The objective of the optimization is to minimize the number of color switches between cars in a paint shop queue during manufacturing, a known NP-hard problem. We distinguish between different sub-classes of paint shop problems, and show how to formulate the basic MCPS problem as an Ising model. The problem instances used in this study are generated using real-world data from a factory in Wolfsburg, Germany. We compare the performance of the D-Wave 2000Q and Advantage quantum processors to other classical solvers and a hybrid quantum-classical algorithm offered by D-Wave Systems. We observe that the quantum processors are well-suited for smaller problems, and the hybrid algorithm for intermediate sizes. However, we find that the performance of these algorithms quickly approaches that of a simple greedy algorithm in the large size limit.