量子计算-P2.PyQUBO使用-Number Partitioning Problem
量子计算-P2.PyQUBO使用-Number Partitioning Problem
DrugScience
发布于 2022-09-19 14:30:03
发布于 2022-09-19 14:30:03
简介：
PyQUBO允许您轻松地从灵活的数学表达式创建qubo或Ising模型。PyQUBO的一些特征是
- 基于Python（C++后端）。
- 与Ocean SDK完全集成。
- 约束的自动验证。
- 用于参数调整的占位符。
使用：
- 安装
pip install pyqubo 或者
python setup.py install- 使用案例
我们来求上文提到的 Number Partitioning Problem 问题，也叫做数字划分问题，它属于Np-Hard。
可以描述为，给定一个集合
S = {3,1,1,2,2,1}
如何在其中划分两个集合，使得两个集合中的元素加和相等。
解的话可以是：
S(1) = {1,1,1,2} and S(2) = {2,3}
其中每个集合中的元素相加都为5
那么此问题可以等价于
(a1s1+a2s2+a3s3+a4s4+a5s5+a6s6)**2 = 0
- a为系数，即为S中元素的值
- s代表此元素是否被选择，二值变量
- 构建QUBO
from pyqubo import Spin
# 创建spin变量，你可以i简单理解为选择或者不选择
s1,s2,s3,s4,s5,s6 = Spin("s1"), Spin("s2"), Spin("s3"), Spin("s4"),Spin("s5"), Spin("s6")
H = (3*s1 + 1*s2 + 1*s3 + 2*s4 + 2*s5 + 1*s6)**2
# 编译
model = H.compile()
# 模型返回QUBO
qubo, offset = model.to_qubo()
print(qubo)
{('s3', 's5'): 16.0,
('s1', 's6'): 24.0,
('s4', 's6'): 16.0,
('s1', 's3'): 24.0,
('s2', 's5'): 16.0,
('s6', 's6'): -36.0,
('s2', 's3'): 8.0,
('s2', 's4'): 16.0,
('s1', 's5'): 48.0,
('s3', 's4'): 16.0,
('s1', 's2'): 24.0,
('s3', 's3'): -36.0,
('s2', 's6'): 8.0,
('s1', 's4'): 48.0,
('s4', 's5'): 32.0,
('s3', 's6'): 8.0,
('s5', 's6'): 16.0,
('s5', 's5'): -64.0,
('s1', 's1'): -84.0,
('s4', 's4'): -64.0,
('s2', 's2'): -36.0}- 使用PyQUBO自带的模拟退火算子进行求解
import neal# 创建SA求解器
sampler = neal.SimulatedAnnealingSampler()
# 模型转化为dimod.BinaryQuadraticModel类型bqm = model.to_bqm()
# 采样
sampleset = sampler.sample(bqm)
# 解码
decoded_samples = model.decode_sampleset(sampleset)
best_sample = min(decoded_samples, key=lambda x: x.energy)
# 输出最优解
best_sample.sample
{'s6': 0, 's3': 1, 's5': 1, 's1': 0, 's4': 1, 's2': 0}
即为：分组为{'s6': 0, 's1': 0, 's2': 0}为一组，{'s3': 1, 's5': 1, 's4': 1}为一组
参考文献：
- PyQUBO网址：https://pyqubo.readthedocs.io/en/latest/
- 数字划分问题：https://en.wikipedia.org/wiki/Partition_problem
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-07-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
