# Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE.

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?

• 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) Commented Jun 3 at 22:07
• @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). Commented Jun 4 at 5:07
• 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. Commented Jun 4 at 5:11
• Never mind I was wrong Commented Jun 4 at 10:07

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.