整数分割问题:
QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量。我先从简单的问题开始说明,让大家有些直观感受。整数分割问题就是一个非常简单,并容易理解的例子。此文参考了日本NTT公司的量子计算指南文档[*1]。
- 整数分割问题定义:
判断能否将一个N 个整数 a 1 , ・・・ a N a_1,・・・a_N a1,・・・aN 的整数集合分割成两个子集合,并且这两个子集合里的元素之和相等。
- 例子:
我们可以看到,上面👆的例子,分割后的两个子集合A和B的元素之和都等于6,所以该集合是可以满足整数分割的。
转化为组合优化问题:
之前讲的QUBO的例子里,用的变量都是0或1。其实,还可以是-1或+1,这时候也叫ising模型。求解变量什么时候用0/1,什么用-1/+1,这个之后用例子给大家解释。
这次的问题,是把求解的两个子集合的标签作为-1/+1的变量。如下图所示。
我们的优化目标就成为了,最小化两个子集合的差值的平方和。大家可以思考一下,如果使用0/1作为子集合A和B的标签,我们要怎么定义最小化的目标函数。
- 目标集合为{ 1, 5, 6 }时的目标函数就是:
我们来枚举一下,所有 x i x_i xi 从-1或+1取值的组合结果:
我们可以看到,目标函数值为0时,我们得到了正确的整数分割结果。
目标函数转化为QUBO:
因为已经获得了目标函数,那我们先把多项式展开就好了。展开结果如下图所示:
因为【
x
i
x_i
xi 从-1或+1取值】这个设定,下面👇的式子是成立的:
・
x
i
2
=
1
・x_i^{2} = 1
・xi2=1
所以我们可以得到下面的QUBO结果:
最后献上Python代码。
PyQUBO实现Ising模型:
之前的目标函数都是展开后的二次多项式,大家可以直接计算出QUBO矩阵。这次使用PyQUBO直接定义目标函数,大家就不用手动求解QUBO矩阵了。
import pyqubo
import neal
x = pyqubo.Array.create('x', shape=(3), vartype='SPIN') # 'SPIN' 就表示目标变量是从{-1, 1}取值。目标变量需要从{0, 1}中取值时,就设定为 'BINARY'
objective_function = (1 * x[0] + 5 * x[1] + 6 * x[2]) ** 2
model = objective_function.compile()
bqm = model.to_bqm()
print("我们可以将bqm转为ising或qubo输出")
print(bqm.to_ising())
sa = neal.SimulatedAnnealingSampler()
sampleset = sa.sample(bqm, num_reads=10)
samples = model.decode_sampleset(sampleset)
best_sample = min(samples, key=lambda s: s.energy)
print("求解时,pyqubo内部已经将ising模型转换为qubo的0或1,所以输出结果为0或1")
print(best_sample.sample)
运行结果如下:文章来源:https://www.toymoban.com/news/detail-427392.html
我们可以将bqm转为ising或qubo输出
({'x[2]': 0.0, 'x[0]': 0.0, 'x[1]': 0.0}, {('x[0]', 'x[2]'): 12.0, ('x[1]', 'x[2]'): 60.0, ('x[1]', 'x[0]'): 10.0}, 62.0)
求解时,pyqubo内部已经将ising模型转换为qubo的0或1,所以输出结果为0或1
{'x[2]': 1, 'x[0]': 0, 'x[1]': 0}
以上就是一个简单建模的例子。下篇讲旅行商问题的建模。文章来源地址https://www.toymoban.com/news/detail-427392.html
- 参考文献:[*1] : https://www.nttdata.com/jp/ja/-/media/nttdatajapan/files/news/services_info/2021/012800/012800-01.pdf
到了这里,关于量子退火算法入门(3):整数分割问题的QUBO建模的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!