Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Asked Feb 22 '24 at 13:12

Active Feb 22 '24 at 13:43

Viewed 81 times

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$?

Note:

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.

edited Feb 22 '24 at 13:43

asked Feb 22 '24 at 13:12

108_mk

1

When you write $BQP/NP$, do you mean $BQP\setminus NP$? When you write $BQP\ne NP$, do you mean $BQP\nsubseteq NP$? – Emil Jeřábek Feb 22 '24 at 13:33
@EmilJeřábek, one typo removed. One clarification added. – 108_mk Feb 22 '24 at 13:45

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

0 Answers0