= Solution
The <hidden subgroup problem> supplies an oracle $f:G\to X$ promised to satisfy
$$
f(g_1)=f(g_2)\quad\Longleftrightarrow\quad g_1H=g_2H
$$
for an unknown subgroup $H\leq G$; the task is to determine $H$.
For a function $f:\mathbb Z_K\to\mathbb Z$ with least period $r$ dividing $K$, use the additive group $G=\mathbb Z_K$ and hidden subgroup
$$
\boxed{H=\langle r\rangle
=\{0,r,2r,\ldots,K-r\}}.
$$
Its cosets are the residue classes modulo $r$. Periodicity makes $f$ constant on each coset, while injectivity within a period makes values on distinct cosets different. Determining $H$, or its least positive generator $r$, is exactly <quantum period finding>.
Back to article page
