最前沿・量子退火建模方法(1) : subQUBO讲解和python实现
前言
量子退火机在小规模问题上的效果得到了有效验证,但是由于物理量子比特的大规模制备以及噪声的影响,还没有办法再大规模的场景下应用。
这时候就需要我们思考,如何通过软件的方法怎么样把大的问题分解成小的问题,以便通过现在小规模的量子退火机解决。主要思路就是,同样的QUBO建模,怎么使用更少的量子比特。
下面的文章中,量子退火机和伊辛机会混用。
一、subQUBO的创新点
先行的研究中,使用启发式方法将大型问题划分为较小的问题,并使用伊辛机进行求解,但划分后的问题的答案与原始大型问题的答案并不相同。达成协议的理论条件仍不清楚。早稻田大学的研究者开发出了subQUBO算法在保证分解后的小问题也能保证在原始大问题上的理论上做出了突破。
Atobe, Yuta, Masashi Tawada, and Nozomu Togawa. "Hybrid annealing method based on subQUBO model extraction with multiple solution instances." IEEE Transactions on Computers 71.10 (2021): 2606-2619.
subQUBO的创新点:
- 首先研究将大规模组合优化问题划分为较小问题而不失去最优性的条件。该条件成立的话就证明,如果用伊辛机来解决一个满足条件的小问题,它就会和原来的大规模问题的答案相匹配。
- 还提出了一种新算法,成功地从大规模问题中提取出此类条件,将原始大规模问题缩小到伊辛机可以解决的问题规模,并迭代求解。所提出的算法通过基于理论支持将大规模问题分解为更小的问题来解决它,使得以比传统技术更高的精度解决原始大规模问题成为可能。
二、subQUBO的详细思路
1. 怎么把大规模问题分解成小问题
1.1 逻辑前提:挑出错误后,回炉重造
- 大规模组合优化问题的QUBO建模中,最终的答案由多个量子比特集合组成。
- 如果你创建一个小规模问题,其中包括最终解的量子比特集合中的,所有不正确的量子比特集合,
- 并使用伊辛机解决该问题,则所有最终解的不正确的量子比特集合都将被纠正为正确的量子比特集合作为解。
1.2 具体实现:
实现方法: 可以创建一个大致包含所有不正确的量子比特集合的小问题,并使用伊辛机重复解决它。
-
不正确的量子比特集合创建:
– 我们使用传统的经典计算器来准备问题的多个候选答案。这些候选答案不一定是正确的,但在比较经典计算器求解得到的多个答案的量子比特集合的最终值。
– 多个候选中匹配一致的就是正确的量子比特集合;
– 答案不匹配且不同的就是不正确的量子比特集合。 -
通过仅提取不正确的量子比特集合,并使用真实的伊辛机进行求解,最终可以获得整体的正确答案。
1.3 业界影响:
传统上,伊辛机很难解决大规模问题,因为可用位数受到硬件限制,但通过使用这种方法,可以使用伊辛机进行计算。因此,人们认为可以使用伊辛机(包括量子退火机)扩展现实世界组合优化问题的用例。此外,本研究尝试将经典计算机与伊辛机相结合来解决问题,这将大大扩展伊辛机的使用范围。
最新成果,参考以下新闻:
Quanmatic Co., Ltd.利用量子计算技术解决方案规模突破1亿比特
https://prtimes.jp/main/html/rd/p/000000015.000117406.html
三、subQUBO的python实现
- 导入库
import random
import itertools
import numpy as np
from dataclasses import dataclass
- 设置subQUBO所需参数
N_I = 20 # instance池
N_E = 10 # subQUBO的抽取次数
N_S = 10 # N_I个instance池中抽取的解的个数
sub_qubo_size = 5 # subQUBO的量子比特数
- QUBO建模
# 为了简单,使用TSP作为例子
NUM_CITY = 4
ALPHA = 1
np.random.seed(0)
num_spin = NUM_CITY ** 2distance_mtx = np.random.randint(1, 100, (NUM_CITY, NUM_CITY))
distance_mtx = np.tril(distance_mtx) + np.tril(distance_mtx).T - 2 * np.diag(distance_mtx.diagonal())# <<< Objective term >>>
qubo_obj = np.zeros((NUM_CITY**2, NUM_CITY**2), dtype=np.int32)
for t_u_v in itertools.product(range(NUM_CITY), repeat=3):t, u, v = t_u_v[0], t_u_v[1], t_u_v[2]idx_i = NUM_CITY * t + uif t < NUM_CITY - 1:idx_j = NUM_CITY * (t + 1) + velif t == NUM_CITY - 1:idx_j = vqubo_obj[idx_i, idx_j] += distance_mtx[u, v]
qubo_obj = np.triu(qubo_obj) + np.tril(qubo_obj).T - np.diag(np.diag(qubo_obj))# <<< Constraint term >>>
qubo_constraint = np.zeros((NUM_CITY**2, NUM_CITY**2), dtype=np.int32)
# Calculate constraint term1 : 1-hot of horizontal line
for t in range(NUM_CITY):for u in range(NUM_CITY - 1):for v in range(u + 1, NUM_CITY):qubo_constraint[NUM_CITY*t+u, NUM_CITY*t+v] += ALPHA * 2
# Linear term
for t_u in itertools.product(range(NUM_CITY), repeat=2):qubo_constraint[NUM_CITY*t_u[0]+t_u[1], NUM_CITY*t_u[0]+t_u[1]] += ALPHA * (-1)
const_constraint = ALPHA * NUM_CITY# Calculate constraint term2 : 1-hot of vertical line
# Quadratic term
for u in range(NUM_CITY):for t1 in range(NUM_CITY - 1):for t2 in range(t1+1, NUM_CITY):qubo_constraint[NUM_CITY*t1+u, NUM_CITY*t2+u] += ALPHA * 2
# Linear term
for u_t in itertools.product(range(NUM_CITY), repeat=2):qubo_constraint[NUM_CITY*u_t[1]+u_t[0], NUM_CITY*u_t[1]+u_t[0]] += ALPHA * (-1)
const_constraint += ALPHA * NUM_CITY
- 创建instance池
@dataclass
class Solution():"""Solution information.Attributes:x (np.ndarray): n-sized solution composed of binary variablesenergy_all (float): energy value obtained from QUBO-matrix of all termenergy_obj (float): energy value obtained from QUBO-matrix of objective termenergy_constraint (float): energy value obtained from QUBO-matrix of constraint termconstraint (bool): flag whether the solution satisfies the given constraint"""x: np.ndarrayenergy_all: float = 0energy_obj: float = 0energy_constraint: float = 0constraint: bool = True@classmethoddef energy(cls, qubo:np.ndarray, x: np.ndarray, const=0) -> float:"""Calculate the enrgy from the QUBO-matrix & solution xArgs:qubo (np.ndarray): n-by-n QUBO-matrixx (np.ndarray): n-sized solution composed of binary variablesconst (int, optional): _description_. Defaults to 0.Returns:float: Energy value."""return float(np.dot(np.dot(x, qubo), x) + const)@classmethoddef check_constraint(cls, qubo: np.ndarray, x: np.ndarray, const=0) -> bool:"""Check whether the solution satisfies the constraints.Args:qubo (np.ndarray): QUBO-model of the constraint term.x (np.ndarray): solution that you want to check.const (int, optional): constant of the constraint term. Defaults to 0.Returns:bool: Return True if the solution satisfy.Return False otherwise."""return True if cls.energy(qubo, x, const) == 0 else False
- subQUBO Hybrid Annealing Algorithm
# https://ieeexplore.ieee.org/document/9664360# <<< Line 2-4 >>>
# Initialize the Instance Pool
pool = []
for i in range(N_I):# ====================# 实验时改动此参数x = np.random.randint(0, 2, num_spin) # 生成随机解# ====================energy_obj = Solution.energy(qubo_obj, x)energy_constraint = Solution.energy(qubo=qubo_constraint, x=x, const=const_constraint)pool.append(Solution(x = x,energy_all = energy_obj + energy_constraint,energy_obj = energy_obj,energy_constraint = energy_constraint,constraint = Solution.check_constraint(qubo=qubo_constraint, x=x, const=const_constraint)))
ascending_order_idx = np.argsort(np.array(list(map(lambda sol: sol.energy_all, pool))))
pool = [pool[i] for i in ascending_order_idx]# <<< Line 5 >>>
# Find the best solution
ascending_order_idx = np.argsort(np.array(list(map(lambda sol: sol.energy_all, pool))))
x_best = pool[ascending_order_idx[0]]for _ in range(1): # <<< Line 6 >>># <<< Line 7-8 >>># Obtain a quasi-ground-state solution for every N_I solution instance by a classical QUBO solverfor solution_i in pool:# ====================# 实验时改动此参数x = np.random.randint(0, 2, num_spin) # 生成随机解# ====================# Update the solution infosolution_i.x = xenergy_obj = solution_i.energy(qubo_obj, x)energy_constraint = solution_i.energy(qubo_constraint, x, const_constraint)solution_i.energy_all = energy_obj + energy_constraintsolution_i.energy_obj = energy_objsolution_i.energy_constraint = energy_constraintsolution_i.constraint = solution_i.check_constraint(qubo=qubo_constraint, x=x, const=const_constraint)for i in range(N_E): # <<< Line 9 >>># <<< Line 10 >>># Select N_S solution instance randomly from the pooln_s_pool = random.sample(pool, N_S)# <<< Line 11-14 >>># Calculate variance of each spin x_i in N_S instance poolSolution.check_constraint(qubo_constraint, x, const_constraint)vars_of_x = np.array([sum(n_s_pool[k].x[j] for k in range(N_S)) - N_S/2 for j in range(num_spin)])# <<< Line 15 >>># Select a solution randomly from N_S solution instance pool as a tentative solutionsolution_tmp = random.choice(n_s_pool)# Extract a subQUBOextracted_spin_idx = np.argsort(vars_of_x)[:sub_qubo_size]non_extracted_spin_idx = np.argsort(vars_of_x)[sub_qubo_size:]subqubo_obj = np.array([[qubo_obj[j, k] for k in extracted_spin_idx] for j in extracted_spin_idx])subqubo_constraint = np.array([[qubo_constraint[j, k] for k in extracted_spin_idx] for j in extracted_spin_idx])for idx_i in range(sub_qubo_size):subqubo_obj[idx_i, idx_i] += sum(qubo_obj[idx_i, idx_j] * solution_tmp.x[idx_j] for idx_j in non_extracted_spin_idx)subqubo_constraint[idx_i, idx_i] += sum(qubo_constraint[idx_i, idx_j] * solution_tmp.x[idx_j] for idx_j in non_extracted_spin_idx)# <<< Line 16 >>># Optimize the subQUBO using an Ising machine# ====================# 实验时改动此参数x_sub = np.random.randint(0, 2, sub_qubo_size) # 生成随机解# ====================# Combine the quasi-ground-state solution from the subQUBO with the tentative solution X_t(solution_tmp)for idx, val in enumerate(extracted_spin_idx):solution_tmp.x[idx] = x_sub[idx]# <<< Line 17 >>># Add the solution into the poolpool.append(solution_tmp)# <<< Line 18 >>># Find the best soliutionascending_order_idx = np.argsort(np.array(list(map(lambda sol: sol.energy_all, pool))))x_best = pool[ascending_order_idx[0]]# <<< Line 19 >>># Arrange the N_I instance poolsorted_pool = [pool[i] for i in ascending_order_idx]pool = sorted_pool[:N_I]pool, x_best
总结
subQUBO思路很简单,希望大家可以看着代码,理解如果实现。这个算法已经被早稻田大学申请专利了。
相关文章:

