I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the hidden subgroup is very large:

Our lower bound on the runtime of the standard method, for subgroups of a group $G$, depends upon two parameters: the size of the hidden subgroup $H$ (naturally the problem becomes easy if $H$ is very large), and $c(G)$, the number of conjugacy classes in $G$. We give a lower bound showing that approximately $\left(\frac{\sqrt{|G|}}{|H|\sqrt{c(G)}}\right)^{1/3}$ rounds of Fourier sampling are required before the standard method can identify $H$.

My questions:

  1. Why is it easy?
  2. How large is 'very large'?

My effort: Let the group be $G$ and the subgroup be $H$. One could argue that If any $g \in G$ is found to be in $H$ we know that all $g^n$ are in $H$ for $n \in \mathbb{Z}$. So we can skip them and check other group elements of $G$. But how do we know that determining $g^n$'s is cheaper than feeding them to the quantum circuit?

  • 3
    $\begingroup$ Large objects are difficult to hide, no? $\endgroup$ – Emil Jeřábek Jan 22 '16 at 15:13
  • 4
    $\begingroup$ You can find a generating set for $H$ whp with a (non-quantum) randomized algorithm just by taking $\mathrm{poly}([G:H])$ random samples from $G$, and keeping those that are in $H$. $\endgroup$ – Emil Jeřábek Jan 22 '16 at 15:16
  • $\begingroup$ @EmilJeřábek, what does the quantity $[G:H]$ mean? $\endgroup$ – Omar Shehab Jan 22 '16 at 20:49
  • 4
    $\begingroup$ @OmarShehab: en.wikipedia.org/wiki/Index_of_a_subgroup $\endgroup$ – Huck Bennett Jan 22 '16 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.