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

Question

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?

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.