最前沿・量子退火建模方法(1) : subQUBO讲解和python实现
前言 量子退火机在小规模问题上的效果得到了有效验证,但是由于物理量子比特的大规模制备以及噪声的影响,还没有办法再大规模的场景下应用。 这时候就需要我们思考,如何通过软件的方法怎么样把大的问题分解成小的问题,以便通过现在…...

如何在Linux部署MeterSphere并实现公网访问进行远程测试工作
文章目录 前言1. 安装MeterSphere2. 本地访问MeterSphere3. 安装 cpolar内网穿透软件4. 配置MeterSphere公网访问地址5. 公网远程访问MeterSphere6. 固定MeterSphere公网地址 前言 MeterSphere 是一站式开源持续测试平台, 涵盖测试跟踪、接口测试、UI 测试和性能测试等功能&am…...

postgis导入shp数据时“dbf file (.dbf) can not be opened.“
作者进行矢量数据导入数据库中出现上述报错 导致报错原因 导入的shp文件路径太深导入的shp文件名称或路径中有中文将需要导入数据的shp 文件、dbf 文件、prj 等文件放在到同一个文件夹内,且名字要一致;导入失败: 导入成功:...

StarUML笔记之从C++代码生成UML图
StarUML笔记之从C代码生成UML图 —— 2024-04-14 文章目录 StarUML笔记之从C代码生成UML图1.安装C插件2.准备好一个C代码文件放某个路径下3.点击Reverse Code选择项目文件夹4.拖动(Class)到中间画面可以形成UML5.另外一种方式:双击Type Hierarchy,然后…...
sizeof()和strlen
一、什么是sizeof() sizeof()是一个在C和C中广泛使用的操作符,用于计算数据类型或变量所占内存的字节数。它返回一个size_t类型的值,表示其操作数所占的字节数。 在使用时,sizeof()可以接收一个数据类型作为参数,也可以接收一个…...

