基于Grover量子搜索算法的MD5碰撞攻击模型

量子计算天然的并行性使其在密码学领域具有巨大潜力,而在信息安全领域,Hash函数的安全性至关重要。因此,后量子密码学概念的提出使得Hash函数在后量子时代的研究价值凸显。文章提出了一种基于Grover量子搜索算法的MD5碰撞攻击模型,运用模差分分析法,通过对输入的量子叠加态进行约束搜索以找到满足碰撞条件的目标态,再根据差分构造出与之相碰撞的消息。此外,文章探讨了量子搜索算法中的迭代过程及其关键操作,设计了相应的Oracle黑盒的量子线路,并对其进行性能分析,结果表明,与经典算法相比,该模型显著降低了攻击的计算复杂度,为后量子密码时期Hash函数的研究提供了新的思路和方法,也为防御此类攻击提供了有益参考。

Grover量子搜索算法在“嵩山”超级计算机系统中的模拟

量子计算凭借其叠加性和纠缠性,具有强大的并行计算能力。然而,目前的量子计算机不能在保证大规模量子比特处于稳定叠加态的同时,进行干涉、纠缠等量子操作。因此,当前研究和推动量子计算的有效途径是使用经典计算机模拟量子计算。Grover量子搜索算法针对无序数据库搜索问题设计,将搜索的时间复杂度加速至开平方级,能加速机器学习中的主成分分析。因此,研究和模拟Grover算法,可以促进量子计算与机器学习结合领域的发展,为Grover量子搜索算法的应用以及量子机器学习在“嵩山”超级计算机系统中的模拟奠定基础。通过研究Grover量子搜索算法,模拟出了算法的量子线路。使用Toffoli量子门优化该量子线路,在减少了两个辅助量子比特的同时,提出了Grover算法的通用量子线路。实验基于“嵩山”超级计算机系统的CPU+DCU异构体系,使用了MPI多进程+HIP多线程的两级并行策略。通过调整辅助比特在量子线路中的位置,减少了MPI进程间的通信;使用分片的方式传输数据依赖的量子态。对比串行版本,并行化的模拟算法取得了最高560.33倍的加速,首次实现了31qubits规模的Grover量子搜索算法。

基于Grover硬币算子的量子行走在商图上的演化算子

商图是利用图的对称性分析量子行走算法的一种重要数学工具.量子行走在商图上的演化算子由移位算子和硬币算子构成.本文以构造的方式给出了Grover硬币算子在超立方体的商图上对应的矩阵形式,并给出了其正确性证明.由于商图上的移位算子可由原图上的移位算子直接导出,从而确定了使用Grover算子作为硬币的量子行走在商图上的演化算子.

基于混淆S盒的高维量子同态加密机制

在量子同态加密机制中,对密文量子态执行同态评估计算并解密得到的结果与对明文量子态直接评估计算所得的结果相同.现有的量子同态加密机制不仅评估算子的逻辑门种类有限,而且使用单点或多点混淆导致计算开销较大.鉴于此,本文使用量子随机游走构建了一个混淆S盒并将其应用到高维量子同态加密机制的设计之中.客户端使用高维的Pauli算子对明文量子态加密之后,将密文量子态发送至服务器;服务器从评估算子集合中选取客户端需要的评估算子,配合评估参数对密文量子态执行评估操作,并将评估结果发送至解密方执行解密运算.为了避免服务器在执行评估操作时泄露解密密钥,客户端通过设计的混淆S盒来完成对解密密钥的混淆并将结果传输给解密方.解密方执行逆混淆S盒还原出解密密钥,并使用该密钥执行解密操作得到委托计算结果.对比同类型的相似机制,该机制增加了评估算子的种类,降低了量子混淆S盒的开销;通过仿真实验结果证明了提出机制的正确性,并从信息理论层面证明了该机制的安全性.

量子行走搜索算法中硬币算子作用分析

为研究基于不同标记硬币算子的搜索算法的性能,分别使用负的恒等算子I、Grover扩散算子D和量子Fourier变换算子F作为标记算子构造基于算子-I、-D和-F的搜索算法(SAI、SAD和SAF),采用数值仿真研究其在对称图和随机图上搜索多个目标时的性能,分析SAI和SAD在一步量子行走中的作用,并使用不重复量子行走研究Cayley树根节点上的状态转移情况.结果表明,SAI的成功概率曲线近似为正弦函数平方曲线,并且在稠密图上成功概率大于0.5;SAD在搜索多个不相邻目标时等价于SAI,而在搜索Johnson图和随机图上的混合顶点时成功概率曲线出现双峰;SAF搜索相邻顶点时的性能取决于目标顶点硬币空间的基中各向量的顺序.在迭代数为g的4-Cayley树上实现了根节点状态在2g步的周期性转移.

