Is there any hidden subgroup of a symmetric group which can be efficiently determined?

Question

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

Answer 1

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.

Answer 2

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$.