最前沿・量子退火建模方法(1) : subQUBO讲解和python实现

2024-04-14 14:36

本文主要是介绍最前沿・量子退火建模方法(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的创新点

  1. 首先研究将大规模组合优化问题划分为较小问题而不失去最优性的条件。该条件成立的话就证明,如果用伊辛机来解决一个满足条件的小问题,它就会和原来的大规模问题的答案相匹配。
  2. 还提出了一种新算法,成功地从大规模问题中提取出此类条件,将原始大规模问题缩小到伊辛机可以解决的问题规模,并迭代求解。所提出的算法通过基于理论支持将大规模问题分解为更小的问题来解决它,使得以比传统技术更高的精度解决原始大规模问题成为可能。
    在这里插入图片描述

二、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实现

  1. 导入库
import random
import itertools
import numpy as np
from dataclasses import dataclass
  1. 设置subQUBO所需参数
N_I = 20 # instance池
N_E = 10 # subQUBO的抽取次数
N_S = 10 # N_I个instance池中抽取的解的个数
sub_qubo_size = 5 # subQUBO的量子比特数
  1. 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
  1. 创建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
  1. 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实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903243

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操