Solve a QUBO problem
In this notebook, we solve a quadratic unconstrained binary optimization (QUBO) problem with Qadence. QUBOs are very popular combinatorial optimization problems with a wide range of applications. Here, we solve the problem using the QAOA 1 variational algorithm by embedding the QUBO problem weights onto a register as standard for neutral atom quantum devices.
Additional background information on QUBOs can be found here, directly solved using the pulse-level interface Pulser.
Define and solve QUBO
Pre-requisite: optimal register coordinates for embedding the QUBO problem
A basic ingredient for solving a QUBO problem with a neutral atom device is to embed the problem onto the atomic register. In short, embedding algorithms cast the problem onto a graph mapped onto the register by optimally finding atomic coordinates. A discussion on the embedding algorithms is beyond the scope of this tutorial and a simplified version taken from here is added below.
With the embedding routine under our belt, let's start by adding the required imports and ensure the reproducibility of this tutorial.
The QUBO problem is initially defined by a graph of weighted edges and a cost function to be optimized. The weighted edges are represented by a
real-valued symmetric matrix Q which is used throughout the tutorial.
The QAOA algorithm needs a variational quantum circuit with optimizable parameters. For that purpose, we use a fully analog circuit composed of two global rotations per layer on different axes of the Bloch sphere. The first rotation corresponds to the mixing Hamiltonian and the second one to the embedding Hamiltonian 1. In this setting, the embedding is realized by the appropriate register coordinates and the resulting qubit interaction.
Rydberg level
The Rydberg level is set to 70. We initialize the weighted register graph from the QUBO definition similarly to what is done in the original tutorial, and set the device specifications with the updated Rydberg level.
By feeding the circuit to a QuantumModel we can check the initial
counts where no clear solution can be found:
Finally, we can proceed with the variational optimization. The cost function
defined above is derived from bitstring computations and therefore non differentiable. We use Qadence
ML facilities to run gradient-free optimizations using the
nevergrad library.
config = TrainConfig(max_iter=100)
optimizer = ng.optimizers.NGOpt(
budget=config.max_iter, parametrization=num_parameters(model)
)
train_gradient_free(model, None, optimizer, config, loss)
optimal_counts = model.sample({}, n_shots=1000)[0]
Finally, let's plot the solution. The expected bitstrings are marked in red.
# Known solutions to the QUBO problem.
solution_bitstrings = ["01011", "00111"]
def plot_distribution(C, ax, title):
C = dict(sorted(C.items(), key=lambda item: item[1], reverse=True))
indexes = solution_bitstrings # QUBO solutions
color_dict = {key: "r" if key in indexes else "g" for key in C}
ax.set_xlabel("bitstrings")
ax.set_ylabel("counts")
ax.set_xticks([i for i in range(len(C.keys()))], C.keys(), rotation=90)
ax.bar(list(C.keys())[:20], list(C.values())[:20])
ax.set_title(title)
fig, axs = plt.subplots(1, 2, figsize=(12, 4))
plot_distribution(initial_counts, axs[0], "Initial counts")
plot_distribution(optimal_counts, axs[1], "Optimal counts")