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.展开更多
By means of F[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given mul-tiple sequences over a field ...By means of F[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given mul-tiple sequences over a field F. Its computational complexity is O(N2) operations in F where N is the length of each sequence. A necessary and sufficient condition for the uniqueness of minimal polynomi-als is given. The set and exact number of all minimal polynomials are also described when F is a finite field.展开更多
基金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.
基金This work was supported by the National Natural Science Foundation of China (Grant Nos. 19931010, G1999035804).
文摘By means of F[x]-lattice basis reduction algorithm, a new algorithm is presented for synthesizing minimum length linear feedback shift registers (or minimal polynomials) for the given mul-tiple sequences over a field F. Its computational complexity is O(N2) operations in F where N is the length of each sequence. A necessary and sufficient condition for the uniqueness of minimal polynomi-als is given. The set and exact number of all minimal polynomials are also described when F is a finite field.
