Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium.

I searched and found none is a BQP-complete (or even BQP-hard) problem.

There has been a discussion on this site about whether HSP on an abelian group can be BQP complete; Link. The answer is suspected to be negative (due to a known oracle separation; see link).

A version of the shortest vector problem is known to be NP-hard (due to Ajtai, 1998). SVP is an HSP in the non-abelian group.

My query:

Is there a hidden subgroup problem in BQP (or even BQP-Hard) that is suspected not to be in NP?

Is there some reason for not finding any HSP in $BQP\backslash NP$?


  • I am assuming conjecture $BQP \nsubseteq NP$ and $NP \nsubseteq BQP$ holds true.
  • I am looking for (full) HSP (both abelian and non-abelian cases).
  • Assume this is in the context of (corresponding) decision version for HSP problems.
  • 1
    $\begingroup$ When you write $BQP/NP$, do you mean $BQP\setminus NP$? When you write $BQP\ne NP$, do you mean $BQP\nsubseteq NP$? $\endgroup$ Feb 22 at 13:33
  • $\begingroup$ @EmilJeřábek, one typo removed. One clarification added. $\endgroup$
    – 108_mk
    Feb 22 at 13:45


Your Answer

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