How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows? In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial subgroup from an order-$2$ subgroup consisting of $\frac{n}{2}$ disjoint transpositions when the group is a symmetric group $S_n$.

My question:


How the hardness of the hidden subgroup problem changes when the order of the subgroup grows beyond $2$?
Is induction the ideal way to derive it?


My effort:

I am confused how to approach this problem. Should we find the element in the hidden subgroup with with largest absolute value of its character? If we can determine the value, would it be useful?
At worst you have to check one element of each repeated prime cycle, https://oeis.org/A186202 Smaller than n! but still large.