一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法及系统

摘要: 本发明属于量子密码与量子电路优化,特别涉及一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法及系统。背景技术:1、随着量子计算技术的飞速发展,基于sho...
一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法及系统

本发明属于量子密码与量子电路优化,特别涉及一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法及系统。

背景技术:

1、随着量子计算技术的飞速发展,基于shor算法和grover算法的量子攻击对传统密码体系的安全性构成了实质性威胁。对于对称密码而言,在grover量子攻击模型下,其安全强度不再单纯依赖于密钥长度,而与其量子实现所需的资源(包括量子比特数、量子门数量和电路深度)密切相关。因此,尽可能降低密码算法的量子实现资源消耗,已成为后量子密码安全性评估的重要研究方向。

2、轻量级分组密码因其低功耗、低面积和高效率的特点,被广泛应用于物联网、射频识别等资源极度受限的环境。典型算法包括aes、prince、midori以及present等。然而,在量子计算模型下实现上述密码算法时,线性扩散层通常需要转换为cnot门网络,因而仍面临若干关键瓶颈:

3、(1)线性层量子实现成本高

4、轻量级分组密码通常包含一个线性扩散层,该层在量子电路中需通过由cnot门构成的线性网络实现。传统的线性层综合方法,如标准高斯消元法或lu分解,仅能保证线性变换的逻辑正确性,却完全不考虑中间矩阵行的汉明重量优化,由此产生大量冗余cnot门,造成量子资源严重浪费。此外,诸如boyar-peralta(bp)算法等启发式方法虽然能在一定程度上减少门数,但其基于局部等价变换的搜索策略缺乏全局汉明重量视野,难以彻底消除线性层中的结构冗余。具体而言,bp算法依赖于一组预定义的局部变换规则库,在有限的搜索窗口内进行门替换与消除,这种方式对于具有全局结构性冗余的矩阵,尤其是在矩阵密度较高时,优化效果显著下降。

5、(2)量子电路深度较大

6、现有量子密码实现普遍采用逐轮串行执行策略,即每一轮的替换层、线性层和密钥加操作完全结束后,再启动下一轮计算。这种强顺序依赖一方面导致电路深度随轮数线性累积,另一方面使得大量量子比特在每一轮内部存在空闲等待时段,形成所谓的时间“气泡”。过大的电路深度直接导致量子退相干影响加剧,严重限制了其在含噪声中等规模量子(nisq)设备上的可行性与保真度。在nisq时代,量子比特的相干时间是极其宝贵的资源,任何不必要的空闲等待都意味着信息丢失风险的急剧增加。

7、(3)门数量与深度缺乏协同优化

8、已有研究主要集中在单一维度的优化,例如通过矩阵分解减少cnot门数,或者利用cnot门的交换性进行局部门重排序以降低深度。然而,这些方法将非线性替换层与线性扩散层视为相互隔离的模块,忽略了跨算子、跨轮次的全局并行潜力。特别地,现有方法未能在矩阵综合阶段就考虑到后续并行调度的需求,导致优化结果在门数和深度两个指标上难以兼得。因此,本领域缺少一个同时将门数量、电路深度和并行度纳入统一框架的协同优化机制。

9、即使将现有的门数优化方法与普通门重排序方法顺序组合,也只能得到“先减少门数、再在单轮内部局部并行”的结果,仍然无法突破密码轮函数之间的同步边界,不能解决相邻轮之间量子比特空闲时间无法利用的问题。

10、因此,亟需提出一种能够同时大幅减少cnot门数目、极致压缩电路深度并充分挖掘并行执行能力的新型量子电路优化方法。

技术实现思路

1、本发明技术方案以克服现有技术中存在的量子门数量多、电路深度大以及并行性不足的缺陷,整体上采取“贪心线性层综合—门级依赖重排序—跨轮融合调度”的三级递进优化框架,实现门级与系统级的联合优化,从而为对称密码的量子资源评估提供一套高效、可扩展且硬件友好的解决方案。

2、本发明提供的技术方案如下:

3、第一方面,一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法,包括:

4、步骤一:线性层建模,将轻量级分组密码的线性扩散层表示为域上的可逆矩阵m;

