# Special Properties for Oracles in HSP

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 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?