Let $(G,+)$ be an **abelian** group, $X$ a finite set (of "colors"), and $f:G to X$ a function such that there exists a subgroup $H<G$ for which $f$ **separates** cosets of $H$, i.e. $forall a,bin G:f(a)=f(b)iff a+H=b+H$.

Using information gained from evaluations of $f$, determine a generating set for $H$.

This is the **hidden subgroup problem**, that is solved in abelian groups using a quantum polynomial time algorithm.

In many cases $f$ is actually an homomorphism. So, in fact, the subgroup $H$ corresponds to $text{Ker}(f)$.

For example, this is true in the cases of factoring, i.e. Shor’s algorithm and also in the discrete log problem.

More generally, I am interested in the cases where the oracle $f$ is some sort of "homomorphism", i.e. we have some mapping $M:Xtimes Xto X$ such that $forall a,bin G:M(f(a),f(b))=f(a+b)$ (note that when $f$ is an homomorphism $(x,y)overset{M}{mapsto} xcdot_Xy$).

Clearly such $M$ always exists, by going through group $G$ using representaitves from coset in $f^{-1}$. So, what is really interesting, even when restricting to the abelian case, is can we always find such $M$ classically and efficiently. Also, is that a known thing that is described somewhere?