量子退火算法入门(3):整数分割问题的QUBO建模

薛定谔了么
2024-11-08 11:12:50

整数分割问题:

QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量。我先从简单的问题开始说明,让大家有些直观感受。整数分割问题就是一个非常简单,并容易理解的例子。此文参考了日本NTT公司的量子计算指南文档[*1]。

·整数分割问题定义:

判断能否将一个N 个整数 a 1 , ・・・ a N  的整数集合分割成两个子集合,并且这两个子集合里的元素之和相等。

·例子:

我们可以看到,上面👆的例子,分割后的两个子集合A和B的元素之和都等于6,所以该集合是可以满足整数分割的。

转化为组合优化问题:

之前讲的QUBO的例子里,用的变量都是0或1。其实,还可以是-1或+1,这时候也叫ising模型。求解变量什么时候用0/1,什么用-1/+1,这个之后用例子给大家解释。

这次的问题,是把求解的两个子集合的标签作为-1/+1的变量。如下图所示。

我们的优化目标就成为了,最小化两个子集合的差值的平方和。大家可以思考一下,如果使用0/1作为子集合A和B的标签,我们要怎么定义最小化的目标函数。

·目标集合为{ 1, 5, 6 }时的目标函数就是:

我们来枚举一下,所有 x i  从-1或+1取值的组合结果:

我们可以看到,目标函数值为0时,我们得到了正确的整数分割结果。

目标函数转化为QUBO:

因为已经获得了目标函数,那我们先把多项式展开就好了。展开结果如下图所示:

因为【x i从-1或+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) 

运行结果如下:

我们可以将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}

以上就是一个简单建模的例子。下篇讲旅行商问题的建模。

————————————————

本文转载自CSDN博主:gang_unerry

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

原文链接:https://blog.csdn.net/gangshen1993/article/details/127594967

70
0
0
0
关于作者
相关文章
  • 量子退火算法入门(7):QUBO中的三次多项式怎么转换? ...
    前言本文还是大部分截图来自于:《最適化問題とWildqatを用いた量子アニーリング計算入門》 http ...
    了解详情 
  • 量子退火算法入门(6):初识量子退火算法的发明过程 ...
    一、量子计算机量子计算机就是使用量子bit实现的计算机。之前提到过,可以分为两类,量子门(gate ...
    了解详情 
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」 ...
    一,旅行商问题QUBO的两种实现看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始 ...
    了解详情 
  • 量子退火算法入门(4):旅行商问题的QUBO建模「上 篇」 ...
    了解详情 
在本版发帖返回顶部
快速回复 返回顶部 返回列表