Grover量子搜索算法的线路优化

Grover算法是能够高效查找到目标态的量子搜索算法,但随着搜索数据量的增大,它的量子线路面临着复杂的门分解问题。在如今的NISQ时代资源非常有限,因此线路的深度成为一种重要的度量标准。介绍了一种基于分治思想的二阶段量子搜索算法,能够在量子计算机上快速地并行运行。提出一种线路优化方法,应用块级的Oracle线路来减少迭代次数。将该方法与分治思想相结合,提出2P-Grover算法。在量子计算框架Cirq上进行模拟实验,与Grover算法进行对比。实验结果表明,2P-Grover算法能够使线路的深度至少减少60%,并且保持了较高的搜索成功率。

量子力学之波动力学(上)

量子力学之波动力学形式是由奥地利人薛定谔构造的(瑞士苏黎世,1926),其思想基础包括物质波理论、理想气-体(Gaskörper)量子化以及矩阵理论,波函数的概率幅诠释则归于德国人玻恩(德国哥廷恩,1926)。薛定谔创立波动力学的论文分四部分共140页,其题目“Quantisierung als Eigenwertproblem”(量子化作为本征值问题)内藏玄机,不仅可见其与线的代数和矩阵(力学)的关系,自其引出希尔伯特空间、能带理论以及光子晶体等概念也在情理之中。波动力学求解稳态问题时将量子力学退化为经典的数学物理方程问题,这也是它迅速被接受的原因。不妨说,波动力学是滤掉了量子思想的量子力学。薛定谔的论文问世后,玻恩、约当、狄拉克、泡利、冯·诺伊曼和福克等人迅速跟进发展了波动力学。

量子均值估计算法研究进展

随机变量的均值估计问题一直是经典数据分析中研究的热点,均值估计算法的目的是通过对随机变量尽可能少地采样从而获得尽可能准确的均值估计值。量子计算作为一项革命性的技术,在一些问题上具有超越经典计算的优势。量子算法在均值估计问题上相对于经典算法具有平方加速,展现了量子计算的优越性。该文系统梳理了量子均值估计算法的发展历程,详细介绍了各阶段的算法流程及其优缺点,并对其主要应用场景进行了展示,最后讨论了量子均值估计算法的潜在发展方向。

量子计算模型下PFP算法的安全性分析

量子技术的快速发展和量子计算效率的不断提高,以及Shor算法和Grover算法的出现,给传统公钥密码和对称密码的安全性造成了较大威胁。因此,基于Feistel结构设计的分组密码PFP算法,首先将轮函数的线性变换P融入Feistel结构的周期函数构造,推导得到PFP算法的4个5轮周期函数,比选择明文攻击模型下典型Feistel结构的周期函数多2轮,并通过实验验证正确性;进一步地,以其中一个5轮周期函数作为区分器,结合量子Grover算法和Simon算法,通过分析PFP密钥编排算法的特点对9、10轮PFP进行了安全性评估,得到正确密钥比特需要的时间复杂度为2^(26)、2^(38.5),需要的量子资源为193、212个量子比特,可以恢复58、77比特密钥,优于已有不可能差分分析结果。

ACCQPSO:一种改进的量子粒子群优化算法及其应用

针对量子粒子群优化算法前期易陷入局部极值点、后期寻优精度不高等问题,文章提出一种自适应交叉算子的混沌量子粒子群优化算法,并将其应用于BP神经网络超参数寻优。首先,利用Logistics映射初始种群为混沌序列进行最优解搜索,增强初始种群的随机性与遍历性,提高算法寻优能力;然后,通过纵向交叉操作进行种群中个体的信息交换,并引入自适应交叉概率公式,增加种群多样性,提高算法的寻优精度;最后,在实验中,一方面,选取8个函数在高低两个维度进行验证,同时进行Wilcoxon秩和检验分析以及消融实验,验证该算法相较其他算法的有效性;另一方面,通过算法优化BP神经网络应用到网络安全态势预测任务中,实验结果表明该算法收敛速度相较于对比算法有大幅度提升。

改进的KLEIN算法及其量子分析

KLEIN自提出之后经历了截断差分分析、积分分析等攻击,加密结构具有实际安全性,但是由于密钥扩展算法的脆弱性导致了全轮密钥恢复攻击。首先,修改密钥扩展算法,提出一种改进后的算法N-KLEIN;其次,采用in-place方法对S盒进行高效量子电路实现,减小了电路的宽度和深度,提高了量子电路的实现效率;再次,使用LUP分解技术实现混淆操作的量子化;继次,对N-KLEIN进行量子电路设计,提出全轮N-KLEIN的高效量子电路。最后,评估N-KLEIN算法量子实现的资源占用,并与PRESENT、HIGHT等现有的轻量级分组密码的量子实现占用资源进行对比;同时,基于Grover算法对密钥搜索攻击所需要的代价进行深入研究,给出Clifford+T模型下N-KLEIN-{64,80,96}使用Grover算法搜索密钥需要的代价,并评估了N-KLEIN的量子安全性。对比结果表明,N-KLEIN算法量子实现的成本明显较低。

