[Rule] PaintShop to QUBO

[GiggleLiu]

Source

PaintShop

Target

QUBO

Motivation

• The PaintShop-to-QUBO mapping is used extensively in quantum computing research (QAOA, D-Wave quantum annealing) and is a well-studied formulation in the quantum optimization literature
• Connects the orphan PaintShop problem to the QUBO hub (7 existing incoming reductions), integrating it into the main reduction graph
• Enables solving PaintShop instances via quantum annealing hardware and QUBO solvers

Reference

Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021). "Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm." Physical Review A, 104, 012403. https://arxiv.org/abs/2011.03403

Reduction Algorithm

Given a PaintShop instance with n cars, each appearing exactly twice in a sequence of length 2n:

1. Variables: Create n binary QUBO variables x₁, ..., xₙ (one per car). Variable xᵢ = 0 means "car i gets color A at its first occurrence and color B at its second"; xᵢ = 1 means the reverse.
2. Initialize an n × n upper-triangular matrix Q of zeros.
3. For each adjacent pair of positions (j, j+1) in the sequence, let a = car at position j and b = car at position j+1:
   • If a = b: skip (always a color change — constant term).
   • If a ≠ b, determine the parity of each position (first or second occurrence of its car):
     • Same parity (both first, or both second): color change when xₐ ≠ xᵦ. Add +1 to Q[a][a], +1 to Q[b][b], −2 to Q[a][b].
     • Different parity (one first, one second): color change when xₐ = xᵦ. Add −1 to Q[a][a], −1 to Q[b][b], +2 to Q[a][b].
4. Objective: Minimize xᵀQx. The QUBO minimum plus a constant offset (number of different-parity pairs) equals the minimum color switches.
5. Solution extraction: The QUBO solution (x₁, ..., xₙ) maps directly back — car i's first occurrence gets color xᵢ, second gets 1−xᵢ.

Size Overhead

Target metric	Formula
num_vars	num_cars

Validation Method

Closed-loop test: construct a PaintShop instance, reduce to QUBO, solve QUBO with brute force, extract solution back to PaintShop, and verify optimality matches direct brute-force solve.

Example

Source (PaintShop): Sequence [A, B, C, A, D, B, D, C], with 4 cars.

Position	0	1	2	3	4	5	6	7
Car	A	B	C	A	D	B	D	C
Parity	1st	1st	1st	2nd	1st	2nd	2nd	2nd

Target (QUBO): 4 variables x_A, x_B, x_C, x_D. Matrix:

        A    B    C    D
Q = [ -1,  -2,   2,   2 ]
    [  0,   2,  -2,   0 ]
    [  0,   0,   1,  -2 ]
    [  0,   0,   0,   0 ]

Constant offset: +3 (from 3 different-parity adjacent pairs).

Optimal QUBO solution: x = (1, 0, 0, 0), giving xᵀQx = −1, total switches = −1 + 3 = 2.

Extracted PaintShop solution: Config (1,0,0,0) → coloring [1, 0, 0, 0, 0, 1, 1, 1] → 2 color switches at positions 0→1 and 4→5.

This example is non-trivial: a greedy approach yields 3+ switches, while the optimal achieves 2. The 4×4 QUBO matrix has both positive and negative entries, exercising all coupling types.

BibTeX

@article{Streif2021,
  title={Beating classical heuristics for the binary paint shop problem
         with the quantum approximate optimization algorithm},
  author={Streif, Michael and Yarkoni, Sheir and Skolik, Andrea
          and Neukart, Florian and Leib, Martin},
  journal={Physical Review A},
  volume={104},
  pages={012403},
  year={2021},
  doi={10.1103/PhysRevA.104.012403}
}