A quantum algorithm for the dihedral hidden subgroup problem based on algorithm SV

Fada Li, Wansu Bao, Xiangqun Fu

Published 2013-05-16, updated 2013-05-29Version 2

To accelerate the algorithms for the dihedral hidden subgroup problem, we present a new algorithm based on algorithm SV(shortest vector). A subroutine is given to get a transition quantum state by constructing a phase filter function, then the measurement basis are derived based on the technique for solving low density subset problem. Finally, the parity of slope is revealed by the measurements on the transition quantum state. This algorithm takes O(n) quantum space and O(n^2) classical space, which is superior to existing algorithms, for a relatively small n(n<6400),it takes (n^0.5)*(log(max aij))^3 computation time, which is superior to 2^(O(n^0.5)).