幂计数算子的表示

讨论平方可积Bernoulli泛函空间L^(2)(M)上幂计数算子a^(N)的表示问题,a是任意非负实数.得到4种表示方法:a^(N)的谱表示,a^(N)以{an;n≥0}为其特征值,a^(N)的特征向量全体构成L^(2)(M)的一组标准正交基,当a=2时,2^(N)可用■-QNBs的异型等时混合积算子级数表示;关于L^(2)(M)的标准正交基的表示;利用真空态Zϕ以及■-QNBs,给出a^(N)的■-QNBs-真空态表示;利用一列特殊的■-QNBs,给出a^(N)的极限表示.考虑a^(N)与■-QNBs等时混合积复合后特征根与特征子空间均会随复合顺序发生变化.

一种求解图分割问题的量子近似优化算法

量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)是求解组合优化问题的算法框架,是近期最有可能展示量子计算优势的算法之一.在QAOA框架内,表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性,本文受Dicke态制备算法的启发,给出了一种新的解编码方案,消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图(Star Graph,SG)算子,及其对应的SG算法,给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示,星图算法比标准QAO算法平均约有25.3%的性能提升.

n 次中心对称量子图的可约性

本文根据群的不可约表示给出了 n 次中心对称量子图上平方可积函数空间的分解及 n 次中心对称 量子图的商图,为量子图久期行列式的分解提供了新的思路,将原量子图的谱问题转化为商图的 谱问题,为等谱量子图的研究打下基础。

量子自组织特征映射神经网络

自组织特征映射是典型的无监督神经网络算法。它运用竞争学习策略实现数据分类。然而当网络中神经元个数为多项式时,自组织特征映射算法训练容易受到计算力挑战。为了降低算法训练的时间复杂度,本文提出了一个量子经典混合的自组织特征映射神经网络算法,利用量子叠加性和量子纠缠性对经典算法进行加速。在神经网络训练过程中,算法利用量子相位估计和Grover搜索算法并行实现相似度计算和标签提取。理论分析表明,本文提出的量子算法相比于经典算法在数据维度上具有指数加速。

Grover量子搜索算法及改进

简单地介绍了量子搜索算法中的相位匹配条件、改进的成功率为 10 0 %的量子搜索算法和量子搜索算法中的主要误差等 .

一种改进的Grover量子搜索算法

Grover量子搜索算法以O(N^(1/2))的时间复杂度进行非结构化数据库穷举搜索,但当问题的解的个数增加,得到解的概率反而减少.本文分析了这种现象的原因,并提出了基于扩大搜索空间的改进算法.同时,为了在成功概率与迭代次数之间折中,增加一个新参数i使得算法可调。求逆问题的仿真实验表明该方法在同等迭代次数的条件下,成功概率高于传统Grover算法;且如果迭代次数不限,则成功概率可以更高。因此,本文算法更加有效。

带交叉算子的量子粒子群优化算法

为了改善量子粒子群优化(QPSO)算法、提高其求解多峰优化问题的能力,采用新的粒子吸引点和势阱特征长度计算方法,引入遗传算法中的交叉算子并融入交叉概率自适应的参数控制技术,设计了一种带交叉算子的量子粒子群优化(CQPSO)算法.CQPSO算法既可确保QPSO粒子群体的多样性、维护粒子整体的活力性,又能克服特殊情况下QPSO算法收敛的不稳定性和陷入局部最优的偶发性.实验结果表明,在21个标准测试函数中,无论对应单峰函数、多峰函数或是偏移、旋转函数,在相同的物理仿真平台上,CQPSO算法的性能在绝大多数情况下都优于其他改进的量子粒子群算法,从而验证了CQPSO算法的有效性和鲁棒性.

量子Grover算法及其在遍历搜寻中的应用

介绍了量子Grover 算法的原理与实现,以及它在遍历搜寻问题中的应用;

无线自组织量子通信网络的Grover路由算法研究

介绍了无线量子通信网络的发展和无线量子通信网络中的路由算法.路由度量基于相邻节点间的纠缠量子对数目.结合Grover量子搜索算法,在限定跳数内搜索路由度量最大的路径作为目标解径,以避免量子信道因纠缠量子对的消耗而断开.路径搜索成功后,节点采用两端逼近的方法建立起量子信道,实现从源节点到目的节点的量子态的传递.采用Grover算法的路由搜索保证了成功率,降低了量子通信网络的网络计算量,使路由搜索快速收敛.