A quantum algorithm beats classical methods for car painting puzzle

Researchers from the National University of Singapore, A*STAR, and the Australian National University have demonstrated a quantum algorithm that surpasses classical methods in solving a complex car painting puzzle. The team tackled the Binary Paint Shop Problem, an optimisation challenge mirroring the logistical constraints of painting a sequence of 2^n cars with two colours while minimising disruptive paint booth switchovers.

Across instances ranging from 2^7 to 2^(12) cars, their XQAOA 1 algorithm achieved an average paint-swap ratio of 0.357, consistently outperforming four classical heuristics, including the recently proposed Recursive Star Greedy. This work marks the first report of size-dependent performance degradation of Recursive QAOA 1 at scale, while XQAOA 1 remains stable.

Binary Paint Shop Problem Formulation as Weighted MaxCut

The reduction of the Binary Paint Shop Problem (BPSP) to the weighted MaxCut problem allows for an exact Ising formulation, a key step in translating the logistical challenge into a form suitable for quantum optimisation algorithms. This transformation, detailed in algorithm 2, achieves the reduction in polynomial time and halves the number of decision variables needed to represent the problem. The resulting Ising Hamiltonian’s ground state directly corresponds to the optimal colouring scheme for the paint shop, providing a clear link between quantum solutions and practical efficiency.

Researchers formally proved this equivalence, enabling a direct mapping of the BPSP’s constraints into the language of quantum mechanics. The process uses spin variables, representing the colour assigned to each car, and defines an energy landscape where the lowest energy state corresponds to the best painting sequence. This formulation explicitly reveals structural features of the BPSP, offering insights beyond simply finding a solution.

Initial Car Colour Encoding and Graph Properties

The efficiency of solving the Binary Paint Shop Problem improved with a new encoding method that reduces the number of variables needed to define a solution by half. Researchers formally established this reduction, known as the Initial Car Colour (ICC) encoding, building on a technique previously introduced by Streif and colleagues to streamline the problem’s representation.

This approach focuses on recording only the colours assigned to the first occurrence of each car model, automatically determining the colour of its subsequent appearance, and significantly simplifying the computational task. The ICC encoding facilitates an exact reduction of the BPSP to a signed weighted MaxCut problem, a transformation that allows the problem’s constraints to be directly mapped into the language of quantum computing.

XQAOA1 Performance Across Problem Sizes

Recursive QAOA 1 exhibited a clear trend of performance decline as the problem size increased, a behaviour not observed in the XQAOA 1 algorithm. In contrast, XQAOA 1 maintained a consistently low paint-swap ratio of approximately 0.357 across all tested problem sizes, with its performance distributions becoming more concentrated as the number of cars grew.

Researchers formally established this connection through their reduction of the BPSP to MaxCut, raising the question of whether similar deterioration might occur in other MaxCut or Ising model applications. This suggests the issue is a potential limitation of the recursive approach within the broader context of quantum optimisation.

RQAOA1 Degradation at Larger Instances

Across instances simulating paint shop logistics, the Recursive QAOA 1 (RQAOA 1) algorithm exhibited declining performance as the number of cars increased, a trend not observed in its counterpart, eXpressive QAOA 1 (XQAOA 1). In contrast, XQAOA 1 remains stable across all tested sizes.

The team’s choice of metric, the paint-swap ratio, helped detect this trend. Normalising the ratio to the number of cars allowed for consistent evaluation at large scales without requiring knowledge of the optimal solution, a feat that would be impossible with metrics like the MaxCut approximation ratio which demands the exact optimum. “The paint-swap ratio E[Δ_C/n] is scale-normalised and requires no oracle access to the optimum, enabling consistent evaluation at arbitrarily large n,” the study reports.

The researchers acknowledge that increasing the depth of QAOA could potentially improve performance by accessing a larger solution space, but this would move away from the shallow-circuit regime that motivates the RQAOA approach. Their results suggest that while recursive methods offer a promising avenue for quantum optimisation, careful consideration must be given to potential size-dependent limitations and the choice of appropriate evaluation metrics.

