4
$\begingroup$

I've encountered a model which can be thought of as a version of the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), but that doesn't quite meet the standard problem's requirements.

Specifically, the universe group is $S_n$ (the permutation group of order $n$), and is hence not Abelian. Also, my hiding function cannot be described with a low enough number of bits.

I'm trying to show that my problem is NP-hard (which I suspect might be the case). So,

Are there any known NP-hard variants of the non-Abelian hidden subgroup problem?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Link for the ignorant and lazy (such as myself): en.wikipedia.org/wiki/Hidden_subgroup_problem $\endgroup$
    – Neal Young
    Jul 27 at 22:30
  • $\begingroup$ @NealYoung - added also to the post. Thanks. $\endgroup$
    – Shaull
    Jul 28 at 7:02
  • 4
    $\begingroup$ Greg Kuperberg proved NP-hardness of HSP over Q, which is abelian though. To my knowledge, the paper is not published yet, but you can find the presentation in QIP'2021 at youtube.com/watch?v=HdUiO78bVdI. $\endgroup$
    – Hhan
    Jul 28 at 13:36
  • 1
    $\begingroup$ There's a pretty canonical reduction showing that if you can efficiently solve HSP for the symmetric group $S_n$ then you can efficiently solve graph isomorphism. I'm not sure if the reduction works the other way (e.g. if you can solve graph isomorphism efficiently then that gets you an alg. for HSP over $S_n$), but if it did then I think that would imply that HSP over $S_n$ is not likely to be NP-hard. I really liked Christopher Moore's lecture on this here - something about the traces of representations of $S_n$ play a strong role. $\endgroup$
    – Mark S
    Jul 31 at 21:14
  • $\begingroup$ @MarkS - Thanks! I'm presuming this refers to a description of the hiding function which is similar to the Abelian HSP. Do you know anything about descriptions that e.g., require more bits for the hiding function? $\endgroup$
    – Shaull
    Aug 1 at 6:09

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.