# The hidden subgroup problem for ℤ for infinite-index subgroups

Shor's algorithm, later generalized by Kitaev, is an algorithm to solve the hidden subgroup problem in $ℤ^K$ in quantum polynomial time, uniformly in all parameter, when the hidden subgroup H has finite index. Explicitly, that algorithm takes as functional input a function f: $ℤ^K$ → S, where S is an unstructured set. The function f has the property that f(x) = f(y) if and only if x-y ∈ H for a hidden subgroup H, and it must itself have a fast algorithm; the Shor-Kitaev algorithm then uses f to calculate H. It is sometimes stated explicitly that H is a finite-index subgroup, or equivalently has maximal rank k; and sometimes only implicit from the condition that S is a finite set. I will present a generalized algorithm that can find H in quantum polynomial time even when H has infinite index or some lower rank. The generalization requires a clear picture of the statistics of the quantum Fourier measurement in this case, and then use of the LLL algorithm to recover H from Fourier samples