量子科技中心_量科网

最近向量问题（CVP）是基于格密码学中的一项基本优化问题，其公认的计算难度构成了格基密码系统的安全基础。此外，Schnorr提出的基于格的因数分解算法将整数分解（包括RSA在内的现行密码系统基础）归结为CVP问题。近期研究探索了在格基因数分解算法中引入启发式CVP近似“精炼”步骤，利用量子变分算法执行这种启发式优化。与此同时，概率计算作为硬件加速器正崭露头角，适用于随机化算法中的组合优化任务。本工作研究了概率计算在格基因数分解的CVP近似精炼这一启发式优化任务中的应用。该研究团队提出了针对该任务的概率计算算法设计，探讨了“素格”参数特性，并通过实验证明概率计算不仅能有效求解CVP问题，还能作为格基因数分解子程序发挥效能。主要发现包括：（1）该方法能以问题规模线性时间找到当前最优的CVP近似精炼解；（2）结合特定格参数使用时，概率计算分解半素数合数因子所需的格实例数量比同类量子及经典方法减少高达100倍。