I read some materials more general about HSP such as 1,2,3. I wonder that if it would be possible to have a faster quantum algorithm when our goal was just to find a non-trivial element of the hidden subgroup H (in any HSP problem for which there is currently no polynomial quantum algorithm), is there any literature on this issue ？
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ In your link to greg Kuperberg's slides, I notice that on p13 he writes: 'We must convert HSP to a decision problem for NP-hardness. If $G = \mathbb{Q}$, we choose “Is $H \neq \mathbb{Z}$?” In other cases, we choose “Is $H \neq 1$?".' So it appears that, in the "other cases" (free groups and free abelian groups), his results show that even finding a non-trivial element is hard. $\endgroup$– HJRWCommented Mar 16, 2023 at 9:51
-
$\begingroup$ Thanks you, and sorry for that I didn't notice the sentences in p13, But what greg Kuperberg said ''In other cases, we choose 'Is $H \neq 1$ ?' '' just means when $G=F_k$ is non-abelian free or $G=\mathbb{Z}^n$ with unary vector encoding (on p7), the HSP is hard. So only in this case, his results show that even finding a non-trivial element is hard as you say. $\endgroup$– constantineCommented Mar 16, 2023 at 11:46
-
1$\begingroup$ Of course one can ask similar questions about other groups! But MO askers are expected to do their own due diligence. I suggest you start by thoroughly examining the literature that you already know! Then perhaps you can ask a more focussed question, which is likely to get better answers. $\endgroup$– HJRWCommented Mar 16, 2023 at 14:08
-
$\begingroup$ Thank you for your advice. I will do it. $\endgroup$– constantineCommented Mar 16, 2023 at 15:03
Add a comment
|