2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Jan 26 at 4:33
  • $\begingroup$ @D.W. In fact using $M$ you can always create a group on the image of $f$, which is a subset of $X$... $\endgroup$ Jan 26 at 5:38
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 26 at 7:10
  • $\begingroup$ @D.W. I have edited it, maybe now it is more clear... $\endgroup$ Jan 26 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.