基于量子克隆的二面体群隐含子群问题量子算法的研究

Quantum Cloning-based Quantum Algorithm for Dihedral Hidden Subgroup Problem

基于最短向量问题的格公钥密码体制是典型的抗量子计算密码体制。格的唯一最短向量问题可转化为二面体群的隐含子群问题。有效地求解二面体群的隐含子群问题可攻破基于格的唯一最短向量问题的公钥密码体制。Kuperberg提出了二面体群隐含子群问题的半指数级量子算法。通过研究Kuperberg量子算法,利用概率量子克隆,文中提出了二面体群隐含子群问题的多项式时间量子算法。

Kuperberg presented a quantum algorithm for the dihedral hidden subgroup problem,but with sub-exponen- tial time and query complexity. We presented a quantum cloning-based quantum algorithm for dihedral hidden subgroup problem with polynomial time and query complexity. Dihedral hidden subgroup problem is related to poly（n）-unique shortest vector problem. If the dihedral hidden subgroup problem is solved efficiently, the lattice-based cryptography can be breaken,which is secure against quantum computers.