<p>I am going through <a href="https://www.math.ucdavis.edu/~vazirani/Papers/hidden.subgroup.pdf" rel="nofollow">QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM</a> 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:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p><strong>My questions:</strong></p>

<ol>
<li>Why is it easy?</li>
<li>How large is 'very large'?</li>
</ol>

<p><strong>My effort:</strong>
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?</p>

CC BY-SA 3.0
2016-01-22T15:13:42.497Z
Large objects are difficult to hide, no?
Emil Jeřábek
CC BY-SA 3.0
2016-01-22T15:16:46.853Z
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$.
Emil Jeřábek
CC BY-SA 3.0
2016-01-22T20:49:38.543Z
@EmilJeřábek, what does the quantity $[G:H]$ mean?
Omar Shehab
CC BY-SA 3.0
2016-01-22T21:35:34.360Z
@OmarShehab: https://en.wikipedia.org/wiki/Index_of_a_subgroup
Huck Bennett
<quantum-computing><linear-algebra><quantum-information><physics><gr.group-theory>
Why hidden subgroup problem is easy for very large subgroup?
Omar Shehab
# Why hidden subgroup problem is easy for very large subgroup?

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

I am going through [QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM](https://www.math.ucdavis.edu/~vazirani/Papers/hidden.subgroup.pdf) 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?

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

> **Comments:**
> **username_1**: Large objects are difficult to hide, no?  
> **username_1**: 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$.  
> **username_0**: @EmilJeřábek, what does the quantity $[G:H]$ mean?  
> **username_2**: @OmarShehab: https://en.wikipedia.org/wiki/Index_of_a_subgroup  

---

## 0 answers

