= Solution
The <hidden subgroup problem> is to recover a <subgroup> $K\leq G$, usually by giving <generators of a group>, from an <oracle machine> providing $f:G\to Y$ with the promise
$$
\boxed{f(g)=f(h)\iff gK=hK.}
$$
Thus $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|$.
Back to article page
