Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2509.15294 · Physical Review Applied

Classical and quantum heuristics for the binary paint-shop problem

V Vijendran, Dax Enshan Koh, Ping Koy Lam, Syed M. Assad

Published Oct 8, 2026• 0 citations
arXivHTMLPDF

Abstract

The Binary Paint Shop Problem (BPSP) is an $\mathsf{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 $2^7$ to $2^{12}$ 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.

DOI
10.1103/dw96-xxfy

Related papers

Beyond Quantum Advantage: Improved Classical Algorithms for the Binary Paint Shop Problem

Mark Goh, Lara Caroline Pereira dos Santos, Thorge Müller +1 more

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.

quant-pharXiv:2604.00607•Apr 2, 2026•0 citations

Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm

Michael Streif, Sheir Yarkoni, Andrea Skolik +2 more

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.

arXiv:2011.03403•Physical Review A•Jul 2, 2021•41 citations

Multi-car paint shop optimization with quantum annealing

Sheir Yarkoni, A. Alekseyenko, Michael Streif +3 more

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.

arXiv:2109.07876•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•42 citations

Paint shop vehicle sequencing based on quantum computing considering color changeover and painting quality

Jing Huang, Qing Chang, Hua-Tzu Fan

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.

arXiv:2206.11204•Advanced Manufacturing•Jan 1, 2024•3 citations

Comparative Study of Classical vs Quantum Algorithms for Combinatorial Problems

Daniel Popescu, Helena Petrov

Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.

Quantum Frontiers Journal•Mar 28, 2024•0 citations

Quantum approximate stochastic combinatorial optimisation

Edric Matwiejew, Paulo E. Santos, Jingbo B. Wang +1 more

Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be $\#\mathrm{P}$-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than $2^{32}$ configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.

quant-pharXiv:2610.22876•Oct 19, 2026•0 citations
The Binary Paint Shop Problem (BPSP) is an APX\mathsf{APX}APX-hard optimisation problem arising in automotive manufacturing: given a sequence of 2n2n2n cars, comprising nnn 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=7p=7p=7 achieves a ratio of 0.3930.3930.393, outperforming the then-best-known classical heuristic, Recursive Greedy, with a proven asymptotic expected ratio of 0.40.40.4 [Phys. Rev. A 104, 012403 (2021)]. More recently, the Recursive Star Greedy (RSG) heuristic was proposed with a conjectured expected ratio of 0.3610.3610.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=1p=1p=1 (denoted XQAOA1_11​ and RQAOA1_11​) against four classical BPSP heuristics. Across instances ranging from 272^727 to 2122^{12}212 cars, XQAOA1_11​ achieves an average paint-swap ratio of 0.3570.3570.357; in our instance-wise benchmarks, it outperforms RQAOA1_11​ on almost all instances and each of the four classical baselines, including RSG, on every instance. Surprisingly, RQAOA1_11​ deteriorates with problem size despite employing provably near-optimal QAOA1_11​ 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 RQAOA1_11​ at scale. In contrast, XQAOA1_11​ 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 nnn car models that occur twice in a sequence of length 2n2n2n, 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.3610.3610.361, thereby outperforming the Quantum Approximate Optimization Algorithm (QAOA) with circuit depth p=7p=7p=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=17p=17p=17, outputting an expected paint swap ratio of 0.3340.3340.334 via an exact computation while numerical extrapolation suggests a further reduction to a value of 0.2950.2950.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.3290.3290.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.2800.2800.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.
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.
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.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
Two-stage stochastic combinatorial optimisation concerns discrete decisions made before all relevant information is known. An initial decision is made; once uncertainty is resolved, it can be adapted to the realised scenario, at a cost. The aim is to find the initial decision that minimises the upfront cost plus the expected cost of optimal adaptation. The first-stage decision problem is often NP-hard, and computing the expected minimum recourse cost can be #P\#\mathrm{P}#P-hard for a single first-stage candidate. We introduce Quantum Approximate Stochastic Combinatorial Optimisation (QASCO), a variational quantum-walk ansatz that coherently incorporates scenario-dependent recourse into its dynamics to search over first-stage decisions without explicitly evaluating expected minimum recourse costs. We demonstrate QASCO for MaxCut with stochastic edge weights, obtain a circuit with polynomial per-layer gate complexity, and study the ansatz via exact state-vector simulation. Across the instances considered, QASCO concentrates amplitude more effectively on stochastic-optimal first-stage decisions than a previously proposed two-stage QAOA construction. We further show that the ansatz can be calibrated using a depth-independent number of parameters and applied to unseen instances without further circuit-parameter optimisation, including joint decision--scenario--recourse spaces spanning more than 2322^{32}232 configurations. Under a query-cost model, comparison with the tested classical heuristics using sample-average approximations of the expected minimum recourse cost shows that QASCO more reliably reaches globally optimal first-stage solutions while requiring fewer cut evaluations. These results show how to incorporate scenario-dependent recourse into the ansatz dynamics, providing a general framework for variational quantum walks in two-stage stochastic combinatorial optimisation.