Binary Paintshop Problem with Quantum Approximate Optimisation Algorithm

View on QuantumAI Run in Google Colab View source on GitHub Download notebook
import numpy as np
try:
    import cirq
except ImportError:
    print("installing cirq...")
    !pip install --quiet cirq
    print("installed cirq.")

Binary Paintshop Problem

Assume an automotive paint shop and a random, but fixed sequence of 2*n cars. Each car has a identical partner that only differs in the color it has to be painted.

import cirq
import cirq.ionq as ionq

CAR_PAIR_COUNT = 10
CAR_SEQUENCE = np.random.permutation([x for x in range(CAR_PAIR_COUNT)] * 2)
print(CAR_SEQUENCE)
[4 2 9 0 0 4 3 7 5 6 5 3 8 9 8 7 1 2 6 1]

The task is to paint the cars such that in the end for every pair of cars one is painted in red and the other in blue. The objective of the following minimization procedure is to minimize the number of color changes in the paintshop.

def color_changes(paint_bitstring):
  color_sequence = []
  painted_once = set()
  for car in CAR_SEQUENCE:
    if car in painted_once:
      color_sequence.append(not paint_bitstring[car])
    else:
      color_sequence.append(paint_bitstring[car])
      painted_once.add(car)
  paint_change_counter = 0
  for color0, color1 in zip(color_sequence[:-1], color_sequence[1:]):
    if color0 != color1:
      paint_change_counter += 1
  return paint_change_counter

If two consecutive cars in the sequence are painted in different colors the robots have to rinse the old color, clean the nozzles and flush in the new color. This color change procedure costs time, paint, water and ultimately costs money, which is why we want to minimize the number of color changes. However a rearrangement of the car sequence is not at our disposal (because of restrictions that are posed by the remainig manufacturing processes), but we can decide once we reach the first car of each car pair which color to paint the pair first. When we have chosen the color for the first car the other car has to be painted in the other respective color. Obvious generalizations exist, for example more than two colors and groups of cars with more than 2 cars where it is permissible to exchange colors, however for demonstration purposes it suffices to consider the here presented binary version of the paintshop problem. The binary paintshop problem is NP-hard and additionally it is NP-hard to come up with approximate solutions with an arbitrary performance guarantee. A performance guarantee in this context would be a proof that an approximation algorithm never gives us a solution with a number of color changes that is more than some factor times the optimal number of color changes. This is the situation where substantial quantum speedup can be assumed (c.f. Quantum Computing in the NISQ era and beyond). It can also be shown that the here presented quantum algorithm can deliver on average better solutions than all polynomial runtime heuristics specificall developed for the paintshop problem in constant time (constant query complexity) (c.f. Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm).

Spin Glass

To be able to solve the binary paintshop problem with the Quantum Approximate Optimization Algorithm (QAOA) we need to translate the problem to a spin glass problem. Interestingly that is possible with no spatial overhead, i.e. the spin glass has as many spins as the sequence has car pairs. The state of every spin represents the color we paint the respective first car in the seqence of every car pair. Every second car is painted with the repsective other color. The interactions of the spin glass can be deduced proceeding through the fixed car sequence: If two cars are adjacent to each other and both of them are either the first or the second car in their respective car pairs we can add a ferromagnetic interaction to the spin glass in order to penalize the color change between these two cars. If two cars are next to each other and one of the cars is the first and the other the second in their respective car pairs we have to add a antiferromagnetic interaction to the spin glass in order to penalize the color change because in this case the color for the car that is the second car in its car pair is exactly the opposite. All color changes in the car sequence are equivalent which is why we have equal magnitude ferromagnetic and antiferromagnetic interactions and additionally we choose unit magnitude interactions.

def spin_glass():
  ferromagnetic = -1
  antiferromagnetic = 1
  appeared_already = set()
  for car0, car1 in zip(CAR_SEQUENCE[:-1], CAR_SEQUENCE[1:]):
    if car0 == car1:
      continue
    if car0 in appeared_already:
      appeared_already.add(car0)
      if car1 in appeared_already:
        yield car0, car1, ferromagnetic
      else:
        yield car0, car1, antiferromagnetic
    else:
      appeared_already.add(car0)
      if car1 in appeared_already:
        yield car0, car1, antiferromagnetic
      else:
        yield car0, car1, ferromagnetic

Quantum Approximate Optimisation Algorithm

We want to execute a one block version of the QAOA circuit for the binary paintshop instance with p = 1 on a trapped-ion quantum computer of IonQ. This device is composed of 11 fully connected qubits with average single- and two-qubit fidelities of 99.5% and 97.5% respectively (Benchmarking an 11-qubit quantum computer). As most available quantum hardware, trapped ion quantum computers only allow the application of gates from a restricted native gate set predetermined by the physics of the quantum processor. To execute an arbitrary gate, compilation of the desired gate into available gates is required. For trapped ions, a generic native gate set consists of a parameterized two-qubit rotation, the Molmer Sorensen gate, $R_\mathrm{XX}(\alpha)=\mathrm{exp}[-\mathrm{i}\alpha \sigma_\mathrm{x}^{(i)}\sigma_\mathrm{x}^{(j)}/2]$ and a parametrized single qubit rotation,

