# 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:

1. How the hardness of the hidden subgroup problem changes when the order of the subgroup grows beyond $2$?
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?

## 1 Answer

At worst you have to check one element of each repeated prime cycle, https://oeis.org/A186202 Smaller than n! but still large.

• did you mean in the worst case I have to check one element from each prime cycle where the prime cycles generate the subgroup of my interest? – Omar Shehab Jan 30 '16 at 3:32
• You would have to check one nontrivial permutation for each of the (repeated) prime cycles in your subgroup to exhaustively search. That's for classic black box testing not quantum. – Chad Brewbaker Jan 30 '16 at 15:48
• I think for quantum blackbox testing we need to calculate the difference between the probability of measuring the label of the representing for the trivial subgroup element and the subgroup element which has the largest absolute value of character. – Omar Shehab Jan 30 '16 at 17:29