HOBOソルバーでグラフカラーリング問題を効率化

HOBOソルバーでグラフカラーリング問題を効率化

皆さん、こんにちは！今日は、私たちの最新のイノベーション「HOBOソルバー」についてご紹介します。グラフカラーリング問題を効率的に解決することができます。

https://vigne-cla.com/21-41/

グラフカラーリング問題とは、隣接するエリアが異なる色で塗り分けられるようにする問題です。通常、この問題を量子ビットで解く場合、各エリアに対して4つの量子ビットを使用してワンホットエンコーディングを行います。例えば、5つのエリアを4色で塗り分ける場合、20量子ビットが必要になります。

しかし、私たちが開発したHOBOソルバーを使用すると、この問題を大幅に効率化できます。HOBOソルバーは、各エリアに対してわずか2つの量子ビットを使用して問題を解決することができます。これにより、5つのエリアの隣接する色塗り分け問題において、従来必要だった20量子ビットが、なんと10量子ビットで解けるようになります。

隣接するエリアのビットが両方同じ時にコストが上がるように設定。
(x0-x2)^2で同じ時に0 違う時に1、((x0-x2)^2 -1)^2で同じ時に1 違う時に0
同様に((x1-x3)^2-1)^2で同じ時に1 違う時に0
次に両方1の時にペナルティ。両方かければ11の時だけ1なので、
((x0-x2)^2 -1)^2 * ((x1-x3)^2-1)^2 が隣接するエリアの色が違う色に塗り分け
最大4次式なのでHOBOとなります。

これを隣接するエリア全てにおいて定式化すると、

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)

この進展により、量子コンピューティングのリソースをより効率的に使用することができます。HOBOソルバーは、グラフカラーリング問題だけでなく、他の多くの最適化問題にも応用可能です。

今後も私たちは、量子コンピューティングの分野での研究開発を進め、さらなる効率化と性能向上を目指していきます。次回のブログでは、HOBOソルバーの技術的な詳細についてさらに深掘りしていきますので、どうぞお楽しみに！

それでは、また次回お会いしましょう。