量子科技中心_量科网

整数分解问题（IFP）是RSA加密安全性的基础，但通过Shor算法可在量子计算机上高效求解。Regev近期提出的高维变体算法虽通过基于格的后处理减少了电路规模，却引入了巨大的空间开销且缺乏实际实现。该团队受可逆计算启发，提出一种“中间非计算”的量子比特复用方法，显著降低了Regev算法的空间复杂度。基础策略将成本从O(n^3/2)降至O(n^5/4)，优化策略更达到O(n log n)——这是该模型下的空间复杂度下限。仿真实验展示了所得的时间-空间权衡与资源缩放规律。此外，研究人员构建并编译了分解N=35的量子电路，通过含噪声仿真验证了方法的有效性。一个更简化的Regev算法实验电路在超导量子计算机上执行，基于格的后处理成功还原了因数。这些成果推进了Regev型量子因数分解的实用化进程，为未来理论与实验发展提供了指引。