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 pro...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(n2)classical space,which is superior to existing algorithms.展开更多
基金supported by a grant from the Major State Basic Research Development Program of China (973 Program) (2013CB338002)
文摘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(n2)classical space,which is superior to existing algorithms.