$R(\theta,\phi)=\begin{pmatrix} \cos{(\theta/2)} & -\mathrm{i}\mathrm{e}^{-\mathrm{i}\phi}\sin{(\theta/2)} \-\mathrm{i}\mathrm{e}^{\mathrm{i}\phi}\sin{(\theta/2)} & \cos{(\theta/2)}
\end{pmatrix}$

QAOA circuits however employ parametrized two body $\sigma_z$ rotations, $R_\mathrm{ZZ}(\gamma)=\mathrm{exp}[-i\gamma \sigma_\mathrm{z}^{(i)}\sigma_\mathrm{z}^{(j)}]$. Therefore to circumvent compilation overhead and optimally leverage the Ion Trap we inject pairs of Hadamard gates $H H^{\dagger} = 1$ for every qubit in between the two body $\sigma_z$ rotations and therefore are able to formulate the phase separator entirely with Molmer Sorensen gates QAOA circuit such that the phase separator employs the native Molmer Sorensen gates and the QAOA starts in the state where all qubits are in the groundstate $\left| 0\right\rangle$ instead of the superposition of all computational basis states $\left| + \right\rangle$,

qubit_register = cirq.LineQubit.range(CAR_PAIR_COUNT)
def phase_separator(gamma):
  for car_pair0, car_pair1, interaction in spin_glass():
    yield cirq.ms(interaction * gamma).on(qubit_register[car_pair0],qubit_register[car_pair1])

circuit = cirq.Circuit()
circuit.append(phase_separator(0.1))

Because we replaced the two body $\sigma_z$ rotations with Molmer Sorensen gates we also have to adjust the mixer slightly to account for the injected Hadamard gates.

def mixer(beta):
  yield cirq.ry(np.pi/2).on_each(qubit_register), cirq.rx(beta - np.pi).on_each(qubit_register)

To find the right parameters for the QAOA circuit we have to assess the quality of the solutions for a goven set of parameters. To this end we execute the QAOA circuit with fixed parameters 100 times and calculate the average number of color changes

def average_color_changes(parameters):
  beta, gamma = parameters
  repetitions = 100
  circuit = cirq.Circuit()
  circuit.append(phase_separator(gamma))
  circuit.append(mixer(beta))
  circuit.append(cirq.measure(*qubit_register, key='z'))
  results = service.run(circuit, repetitions=repetitions)
  avg_cc = 0
  for paint_bitstring in results.measurements['z']:
    avg_cc += color_changes(paint_bitstring) / repetitions
  return avg_cc

We optimize the average number of color changes by adjusting the parameters with scipy.optimzes function minimize. The results of these optimsation runs strongly depend on the random starting values we choose for the parameters, which is why we restart the optimization procedure for different starting parameters 10 times and take the best performing optimized parameters.

from scipy.optimize import minimize
service =  cirq.Simulator()
beta, gamma = np.random.rand(2)
average_cc = average_color_changes([beta, gamma])
for _ in range(10):
  initial_guess = np.random.rand(2)
  optimization_result = minimize(average_color_changes,initial_guess,method="SLSQP",options={'eps': 0.1})
  average_cc_temp = average_color_changes(optimization_result.x)
  if average_cc > average_cc_temp:
    beta, gamma = optimization_result.x
    average_cc = average_cc_temp
average_cc
7.840000000000001

Note here that the structure of the problem graphs of the binary paintshop problem allow for an alternative technique to come up with good parameters independent of the specifics of the respective instance of the problem: Training the quantum approximate optimization algorithm without access to a quantum processing unit

Once the parameters are optimised, we execute the optimised QAOA circuit 100 times and output the solution with the least color changes. Please replace <your key> with your IonQ API key and <remote host> with the API endpoint.

repetitions = 100
circuit = cirq.Circuit()
circuit.append(phase_separator(gamma))
circuit.append(mixer(beta))
circuit.append(cirq.measure(*qubit_register, key='z'))
service = ionq.Service(remote_host='<remote host>', api_key='<your key>', default_target='qpu')
results = service.run(circuit, repetitions=repetitions)
best_result = CAR_PAIR_COUNT 
for paint_bitstring in results.measurements['z']:
  result = color_changes(paint_bitstring) 
  if result < best_result:
    best_result = result
    best_paint_bitstring = paint_bitstring
print(f'The minimal number of color changes found by level-1 QAOA is: {best_result}')
print(f'To achieve this number of color changes the first cars of the car pairs have to be painted with {best_paint_bitstring}')
The minimal number of color changes found by level-1 QAOA is: 6
To achieve this number of color changes the first cars of the car pairs have to be painted with [0 1 0 0 0 0 0 0 0 0]

Note here, that in a future production environment the optimisation and execution phase of the QAOA should be merged, i.e. we output in the end the best performing sample gathered during the training phase of the QAOA circuit. For educational purposes we separated here the training and the evaluation phase of the QAOA.