entropicalabs / openqaoa

Multi-backend SDK for quantum optimisation
MIT License
113 stars 59 forks source link

UF: Adding the K-Color problem #251

Closed alejomonbar closed 12 months ago

alejomonbar commented 1 year ago

Unitary Fund

Adding the k-color class with its corresponding test. https://en.wikipedia.org/wiki/Graph_coloring

Description

This pull request adds support for the k-color problem, a combinatorial optimization problem related to graph coloring. The k-color problem involves assigning colors to the vertices of a graph such that no two adjacent vertices have the same color while minimizing the number of colors used.

The implementation includes a new class KColor in the existing problem module. The KColor class allows the creation of instances of the k-color problem and provides methods for solving the problem using the Docplex solver, visualizing the graph with a given solution, and obtaining the qubo.

Example:

from openqaoa.problems import KColor
import matplotlib.pyplot as plt
from openqaoa import QAOA

kc = KColor.random_instance(n_nodes=5, edge_probability=0.7, k=3)
sol = kc.classical_solution()

qaoa = QAOA()
qaoa.compile(kc.qubo)
qaoa.optimize()

sol_qaoa = qaoa.result.lowest_cost_bitstrings()["solutions_bitstrings"][0]

fig, ax = plt.subplots(1, 2, figsize = (10, 5))
kc.plot_solution(sol_qaoa, ax=ax[0])
ax[0].set_title("QAOA Results")
kc.plot_solution(sol, ax=ax[1])
ax[1].set_title("CPLEX Results")
Screenshot 2023-08-08 at 5 17 26 AM

Checklist

Type of change

Please delete options that are not relevant.

How Has This Been Tested?

the test is inside './tests/test_problems.py'