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?

Improve this question
$\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, 2021 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$
    – Don Fanucci
    Jan 26, 2021 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, 2021 at 7:10
  • $\begingroup$ @D.W. I have edited it, maybe now it is more clear... $\endgroup$
    – Don Fanucci
    Jan 26, 2021 at 13:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.