5、步骤二:贪心门数优化,对可逆矩阵m任意两行进行异或操作的结果,根据行的异或操作结果对应的行的汉明重量,采用贪心算法进行cnot量子门操作,更新可逆矩阵m,优化量子门序列;

6、步骤三:依据量子门序列构建量子门依赖关系图,以量子门为节点,量子门之间的执行依赖关系表示量子门之间的边;

7、步骤四:门级并行调度,依据量子门依赖关系图,将不存在依赖关系的量子门调度至同一并行执行层;

8、步骤五:跨轮融合调度;

9、检测当前轮执行过程中产生的量子比特空闲时隙,并在满足量子比特可用性和数据依赖约束的条件下,将下一轮量子门插入所述量子比特空闲时隙,使得相邻轮量子门的重叠执行;

10、步骤六:根据量子门执行结果生成优化量子电路。

11、优化后的量子电路结构,包括门序列、并行分层信息及跨轮调度结果。

12、进一步的,所述采用贪心算法进行cont量子门操作,优化量子门序列的具体过程如下:

13、定义为可逆矩阵m中第i行的汉明重量;对可逆矩阵m中任意两个不同的行和,计算;若满足,则执行将可逆矩阵m中的第j行更新为的行变换,并将对应的cnot门操作cnot(i,j)记录到门序列g中,其中i为控制比特索引,j为目标比特索引;重复上述扫描与更新过程,直至遍历所有行对后,无法再找到任何能够降低目标行汉明重量的行变换为止。

14、即矩阵整体汉明重量达到贪婪意义下的局部极小值。

15、进一步的,所述不存在依赖关系的量子门是指对量子门序列中任意两个量子门和的控制量子比特和目标量子比特互不冲突,即满足:

16、;

17、其中,和表示量子门和的控制量子比特,和表示量子门和的目标量子比特,表示空集。

18、进一步的,步骤四中采用基于拓扑排序的层划分算法将不存在依赖关系的量子门分组到并行的执行层中,具体过程如下:

19、首先将所有无前驱依赖且不存在量子比特资源冲突的量子门划分至第一并行执行层;将所述第一并行执行层中的量子门从量子门依赖关系图中移除后,再将新产生的无前驱依赖量子门划分至下一并行执行层;重复上述过程,直至所有量子门均被分配至对应执行层。

20、令最终所得的层数为l,则单轮线性层经并行调度后的原始电路深度draw=l。此步骤在不改变逻辑功能的前提下,通过交换性和并行性开发,显著缩短了线性层的执行时间跨步。

21、进一步的,步骤五中所述量子比特可用性和数据依赖约束的条件是指:

22、第一,下一轮待插入操作所作用的全部量子比特在当前时刻均处于可用状态,即所作用的量子比特的t(q)不大于当前可调度时刻;

23、第二,所述待插入操作的量子比特对应的量子门所依赖的前序操作已经完成,且不会改变密码轮函数的逻辑输入输出关系;

24、其中,t(q)表示量子比特q变得可用的最早时间;

25、;

26、其中,表示量子比特对和对应的量子门可用的最早时间,和分别表示量子比特和可用的最早时间。

27、第二方面,一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化系统,包括:

28、线性层建模单元,将轻量级分组密码的线性扩散层表示为域上的可逆矩阵m;

29、贪心门数优化单元,对可逆矩阵m任意两行进行异或操作的结果,根据异或操作结果对应的汉明重量,采用贪心算法进行cnot量子门操作,优化量子门序列;

30、量子门依赖关系图构建单元,对量子门序列构建量子门依赖关系图,以量子门为节点,量子门之间的执行依赖关系表示量子门之间的边;

31、门级并行调度单元,依据量子门依赖关系图,将不存在依赖关系的量子门调度至同一并行执行层;

32、跨轮融合调度单元,检测当前轮执行过程中产生的量子比特空闲时隙,并在满足量子比特可用性和数据依赖约束的条件下,将下一轮量子门插入所述空闲时隙,使得相邻轮量子门的重叠执行;

33、量子电路生成单元,根据量子门执行结果生成优化量子电路。

