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 nontrivial 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 NPhardness. 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 nontrivial 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 nonabelian 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 nontrivial 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
