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

The hidden subgroup problem is to recover a subgroup $K\le G$, usually by giving generators of a group, from an oracle machine providing $f:G\to Y$ with the promiseThus $f$ is constant on each left coset and distinguishes different left cosets. The input includes an effective representation of elements of the group and access to the group operations; the desired efficiency is measured against the number of bits describing an element, rather than necessarily against $|G|$.