1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Omar Shehab
    Jan 30, 2016 at 3:32
  • $\begingroup$ 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. $\endgroup$
    – Chad Brewbaker
    Jan 30, 2016 at 15:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – Omar Shehab
    Jan 30, 2016 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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