There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum algorithm to find a hidden subgroup in a symmetric group even when the structure of the hidden subgroup is heavily restricted (e.g. the hidden subgroup could be a very special direct or semidirect product)?


From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever the hidden subgroup is normal (but this is not a property of the subgroup itself - analogous to being a direct product etc - but rather how the subgroup sits within the larger group), but that's no help for the symmetric group because its only normal subgroup is the alternating group (for $n \geq 5$).

From the examples of [1] - which shows that in the symmetric group strong Fourier sampling produces distributions for the hidden trivial group vs a hidden random involution that are exponentially close - and [2], it would seem that there may be some hope if the hidden subgroup is promised to be relatively large. But you would need to either be able to show that Fourier sampling succeeds in this case, or to come up with a different method that (likely) really took advantage of the largeness of the hidden subgroup.

Moore, Russell, and Sniady [3] also showed that the other relatively successful method - a Kuperberg-style sieve - doesn't work efficiently in a group very close to the symmetric group (namely, $S_n \wr S_2 = (S_n \times S_n) \rtimes S_2$), to distinguish a hidden trivial group from a hidden involution.

[1] Moore, C., A. Russell, and L. J. Schulman. The Symmetric Group Defies Strong Fourier Sampling. SIAM J. Comput. 37, p. 1842, 2008. Preliminary version in FOCS 2005. (arXiv version)

[2] Grigni, M., L. J. Schulman, M. Vazirani, and U. Vazirani. Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem. Combinatorica 24, p. 137, 2004. Preliminary version in STOC 2001.

[3] Moore, Russell, and Sniady. On the impossibility of a quantum sieve algorithm for graph isomorphism. SIAM J. Comput. 39 (2010), no. 6, 2377–2396. Preliminary version in STOC 2007.

  • $\begingroup$ when you say 'the structure of the hidden subgroup', what properties, other than the size of the subgroup, do you indicate? $\endgroup$ – Omar Shehab Mar 20 '16 at 20:58
  • 1
    $\begingroup$ @OmarShehab: I had in mind intrinsic properties like the ones you specified: being a special direct or semi-direct product, being solvable, or other properties that depend only on the subgroup, and not on how it sits inside the larger group. $\endgroup$ – Joshua Grochow Mar 21 '16 at 0:45
  • $\begingroup$ Why being a product of special type should increase the probability of the subgroup getting detected? Shouldn't it depend on how it lies inside the symmetric group? We are doing sampling here. Shouldn't finding a needle in the haystack be easier if the the number of the needles is a big percentage of the total number of hays? $\endgroup$ – Omar Shehab Mar 21 '16 at 0:52
  • 1
    $\begingroup$ @OmarShehab: I agree. I was just going based on your initial question, which specifically mentioned direct product, semidirect product, and other properties of the subgroup itself, and trying to say that we have no idea how to use such properties. $\endgroup$ – Joshua Grochow Mar 21 '16 at 3:52

Exact classical bounds are known, https://oeis.org/A186202 , you only have to sample certain prime cycles as they form a min dominating set on $S_n$ under a detection relation. Smaller than $n!$ but still about the order of $p!$ were $p$ is the largest prime less than or equal to $n$.

  • 4
    $\begingroup$ This gives an upper bound that is not particularly efficient. Not that we know how to do much better, but the question was about why we haven't found efficient algorithms for the HSP in the symmetric group. That is, about obstacles or lower bounds. How is your answer relevant? $\endgroup$ – Joshua Grochow Mar 17 '16 at 21:42

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.