<p>Yes, an <span class="math-container">$NP$</span>-hard problem high up in the polynomial hierarchy would likely not be <span class="math-container">$QMA$</span>-hard, since otherwise <span class="math-container">$QMA$</span> would be contained in <span class="math-container">$PH$</span>, exactly as you point out. In fact, we don't need to look that far; let us backtrack.</p>
<p>We are looking for a problem which is:</p>
<ul>
<li><em>difficult enough</em> that it is <span class="math-container">$NP$</span>-hard, but</li>
<li><em>easy enough</em> that it is not <span class="math-container">$QMA$</span>-hard</li>
</ul>
<p>Any <span class="math-container">$NP$</span>-Complete problem is an excellent candidate. For example, 3-SAT will do. If, hypothetically, 3-SAT were <span class="math-container">$QMA$</span>-hard, then any <span class="math-container">$QMA$</span> problem can be reduced to it, and in particular any <span class="math-container">$BQP$</span> problem could be reduced to 3-SAT, which would be surprising. The same holds when 3-SAT is substituted by any problem in the polynomial hierarchy that is <span class="math-container">$NP$</span>-hard, as you sugggest. We can make this more formal.</p>
<p><strong>Lemma.</strong> If 3-SAT is <span class="math-container">$QMA$</span>-hard then <span class="math-container">$QMA=NP$</span>.</p>
<p><em>Proof.</em> The difficult part is showing that <span class="math-container">$QMA\subseteq NP$</span>. To this end, let <span class="math-container">$L\in QMA$</span>. Under the assumption, <span class="math-container">$L$</span> can be reduced to 3-SAT. An NP algorithm for <span class="math-container">$L$</span> reduces it to a 3-SAT formula <span class="math-container">$\phi$</span> and then solves 3-SAT by guessing a satisfying assignment for <span class="math-container">$\phi$</span>. Thus, <span class="math-container">$L\in NP$</span>; so <span class="math-container">$QMA\subseteq NP$</span>. The other direction, <span class="math-container">$NP\subseteq QMA$</span>, you seem to have already figured out. <span class="math-container">$\square$</span></p>
<p>You write,</p>
<blockquote>
<p>I thought about considering complete problems in higher classes w.r.t QMA
, i.e., PP
, PSPACE
, EXP
, and so on. However, they are known to be both QMA-hard and NP-hard.</p>
</blockquote>
<p>Yes, that's right. These problems are QMA-hard; therefore, in particular they are NP-hard.</p>

CC BY-SA 4.0
2024-05-31T19:44:27.523Z
2024-05-31T19:44:27.523Z
Lieuwe Vinkhuijzen
<p>I saw this complexity classes diagram in this quantum computing paper in <em><a href="https://www.nature.com/articles/nphys1415/figures/1" rel="nofollow noreferrer">NATURE</a></em>.
<a href="https://i.sstatic.net/65vgRhlB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/65vgRhlB.png" alt="enter image description here" /></a></p>
<p>Based on the <em><strong>standard assumption</strong></em> of <span class="math-container">$P\neq NP\neq QMA$</span>, they also seem to have related the NP-hard and QMA-hard classes as <span class="math-container">$QMA-hard\subseteq NP-hard$</span>.</p>
<p>I am convinced about the containment of QMA-hard in NP-hard.</p>
<p><strong>My query</strong>: I am looking for a problem which is NP-hard but <strong>not</strong> QMA-hard.</p>
<p><strong>My attempt</strong>: I think the problem in the second (or above) level in PH (polynomial hierarchy) is an excellent candidate for it. They are known to be NP-hard but unlikely to be QMA-complete. Otherwise, QMA would lie in PH.</p>
<blockquote>
<p>But, can we find such a problem outside PH? If yes, where do they lie in the complexity theory diagram?</p>
</blockquote>
<p>I thought about considering complete problems in higher classes w.r.t <span class="math-container">$QMA$</span>, i.e., <span class="math-container">$PP$</span>, <span class="math-container">$PSAPCE$</span>, <span class="math-container">$EXP$</span>, and so on. However, they are known to be both QMA-hard and NP-hard. Because <span class="math-container">$NP$</span> and <span class="math-container">$QMA$</span> are contained in <span class="math-container">$PP$</span>, <span class="math-container">$PSPACE$</span>, <span class="math-container">$EXP$</span>, and so on.</p>
<p>I suspect they lie somewhere between the <span class="math-container">$QMA$</span> and complete problems in <span class="math-container">$PP$</span>, <span class="math-container">$PSPACE$</span>, <span class="math-container">$EXP$</span>, etc. Is it correct to think so?</p>

