 View on QuantumAI
|
 Run in Google Colab
|
 View source on GitHub
|
 Download notebook
|
from typing import Sequence, Tuple
import numpy as np
try:
import cirq
except ImportError:
print("installing cirq...")
!pip install --quiet cirq
print("installed cirq.")
import cirq
import cirq_ionq as ionq
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.
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: Sequence[int], car_sequence: Sequence[int]) -> int:
"""Count the number of times the color changes if the robots
paint each car in car_sequence according to paint_bitstring,
which notes the color for the first car in each pair.
Args:
paint_bitstring: A sequence that determines the color to
paint the first car in pair i. For example, 0 for blue
and nonzero for red.
car_sequence: A sequence that determines which cars are
paired together
Returns:
Count of the number of times the robots change the color
"""
color_sequence = []
painted_once = set()
for car in car_sequence:
if car in painted_once:
# paint the other color for the second car in the pair
color_sequence.append(not paint_bitstring[car])
else:
# paint the noted color for the first car in the pair
color_sequence.append(paint_bitstring[car])
painted_once.add(car)
paint_change_counter = 0
# count the number of times two adjacent cars differ in color
for color0, color1 in zip(color_sequence, 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. It is NP-hard to solve the binary paintshop problem exactly as well as approximately 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). The quantum algorithm presented here can deliver, on average, better solutions than all polynomial runtime heuristics specifically 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(car_sequence: Sequence[int]) -> Sequence[Tuple[int, int, int]]:
"""Assign interactions between adjacent cars.
Assign a ferromagnetic(1) interaction if both elements of the pair are
the first/second in their respective pairs. Otheriwse, assign an antiferromagnetic(-1)
interaction. Yield a tuple with the two paired cars followed by the
chosen interaction.
"""
ferromagnetic = -1
antiferromagnetic = 1
appeared_already = set()
for car0, car1 in zip(car_sequence, 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 Optimization 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 employ parametrized two body \(\sigma_z\) rotations, \(R_\mathrm{ZZ}(\gamma)=\mathrm{exp}[-i\gamma \sigma_\mathrm{z}^{(i)}\sigma_\mathrm{z}^{(j)}]\). To circumvent a 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. This means we are able to formulate the phase separator entirely with Molmer Sorensen gates. To support this, the QAOA circuit 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\),
def phase_separator(
gamma: float, qubit_register: Sequence[cirq.Qid], car_sequence: Sequence[int]
) -> Sequence[cirq.Operation]:
"""Yield a sequence of Molmer Sorensen gates to implement a
phase separator over the ferromagnetic/antiferromagnetic
interactions between adjacent cars, as defined by spin_glass
"""
for car_pair0, car_pair1, interaction in spin_glass(car_sequence):
yield cirq.ms(interaction * gamma).on(
qubit_register[car_pair0], qubit_register[car_pair1]
)
qubit_register = cirq.LineQubit.range(CAR_PAIR_COUNT)
circuit = cirq.Circuit([phase_separator(0.1, qubit_register, car_sequence)])
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: float, qubit_register: Sequence[cirq.Qid]) -> Iterator[cirq.Operation]:
"""Yield a QAOA mixer of RX gates, modified by adding RY gates first,
to account for the additional Hadamard gates.
"""
yield cirq.ry(np.pi / 2).on_each(qubit_register)
yield 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 given 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: Tuple[float, float],
qubit_register: Sequence[cirq.Qid],
car_sequence: Sequence[int],
) -> float:
"""Calculate the average number of color changes over all measurements of
the QAOA circuit, aross `repetitions` many runs, for provided parameters
beta and gamma.
Args:
parameters: tuple of (`beta`, `gamma`), the two parameters for the QAOA circuit
qubit_register: A sequence of qubits for the circuit to use.
car_sequence: A sequence that determines which cars are paired together.
Returns:
A float average number of color changes over all measurements.
"""
beta, gamma = parameters
repetitions = 100
circuit = cirq.Circuit()
circuit.append(phase_separator(gamma, qubit_register, car_sequence))
circuit.append(mixer(beta, qubit_register))
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, car_sequence) / 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], qubit_register, car_sequence)
optimization_function = lambda x: average_color_changes(x, qubit_register, car_sequence)
for _ in range(10):
initial_guess = np.random.rand(2)
optimization_result = minimize(
optimization_function, initial_guess, method="SLSQP", options={"eps": 0.1}
)
average_cc_temp = average_color_changes(
optimization_result.x, qubit_register, car_sequence
)
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, qubit_register, car_sequence))
circuit.append(mixer(beta, qubit_register))
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, car_sequence)
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"The car pairs have to be painted according to {best_paint_bitstring}, with index i representing the paint of the first car of pair i."
)
print(f" The other car in pair i is painted the second color.")
The minimal number of color changes found by level-1 QAOA is: 6 The first cars of the car pairs have to be painted with [0 1 0 0 0 0 0 0 0 0], with index i representing the paint of the first car on pair i. The other car in pair i is painted with the second color.
Note here, that in a future production environment the optimization 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.