具体分析

量子格枚举的具体分析？

摘要：格约化算法（例如 BKZ（Block-Korkine-Zolotarev））在评估基于格的密码学的安全性方面起着核心作用。BKZ 中用于查找投影子格中最短向量的子程序可以用枚举算法实例化。枚举过程可以看作是在某些枚举树上的深度优先搜索，枚举树的节点表示系数的部分分配，对应于格点，即格基与系数的线性组合。这项工作基于 Montanaro 的量子树回溯算法，对量子格枚举的成本进行了具体的分析。更准确地说，我们在量子电路模型中给出了具体的实现。我们还展示了如何通过并行化组件来优化电路深度。基于设计的电路，我们讨论了格枚举所需的具体量子资源估计。