量子全连接近似的分块反馈计算方法和装置与流程

摘要: 本发明创造涉及量子计算,特别是涉及量子全连接近似的分块反馈计算方法和装置。背景技术:1、伊辛机(isingmachine)是求解组合优化问题的专用计算架构,其核...
量子全连接近似的分块反馈计算方法和装置与流程

本发明创造涉及量子计算,特别是涉及量子全连接近似的分块反馈计算方法和装置。

背景技术:

1、伊辛机(ising machine)是求解组合优化问题的专用计算架构,其核心工作原理为:个自旋变量通过耦合矩阵(对称矩阵)相互作用,系统通过迭代演化搜索使伊辛哈密顿量最小化的自旋构型。在每次迭代中,反馈计算模块需执行矩阵-向量乘法:

2、

3、其中为第个自旋的测量结果。该计算的复杂度为,当自旋数较大时(如),计算延迟成为系统性能的主要瓶颈。

4、在相关技术中有以下几种方案来解决这个问题:

5、1、ntt 相干伊辛机方案:ntt 团队在 2016 年 science 论文中实现了 2000 自旋 cim,采用 fpga 进行全连接反馈计算。但随着自旋数增加到 10 万量级(2021 年),全连接计算延迟急剧增长,需要采用分时复用等策略,牺牲了实时性。

6、2、稀疏矩阵方法:部分工作将耦合矩阵限制为稀疏矩阵(仅保留部分非零元素),虽可降低计算复杂度至(为平均非零元素数),但这是对问题本身的限制,无法处理密集耦合的优化问题。

7、3、gpu 加速方案:使用 gpu 进行矩阵乘法计算虽然吞吐量高,但延迟难以满足伊辛机反馈回路的实时性要求(通常要求)。gpu 的 pcie 通信延迟()和内核启动开销()进一步恶化了总延迟。

8、4、已有 fpga 实现:2024 年已有团队实现单 fpga 全精度 cim 仿真,但全连接计算的延迟仍随增长,进一步扩展到时面临资源和延迟的双重限制。

9、也就是说,相关技术中没有一种既能保持近全连接的计算精度、又能将计算复杂度从显著降低的方法,且该方法需适配 fpga 硬件架构,满足伊辛机反馈回路的实时性要求。

10、现有伊辛机反馈回路中,为了解决计算延迟问题,虽然可以对耦合矩阵分块或者依据初始耦合强度聚类自旋,但分块方案在整个迭代求解过程中固定不变,自旋迭代过程中新形成的强耦合自旋对会分散到非对角子块中,被稀疏近似舍弃,误差不断累积,降低伊辛机寻优效果。

11、由此可知,相关技术中存在对耦合矩阵分块固定不变导致误差不断增大因而降低伊辛机寻优效果的问题。

12、针对相关技术中存在的上述问题,目前尚未提出有效的解决方案。

技术实现思路

1、本发明实施例提供了一种量子全连接近似的分块反馈计算方法和装置,以至少解决相关技术中存在对耦合矩阵分块固定不变导致误差不断增大因而降低伊辛机寻优效果的问题。

2、根据本发明的一个实施例,提供了一种量子全连接近似的分块反馈计算方法,用于伊辛机反馈回路中的耦合矩阵与自旋向量的乘法计算,包括:s1:将 n 个自旋变量对应的 n×n 耦合矩阵 j 划分为 m×m 个子块,每个子块的行数和列数均为 b,其中, m=n/b,m、n、b都 为大于 1 的整数,在划分所述耦合矩阵时,将耦合强度绝对值大于预设阈值的自旋对分配到同一子块内;s2:对 m 个对角子块分别执行完整的矩阵-向量乘法计算,获得各对角子块的子块内局部场分量;s3:对非对角子块中的耦合项,仅保留耦合强度绝对值超过阈值 θ 的耦合项,并基于所保留的耦合项执行稀疏矩阵-向量乘法计算,获得子块间局部场分量;s4:将所述子块内局部场分量与所述子块间局部场分量按自旋索引求和,得到每个自旋对应的反馈信号;s5:依据所述反馈信号更新所有自旋变量,完成一轮迭代求解;s6:循环执行步骤 s2~s5 完成多轮迭代,每经过预设迭代间隔,采用与步骤 s1 相同的分块尺寸与划分算法对所述耦合矩阵重新执行子块划分,更新子块配置。

3、进一步地,将 n 个自旋变量对应的 n×n 耦合矩阵 j 划分为 m×m 个子块包括:构造以耦合强度绝对值为边权重的加权图;对所述加权图执行 k-way 均衡图划分算法,将代表自旋变量的 n 个节点划分为 m 个节点数量均衡的节点簇,得到m×m 个子块,划分优化目标为簇间耦合边的权重绝对值之和最小化。

4、进一步地,保留耦合强度绝对值超过阈值 θ 的耦合项包括:针对每个非对角子块,统计当前非对角子块中所有耦合项绝对值的经验累积分布函数 f(x);设定保留比例参数ρ,其中 0<ρ<1;求解满足f(θ)=1ρ的阈值θ;对耦合项进行筛选,仅保留耦合强度绝对值大于θ、处于前 ρ 分位的耦合项,舍弃其余弱耦合项。

5、进一步地,对所述耦合矩阵重新执行子块划分的触发条件包括:定义划分后得到的每个子块在当前迭代时刻t的子块内部一致性指标,用于表征第k个子块内部全部自旋变量之间耦合关联的整体强弱程度,一致性指标的数值越大,对应子块内自旋耦合关联越强;计算全部子块的一致性指标的算术平均值或各子块规模加权求和值,得到全局一致性指标iglobal(t);当任意迭代时刻t满足iglobal(t)≤αi0时,对所述耦合矩阵重新执行子块划分,其中,α为预设的重划分敏感度参数, 0<α<1, i0为初次完成子块划分时对应的初始全局一致性指标。

