common.title
Cloud support

Nobisuke

Dekisugi

RAG


autoQAOA
RAG for dev
Fortune telling app
Annealing
DEEPSCORE
Translation

Overview
Service overview
Terms of service

Privacy policy

Contact
Research

Sign in
Sign up
common.title

使用 HOBO Solver 优化图着色问题

Yuichiro Minato

2024/08/11 03:51

使用 HOBO Solver 优化图着色问题

大家好!今天,我想介绍我们最新的创新产品——HOBO Solver,它可以高效地解决图着色问题。

https://github.com/ShoyaYasuda/hobotan

图着色问题涉及将相邻的区域涂上不同的颜色。通常,当我们使用量子比特来解决这个问题时,每个区域需要四个量子比特来进行一位热编码。例如,如果我们需要用四种颜色为五个区域着色,则需要20个量子比特。

然而,使用我们的 HOBO Solver,可以显著优化这一过程。HOBO Solver 只需每个区域使用两个量子比特即可解决问题。因此,原本需要20个量子比特才能解决的五个相邻区域的着色问题,现在只需要10个量子比特就能解决。

image

当相邻区域的比特相同时,代价增加。
例如:

  • (x0-x2)^2 在值相同的情况下为0,在值不同的情况下为1。
  • ((x0-x2)^2 -1)^2 在值相同的情况下为1,在值不同的情况下为0。
    同样地,((x1-x3)^2-1)^2 在值相同的情况下为1,在值不同的情况下为0。
    接下来,当两个值都为1时,会有一个惩罚。只有在两个值都为1时,乘积结果才为1:
    ((x0-x2)^2 -1)^2 * ((x1-x3)^2 -1)^2 确保相邻区域被不同颜色着色。
    由于这是一个最多四次方程,因此成为了 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 Solver 不仅适用于图着色问题,还可以用于许多其他优化问题。

我们将继续在量子计算领域进行研究和开发,致力于进一步优化和提升性能。在我们接下来的博客文章中,我们将深入探讨 HOBO Solver 的技术细节,敬请期待!

下次再见。

© 2024, blueqat Inc. All rights reserved