<p>At worst you have to check one element of each repeated prime cycle, <a href="https://oeis.org/A186202" rel="nofollow">https://oeis.org/A186202</a> Smaller than n! but still large.</p>

CC BY-SA 3.0
2016-01-30T03:32:18.267Z
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
CC BY-SA 3.0
2016-01-30T15:48:55.460Z
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
CC BY-SA 3.0
2016-01-30T17:29:44.323Z
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
CC BY-SA 3.0
2016-01-29T16:08:58.223Z
2016-01-29T16:08:58.223Z
Chad Brewbaker
<p>In <a href="http://www.cs.tau.ac.il/~amnon/Papers/HRT.stoc00.pdf" rel="nofollow">Normal Subgroup Reconstruction and Quantum Computation Using Group Representations</a> 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$.</p>

<p><strong>My question:</strong></p>

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

<p><strong>My effort:</strong></p>

<p>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?</p>

<quantum-computing><linear-algebra><quantum-information><physics><gr.group-theory>
How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?
Omar Shehab
# How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?

(Asked by: username_0 on 2016-01-29)

In [Normal Subgroup Reconstruction and Quantum Computation Using Group Representations](http://www.cs.tau.ac.il/~amnon/Papers/HRT.stoc00.pdf) 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?

**Tags:** quantum-computing, linear-algebra, quantum-information, physics, gr.group-theory


---

## 1 answers

### Answer by username_1 on 2016-01-29. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  
> **username_0**: 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.  

---

