<p><a href="https://en.wikipedia.org/wiki/Hidden_subgroup_problem" rel="nofollow noreferrer">Wikipedia</a> lists HSP problems in abelian and non-abelian groups. So does the following (extensive) <a href="https://quantumalgorithmzoo.org/" rel="nofollow noreferrer">compedium</a>.</p>
<p>I searched and found none is a BQP-complete (or even BQP-hard) problem.</p>
<p>There has been a discussion on this site about whether <strong>HSP on an abelian group</strong> can be BQP complete; <a href="https://cstheory.stackexchange.com/q/1298/68722">Link</a>. The answer is suspected to be negative (due to a known oracle separation; see link).</p>
<p>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.</p>
<p>My query:</p>
<blockquote>
<p>Is there a hidden subgroup problem in BQP (or even BQP-Hard) that is suspected not to be in NP?</p>
</blockquote>
<blockquote>
<p>Is there some reason for not finding any HSP in <span class="math-container">$BQP\backslash NP$</span>?</p>
</blockquote>
<p>Note:</p>
<ul>
<li>I am assuming conjecture <span class="math-container">$BQP \nsubseteq NP$</span> and <span class="math-container">$NP \nsubseteq BQP$</span> holds true.</li>
<li>I am looking for (full) HSP (both abelian and non-abelian cases).</li>
<li>Assume this is in the context of (corresponding) decision version for HSP problems.</li>
</ul>

CC BY-SA 4.0
2024-02-22T13:33:25.430Z
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
CC BY-SA 4.0
2024-02-22T13:45:02.100Z
@EmilJeřábek, one typo removed. One clarification added.
Manish Kumar
<cc.complexity-theory><quantum-computing><np>
Is there a Hidden subgroup problem in BQP but suspected not to be in NP?
Manish Kumar
# Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

(Asked by: username_0 on 2024-02-22)

[Wikipedia](https://en.wikipedia.org/wiki/Hidden_subgroup_problem) lists HSP problems in abelian and non-abelian groups. So does the following (extensive) [compedium](https://quantumalgorithmzoo.org/).

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](https://cstheory.stackexchange.com/q/1298/68722). 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.

**Tags:** cc.complexity-theory, quantum-computing, np
> **Comments:**
> **username_1**: When you write $BQP/NP$, do you mean $BQP\setminus NP$? When you write $BQP\ne NP$, do you mean $BQP\nsubseteq NP$?  
> **username_0**: @EmilJeřábek, one typo removed. One clarification added.  

---

## 0 answers