CC BY-SA 4.0
2024-06-03T22:07:49.830Z
Did you reverse your statement that QMA-hard$\subseteq$NP-hard? From your question I think you meant that NP$\subseteq$QMA (which is true) and also that NP$\ne$QMA (which almost everyone believes)
Mark S
CC BY-SA 4.0
2024-06-04T05:07:47.413Z
@MarkS, I need some help to understand your query. I think you are asking if assumption $NP\subset QMA$ (proper subset) implies QMA-hard $\subset$ NP-hard. // (And I am assuming $NP\subset$QMA for the question).
Manish Kumar
CC BY-SA 4.0
2024-06-04T05:11:59.347Z
The paper by Aaronson (from where this picture has been taken) has a small argument on it. I think it is indeed a direct consequence.
Manish Kumar
CC BY-SA 4.0
2024-06-04T10:07:57.953Z
Never mind I was wrong
Mark S
<cc.complexity-theory><np-hardness><complexity-classes><quantum-computing><polynomial-hierarchy>
Where does a problem lie which is NP-hard but not QMA-hard?
Manish Kumar
# Where does a problem lie which is NP-hard but not QMA-hard?

(Asked by: username_0 on 2024-05-30)

I saw this complexity classes diagram in this quantum computing paper in *[NATURE](https://www.nature.com/articles/nphys1415/figures/1)*.
[![enter image description here](https://i.sstatic.net/65vgRhlB.png)](https://i.sstatic.net/65vgRhlB.png)

Based on the ***standard assumption*** of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard classes as $QMA-hard\subseteq NP-hard$.

I am convinced about the containment of QMA-hard in NP-hard.

**My query**: I am looking for a problem which is NP-hard but **not** QMA-hard.

**My attempt**: I think the problem in the second (or above) level in PH (polynomial hierarchy) is an excellent candidate for it. They are known to be NP-hard but unlikely to be QMA-complete. Otherwise, QMA would lie in PH.

> But, can we find such a problem outside PH? If yes, where do they lie in the complexity theory diagram?

I thought about considering complete problems in higher classes w.r.t $QMA$, i.e., $PP$, $PSAPCE$, $EXP$, and so on. However, they are known to be both QMA-hard and NP-hard. Because $NP$ and $QMA$ are contained in $PP$, $PSPACE$, $EXP$, and so on.

I suspect they lie somewhere between the $QMA$ and complete problems in $PP$, $PSPACE$, $EXP$, etc. Is it correct to think so?

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, quantum-computing, polynomial-hierarchy

> **Comments:**
> **username_1**: Did you reverse your statement that QMA-hard$\subseteq$NP-hard? From your question I think you meant that NP$\subseteq$QMA (which is true) and also that NP$\ne$QMA (which almost everyone believes)  
> **username_0**: @MarkS, I need some help to understand your query. I think you are asking if assumption $NP\subset QMA$ (proper subset) implies QMA-hard $\subset$ NP-hard. // (And I am assuming $NP\subset$QMA for the question).  
> **username_0**: The paper by Aaronson (from where this picture has been taken) has a small argument on it. I think it is indeed a direct consequence.  
> **username_1**: Never mind I was wrong  

---

## 1 answers

### Answer by username_2 on 2024-05-31. Score: 3 | Accepted answer

Yes, an $NP$-hard problem high up in the polynomial hierarchy would likely not be $QMA$-hard, since otherwise $QMA$ would be contained in $PH$, exactly as you point out. In fact, we don't need to look that far; let us backtrack.

We are looking for a problem which is:

* *difficult enough* that it is $NP$-hard, but
* *easy enough* that it is not $QMA$-hard

Any $NP$-Complete problem is an excellent candidate. For example, 3-SAT will do. If, hypothetically, 3-SAT were $QMA$-hard, then any $QMA$ problem can be reduced to it, and in particular any $BQP$ problem could be reduced to 3-SAT, which would be surprising. The same holds when 3-SAT is substituted by any problem in the polynomial hierarchy that is $NP$-hard, as you sugggest. We can make this more formal.

**Lemma.** If 3-SAT is $QMA$-hard then $QMA=NP$.

*Proof.* The difficult part is showing that $QMA\subseteq NP$. To this end, let $L\in QMA$. Under the assumption, $L$ can be reduced to 3-SAT. An NP algorithm for $L$ reduces it to a 3-SAT formula $\phi$ and then solves 3-SAT by guessing a satisfying assignment for $\phi$. Thus, $L\in NP$; so $QMA\subseteq NP$. The other direction, $NP\subseteq QMA$, you seem to have already figured out. $\square$

You write,

> I thought about considering complete problems in higher classes w.r.t QMA
> , i.e., PP
> , PSPACE
> , EXP
> , and so on. However, they are known to be both QMA-hard and NP-hard.

Yes, that's right. These problems are QMA-hard; therefore, in particular they are NP-hard.


---

