A quantum algorithm for the dihedral hidden subgroup problem based on lattice basis reduction algorithm |
| |
Authors: | Fada Li Wansu Bao Xiangqun Fu |
| |
Affiliation: | 1. The PLA Information Engineering University, Zhengzhou, 450004, China 2. Synergetic Innovation Center of Quantum Information and Quantum Physics, University of Science and Technology of China, Hefei, 230026, China
|
| |
Abstract: | To optimize the algorithms for the dihedral hidden subgroup problem, we present a new algorithm based on lattice basis reduction algorithm. For n < 120, we reduce the dihedral hidden subgroup problem to shortest vector problem. A subroutine is given to get a transition quantum state by constructing a phase filter function, and then the measurement basis are derived based on the lattice basis reduction algorithm for solving low density subset sum problem. Finally, the parity of slope s is revealed by the measurement. This algorithm needs preparing mn quantum states, m qubits to store and O(n 2) classical space, which is superior to existing algorithms. |
| |
Keywords: | Quantum algorithm Dihedral hidden subgroup problem Lattice basis reduction algorithm |
本文献已被 CNKI 维普 SpringerLink 等数据库收录! |
|