Classical Heuristics for the Binary Paint Shop Problem

Across instances ranging from $2^7$ to $2^{12}$ cars, XQAOA 1 achieves an average paint-swap ratio of 0.357; in instance-wise benchmarks, it outperforms RQAOA 1 on nearly every instance tested, and consistently bests all four classical baselines, including RSG, across all problem sizes. This consistent performance is significant because the paint-swap ratio directly impacts production efficiency and cost, making even small improvements valuable in a real-world setting.

XQAOA1 Outperforms Classical and Quantum Baselines

357, demonstrably surpassing four established classical heuristics and its quantum counterpart, Recursive QAOA 1 (RQAOA 1). This performance marks an advancement in applying quantum-inspired algorithms to practical optimisation challenges, specifically minimising colour changes during a car painting sequence. The simulations considered instances ranging from 2⁷ to 2¹² “cars”, each representing a distinct model appearing twice, requiring different colours for each instance. While RQAOA 1 initially showed competitive results on smaller instances, its performance degraded with increasing problem size, eventually falling behind both XQAOA 1 and the best-performing classical method, Recursive Star Greedy (RSG).

This degradation represents the first documented instance of performance decline for RQAOA 1 at scale, highlighting a potential limitation of recursive approaches to quantum optimisation. 357 average even as the number of cars increased.

The classical heuristics adhered to expected theoretical performance, with RSG achieving an average of 0.37, slightly above its conjectured value of 0.361. “In the instance-wise comparisons, XQAOA 1 outperforms RQAOA 1 on almost all instances and each of the four classical BPSP heuristics on every instance,” the researchers state, emphasising the algorithm’s robust and consistent performance. The tightly concentrated distribution of paint-swap ratios obtained from XQAOA 1’s multiple restarts further reinforces its stability and reliability in solving this complex optimisation problem.

Paint Swap Ratio as Automotive Production Metric

The efficiency of automotive paint processes saw a boost as an expressive quantum algorithm achieved a paint-swap ratio of approximately 0.357 across simulations of up to 4096 cars. The paint-swap ratio itself measures the average number of colour changes needed during production, directly impacting material usage and overall cost. Analysis of the quantum algorithm, dubbed XQAOA 1, revealed a stable performance profile across varying problem sizes, a characteristic not shared by its recursive counterpart, RQAOA 1.

RQAOA 1 deteriorates with problem size despite employing provably near-optimal QAOA 1 parameters at each recursive step, eventually falling behind Recursive Star Greedy at the largest sizes. While Red-First exhibited the poorest scaling, Recursive Star Greedy proved the most effective among the classical methods tested. However, XQAOA 1 consistently outperformed all classical algorithms, demonstrating its ability to identify more efficient painting sequences. The researchers highlight that even seemingly small improvements in the paint-swap ratio can translate into substantial cost savings when applied to large-scale automotive manufacturing.

NISQ Devices and Low-Depth QAOA Variants

Across problem instances simulating between 128 and 4096 cars, XQAOA 1 achieved an average paint-swap ratio of 0. This size-dependent degradation, a previously unreported phenomenon, saw RQAOA 1 eventually fall behind the Recursive Star Greedy heuristic at the largest problem sizes.

This encoding facilitates translation of the Binary Paint Shop Problem into an Ising spin model, suitable for implementation on a quantum computer using QAOA or its variants. All code and datasets used in the study are publicly available, allowing for independent verification and further exploration of these low-depth quantum algorithms.

More like this

Quantum Error CorrectionGrover’s search runs on three logical qubits with this new code

Quantum HardwareClassiq and QuEra Reduce CZ-Depth for Neutral-Atom Processors

Quantum AlgorithmsHybrid quantum-classical algorithm matches best code solvers

Quantum HardwareRigetti says scaling quantum means complex tasks, fast results