# 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,b\in 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 we can construct a mapping $$M:X\times X\to X$$ such that $$\forall a,b\in G:M(f(a),f(b))=f(a+b)$$ (e.g. when $$f$$ is an homomorphism $$(x,y)\overset{M}{\mapsto} x\cdot_Xy$$ is the mapping). However, $$f$$ is not necessarily an homomorphism and $$X$$ is not necessarily associated with a know group operation either.

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

• Are we guaranteed that $\langle X,M \rangle$ is a group (i.e., treating $M$ as the multiplication operator, we obtain a group on $X$)? Perhaps you could check whether that is guaranteed or whether there is a counterexample? – D.W. Jan 26 at 4:33
• @D.W. In fact using $M$ you can always create a group on the image of $f$, which is a subset of $X$... – Don Fanucci Jan 26 at 5:38
• Cool. Thank you. So it appears we can rephrase your question in the following equivalent form: Given a group homomorphism $f:G \to H$, where $f$ is efficiently computable and the group operation on $G$ is efficiently computable, is the group operation on $H$ necessarily efficiently computable? Do I have that right? If so, it might be worth editing the question to ask that version of the question, as that seems cleaner and simpler to me. – D.W. Jan 26 at 7:10
• @D.W. I have edited it, maybe now it is more clear... – Don Fanucci Jan 26 at 13:06