Python学习笔记13 - 元组
什么是元组 元组的创建方式 为什么要将元组设计为不可变序列? 元组的遍历...

[leetcode]remove-duplicates-from-sorted-list-ii
. - 力扣(LeetCode) 给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 示例 1: 输入:head [1,2,3,3,4,4,5] 输出:[1,2,5]示例 2&…...
共享内存和Pytorch中的Dataloader结合
dataloader中通常使用num_workers来指定多线程来进行数据的读取。可以使用共享内存进行加速。 代码地址:https://github.com/POSTECH-CVLab/point-transformer/blob/master/util/s3dis.py 文章目录 1. 共享内存和dataloader结合1.1 在init中把所有的data存储到共享内…...

分享 WebStorm 2024 激活的方案,支持JetBrains全家桶
大家好,欢迎来到金榜探云手! WebStorm公司简介 JetBrains 是一家专注于开发工具的软件公司,总部位于捷克。他们以提供强大的集成开发环境(IDE)而闻名,如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…...

Android OOM问题定位、内存优化
一、OOM out of memory:简称OOM,内存溢出,申请的内存大于剩余的内存而抛出的异常。 对于Android平台,广义的OOM主要是以下几种类型 JavaNativeThread 线程数的上限默认为32768,部分华为设备的限制是500通常1000左右…...
棋盘(c++题解)
题目描述 有一个m m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的) ,你只能向上、下、 左、右…...