6、进一步地,对每个子块,所述内部一致性指标通过以下方法计算得到:,其中,表示在最近轮迭代自旋状态平均值,为滑动窗口大小,,为第个子块对应的自旋索引集合,σi、σj分别为第i、第j个自旋变量。

7、进一步地,对所述耦合矩阵重新执行子块划分,更新子块配置包括:以当前迭代下的自旋相关性矩阵替代原始耦合强度∣jij∣作为图划分的边权重基准;以每一个自旋变量作为加权图的独立节点,节点i与节点j之间连接边的权重取∣cij∣,完成加权图重构;对重构得到的加权图执行 metis 多路均衡图划分算法,划分约束为:将全部节点划分为 m个节点规模均衡的节点簇,优化目标为最小化不同簇之间连接边的权重总和;各节点簇一一对应耦合矩阵划分后的自旋子块,基于划分得到的节点簇分配关系生成更新后的子块配置; 基于更新后的子块配置重建适配稀疏矩阵-向量乘法运算的子块间稀疏索引表, 其中,自旋相关性矩阵的矩阵元素满足,σi、σj分别为第i、第j个自旋变量。

8、进一步地,所述预设迭代间隔通过以下方式确定:获取连续多次重新执行子块划分时相邻两次子块划分结果中各自旋所属子块编号的变更比例,得到分区变化率;若连续l次重划分操作对应的分区变化率均小于预设下限δlow,将所述预设迭代间隔扩大一倍;若单次重划分操作对应的分区变化率大于预设上限δhigh,将所述预设迭代间隔缩小一半;其中,l为预设连续判定次数,0<δlow<δhigh<1,δlow、δhigh、l均由待求解伊辛问题的类型预先配置得到。

9、进一步地,子块行数与列数b的取值bopt由下式确定:,其中,bmin为满足预设最大近似误差约束的最小子块尺寸,表示向上取整运算;总计算延迟函数为:,式中,p为并行计算单元数量,tmac为单次乘累加运算耗时,tintra为子块内完整稠密计算延迟,随分块尺寸b增大单调递增;tinter为子块间稀疏耦合项计算延迟。

10、根据本发明的另一个实施例,提供了一种量子全连接近似的分块反馈计算装置,用于执行伊辛机反馈回路中的耦合矩阵与自旋向量的乘法计算,包括:划分单元,用于执行s1:将 n 个自旋变量对应的 n×n 耦合矩阵 j 划分为 m×m 个子块,每个子块的行数和列数均为 b,其中, m=n/b,m、n、b都 为大于 1 的整数,在划分所述耦合矩阵时,将耦合强度绝对值大于预设阈值的自旋对分配到同一子块内;计算单元,用于执行s2:对 m 个对角子块分别执行完整的矩阵-向量乘法计算,获得各对角子块的子块内局部场分量;乘法单元,用于执行s3:对非对角子块中的耦合项,仅保留耦合强度绝对值超过阈值 θ 的耦合项,并基于所保留的耦合项执行稀疏矩阵-向量乘法计算,获得子块间局部场分量;求和单元,用于执行s4:将所述子块内局部场分量与所述子块间局部场分量按自旋索引求和,得到每个自旋对应的反馈信号;求解单元,用于执行s5:依据所述反馈信号更新所有自旋变量,完成一轮迭代求解;更新单元,用于执行s6:循环执行步骤 s2~s5 完成多轮迭代,每经过预设迭代间隔,采用与步骤 s1 相同的分块尺寸与划分算法对所述耦合矩阵重新执行子块划分,更新子块配置。

11、根据本发明的又一个实施例,还提供了一种计算机可读存储介质,所述计算机可读存储介质中存储有计算机程序,其中,所述计算机程序被设置为运行时执行上述任一项方法实施例中的步骤。

12、根据本发明的又一个实施例,还提供了一种电子装置,包括存储器和处理器,所述存储器中存储有计算机程序,所述处理器被设置为运行所述计算机程序以执行上述任一项方法实施例中的步骤。

13、通过本发明,s1:将 n 个自旋变量对应的 n×n 耦合矩阵 j 划分为 m×m 个子块,每个子块的行数和列数均为 b,其中, m=n/b,m、n、b都 为大于 1 的整数,在划分耦合矩阵时,将耦合强度绝对值大于预设阈值的自旋对分配到同一子块内;s2:对 m 个对角子块分别执行完整的矩阵-向量乘法计算,获得各对角子块的子块内局部场分量;s3:对非对角子块中的耦合项,仅保留耦合强度绝对值超过阈值 θ 的耦合项,并基于所保留的耦合项执行稀疏矩阵-向量乘法计算,获得子块间局部场分量;s4:将子块内局部场分量与子块间局部场分量按自旋索引求和,得到每个自旋对应的反馈信号;s5:依据反馈信号更新所有自旋变量,完成一轮迭代求解;s6:循环执行步骤 s2~s5 完成多轮迭代,每经过预设迭代间隔,采用与步骤 s1 相同的分块尺寸与划分算法对耦合矩阵重新执行子块划分,更新子块配置。因此,可以解决相关技术中存在的对耦合矩阵分块固定不变导致误差不断增大因而降低伊辛机寻优效果的问题,达到动态调整分块进而提高伊辛机计算准确度的效果。