34、进一步的,所述门级并行调度单元中,不存在依赖关系的量子门是指对量子门序列中任意两个量子门和的控制量子比特和目标量子比特互不冲突,即满足:

35、;

36、其中,和表示量子门和的控制量子比特,和表示量子门和的目标量子比特,表示空集。

37、第三方面,一种计算机设备,包括:

38、一个或多个处理器;

39、存储器,用于存储一个或多个计算机程序;

40、当所述一个或多个计算机程序被所述一个或多个处理器执行时,使得所述设备实现如所述一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法的步骤。

41、第四方面,一种计算机可读存储介质,其上存储有计算机程序,其特征在于:该程序被处理器执行时实现如所述一种基于门级约减与跨轮融合的轻量级分组密码量子电路优化方法的步骤。

42、与现有技术相比,本发明技术方案具有如下优点:

43、(1)cnot门数量显著减少。通过全局贪心权重约减机制,显式最小化矩阵中间行的汉明重量,能够从根本上消除线性层中的逻辑冗余。实验数据表明,相较当前最先进的bp启发式算法,本发明技术方案在8×8矩阵上可将cnot门数由80.00降至14.60,降幅高达81.75%;在16×16和32×32矩阵上,降幅也分别达到72.50%和54.56%。在与标准高斯消元法的对比中,优势同样极为显著。更为重要的是,对于aes-128的mixcolumns操作,本发明技术方案仅用36个cnot门即完成综合,而prince的mhat矩阵仅需34个cnot门,midori线性层则维持在极为精简的48个cnot门,均达到了实用级别的极低门数。

44、(2)电路深度极大压缩。传统bp算法生成的电路深度极为庞大,在8×8矩阵上即高达70.00层,表现出严重的顺序依赖性。本发明通过“贪心综合+门级重排序+跨轮融合”的三级递进优化,可将8×8矩阵的最终深度压缩至4.20层,压缩比高达94.00%;对于16×16和32×32矩阵,压缩率分别维持91.81%和89.85%。在真实密码案例中,prince电路深度由10降至7,midori由24降至18,aes-128电路深度稳定在8。这种深度上的量级式缩减,对于降低退相干影响、提升nisq设备上的计算保真度具有决定性作用。

45、(3)并行执行能力大幅提升。通过构建门依赖有向无环图并实施基于资源冲突检测的分层调度,无冲突的cnot门被最大化地归并至同一时间槽内并行执行,单轮内部的并行度显著增加,关键路径得到有效缩短。再结合跨轮融合调度,轮间操作重叠程度进一步加深,整体并行性达到传统串行实现所无法企及的水平。此外,并行度的提升还意味着电路在量子处理器上的映射更为灵活,有助于降低因量子比特间有限的连通性而引入的额外swap门开销。

46、(4)强量子硬件适配性。电路深度和门数量的双重缩减,直接意味着更少的门误差累积和更短的退相干暴露时间,从而使得优化后的量子电路更加契合当前含噪声中等规模量子设备的物理约束。在qiskit0.44.0平台上对所有真实密码矩阵的仿真验证表明,理论优化数据与量子软件栈的实际输出完全一致,证明了方法的硬件可实现性。

47、(5)通用性、可扩展性与鲁棒性兼备。本发明技术方案所提的方法和系统不依赖于特定密码算法的结构特征,适用于任何以gf(2)矩阵形式表达的线性扩散层,已覆盖aes、prince、midori、present等主流轻量级分组密码。同时,方法的时间复杂度为多项式级别,能够平稳扩展至32×32乃至更大规模的矩阵,且不会遭遇smt/sat等整数规划方法所面临的状态空间爆炸问题。在多轮随机矩阵测试中,性能指标保持高度稳定,体现出良好的统计鲁棒性。

48、(6)填补了门数与深度协同优化的空白。现有技术多聚焦于门数或深度的单一目标优化,而本发明将两者纳入统一的贪心综合与跨轮融合框架,首次在轻量级密码量子实现领域,同时实现cnot门数量削减和电路深度压缩的协同最优,弥补了现有合成策略的重大缺陷。