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

Question

I saw this complexity class diagram in this quantum computing paper in NATURE . enter image description here

Based on the standard assumption of $\mathsf{P\neq NP\neq QMA}$, they have related the $\mathsf{NP}$-hard and $\mathsf{QMA}$-hard classes as $\mathsf{QMA}$-hard $\subseteq \mathsf{NP}$-hard.

I am convinced about the containment of $\mathsf{QMA}$-hard in $\mathsf{NP}$-hard.

My query: I am looking for a problem which is $\mathsf{NP}$-hard but not $\mathsf{QMA}$-hard. (Indicated with the red arrow in the picture above.)

My attempt: I think the problem at the second (or higher) level of $\mathsf{PH}$ (polynomial hierarchy) is an excellent candidate for it. They are known to be $\mathsf{NP}$-hard but unlikely to be $\mathsf{QMA}$-complete. Otherwise, $\mathsf{QMA}$ would lie in $\mathsf{PH}$.

But, can we find such a problem outside $\mathsf{PH}$? If yes, where do they lie in the complexity theory diagram?

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

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

• Mark S: 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)
• Manish Kumar: @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: 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.
• Mark S: Never mind I was wrong

Answer 1

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.