Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 324 / 1 / a / Solution

The hidden subgroup problem supplies an oracle $f:G\to X$ promised to satisfyfor an unknown subgroup $H\le 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 subgroupIts 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.