滑动窗口例题
一、209:长度最小的子数组 209:长度最小的子数组 思路:1、暴力解法:两层for循环遍历,当sum > target时计算子数组长度并与result比较,取最小的更新result。提交但是超出了时间限制。 class Solution {public int minSubArray…...

智过网:注册安全工程师注册有效期与周期解析
在职业领域,各种专业资格认证不仅是对从业者专业能力的认可,也是保障行业安全、规范发展的重要手段。其中,注册安全工程师证书在安全生产领域具有举足轻重的地位。那么,注册安全工程师的注册有效期是多久呢?又是几年一…...

腐蚀Rust 服务端搭建架设个人社区服务器Windows教程
腐蚀Rust 服务端搭建架设个人社区服务器Windows教程 大家好我是艾西,一个做服务器租用的网络架构师也是游戏热爱者。最近在steam发现rust腐蚀自建的服务器以及玩家还是非常多的,那么作为服务器供应商对这商机肯定是不会放过的哈哈哈! 艾西这…...

蓝桥杯备赛:考前注意事项
考前注意事项 1、DevCpp添加c11支持 点击 工具 - 编译选项 中添加: -stdc112、万能头文件 #include <bits/stdc.h>万能头文件的缺陷:y1 变量 在<cmath>中用过了y1变量。 #include <bits/stdc.h> using namespace std;// 错误示例 …...
111111111111
111111111111...

uniapp 卡片勾选
前言 公司的app项目使用的uniapp,项目里有一个可勾选的卡片功能,效果图如下: 找了一圈没找到什么太好的组件,于是就自己简单写了一个,记录一下。避免以后还会用到 代码 <template><view class"card-…...

乐趣Python——文件与数据:挥别乱糟糟的桌面
各位朋友们,今天我们要开启一场非凡的冒险——进入文件操作的世界!你知道吗,在你的电脑里,有一个叫做“文件系统”的迷宫,里面藏着各种各样的文件和文件夹,它们就像是迷宫中的宝藏。但有时候,这…...
docker nginx-lua发送post json 请求
环境准备 dockerfile from fabiocicerchia/nginx-lua:1.25.3-ubuntu22.04 run apt-get -qq update && apt-get -qq install luarocks run luarocks install lua-cjson run luarocks install lua-iconv run luarocks install lua-resty-http后台代理服务准备ÿ…...

阿里面试总结 一
写了这些还是不够完整,阿里 字节 卷进去加班!奥利给 ThreadLocal 线程变量存放在当前线程变量中,线程上下文中,set将变量添加到threadLocals变量中 Thread类中定义了两个ThreadLocalMap类型变量threadLocals、inheritableThrea…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...