Optimizing Graph Coloring Problems with the HOBO Solver

Optimizing Graph Coloring Problems with the HOBO Solver

Hello everyone! Today, I’d like to introduce our latest innovation, the “HOBO Solver,” which can efficiently solve graph coloring problems.

https://github.com/ShoyaYasuda/hobotan

A graph coloring problem involves coloring adjacent areas with different colors. Typically, when solving this problem using qubits, we use four qubits per area for one-hot encoding. For example, if we need to color five areas with four colors, we would require 20 qubits.

However, using our HOBO Solver, we can significantly optimize this process. The HOBO Solver can solve the problem using just two qubits per area. As a result, the problem of coloring five adjacent areas, which previously required 20 qubits, can now be solved with just 10 qubits.

The cost increases when the bits of adjacent areas are the same.
For example:

• (x0-x2)^2 is 0 when the values are the same and 1 when different.
• ((x0-x2)^2 -1)^2 is 1 when the values are the same and 0 when different.
  Similarly, ((x1-x3)^2-1)^2 is 1 when the values are the same and 0 when different.
  Next, there is a penalty when both values are 1. Multiplying both results in 1 only when both are 1:
  ((x0-x2)^2 -1)^2 * ((x1-x3)^2 -1)^2 ensures that adjacent areas are colored differently.
  Since this is a maximum of a fourth-degree equation, it becomes a HOBO.

Formulating this for all adjacent areas:

from hobotan import *

q = symbols_list(10, 'q{}')

H =  ((q[0] - q[2])**2 -1)**2 * ((q[1] - q[3])**2 -1)**2 #AB
H +=  ((q[0] - q[6])**2 -1)**2 * ((q[1] - q[7])**2 -1)**2 #AD
H +=  ((q[2] - q[6])**2 -1)**2 * ((q[3] - q[7])**2 -1)**2 #BD
H +=  ((q[2] - q[4])**2 -1)**2 * ((q[3] - q[5])**2 -1)**2 #BC
H +=  ((q[2] - q[8])**2 -1)**2 * ((q[3] - q[9])**2 -1)**2 #BE
H +=  ((q[4] - q[8])**2 -1)**2 * ((q[5] - q[9])**2 -1)**2 #CE
H +=  ((q[6] - q[8])**2 -1)**2 * ((q[7] - q[9])**2 -1)**2 #DE

hobo, offset = Compile(H).get_hobo()
print(f'offset\n{offset}')

solver = sampler.SASampler(seed=0)
result = solver.run(hobo, shots=100)

for r in result:
    print(r)
    arr, subs = Auto_array(r[0]).get_ndarray('q{}')
    print(arr)

With this advancement, we can use quantum computing resources more efficiently. The HOBO Solver is not only applicable to graph coloring problems but also to many other optimization problems.

We will continue to advance our research and development in the field of quantum computing, aiming for further optimization and performance improvements. In our next blog post, we will delve deeper into the technical details of the HOBO Solver, so stay tuned!

Until next time.