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:2011.03403 · Physical Review A

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

Michael Streif, Sheir Yarkoni, Andrea Skolik, Florian Neukart, Martin Leib

Published Jul 2, 2021• 41 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.104.012403

Related papers

Classical and quantum heuristics for the binary paint-shop problem

V Vijendran, Dax Enshan Koh, Ping Koy Lam +1 more

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.

arXiv:2509.15294•Physical Review Applied•Oct 8, 2026•0 citations

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

Optimization-free recursive Quantum Approximate Optimization Algorithm for the binary paint shop problem

Gary J. Mooney, Jedwin Villanueva, Bhaskar Roy Bardhan +3 more

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.

arXiv:2507.10908•Physical Review Research•Feb 13, 2026•1 citation

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

Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

Anuj Apte, Sami Boulebnane, Yuwei Jin +3 more

Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.

quant-pharXiv:2602.05956•Feb 6, 2026•0 citations
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→\ensuremath∞n\ensuremath{\rightarrow}\ensuremath{\infty}n\ensuremath→\ensuremath∞. We complete our studies by running first experiments of small-sized instances on a trapped-ion quantum computer through Amazon Braket.
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 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.
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.
Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-ppp QAOA expectation on high-girth ddd-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth ppp but does not depend on the graph size. Evaluating this formula for Max-kkk-Cut problem for p≤4p\leq 4p≤4, we identify parameter regimes (k=3k=3k=3 with degree d≤10d \leq 10d≤10 and k=4k=4k=4 with d≤40d \leq 40d≤40) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth p≤20p\leq 20p≤20. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.