# Oracle separation between coNP and QMA implies oracle separation between NP and QMA

In [this] paper, Aaronson remarks (page 2, footnote) that:

From the BBBV lower bound for quantum search , one immediately obtains an oracle $$A$$ such that $$coNP^{A} \not\subseteq QMA^{A}$$ for if there exists a witness state $$|φ⟩$$ that causes a $$QMA$$ verifier to accept the all-0 oracle string, then that same $$|φ⟩$$ must also cause the verifier to accept some string of Hamming weight 1.

What stops us from modifying this argument to get a oracle separation between $$NP$$ and $$QMA$$ (using diagonalization etc)? For example, one can have an argument like the following:

From the BBBV lower bound for quantum search , one immediately obtains an oracle $$A$$ such that $$NP^{A} \not\subseteq QMA^{A}$$ for if there exists a witness state $$|φ⟩$$ that causes a $$QMA$$ verifier to reject the all-0 oracle string, then that same $$|φ⟩$$ must also cause the verifier to reject some string of Hamming weight 1.

In other words, during diagonalization, if the machine rejects with high probability in the presence of a proof for a no instance, then the machine will reject with high probability in the presence of the same proof if the oracle is changed to make it a yes instance. This is true for any proof that the prover might send (if there were a proof making the verifier accept for some string with Hamming weight 1, the same proof would also have made him accept the all 0 string: which is a contradiction as he rejects the all 0 string. Hence, no proof can make him accept some string with Hamming weight 1).

However, the second argument is nonsense as $$NP^{A} \subseteq QMA^{A}$$ for any oracle $$A$$ (and the prover can just send the verifier the right string to query when we change the oracle to a yes instance). But I cannot put a finger on where the argument is going wrong when stated as above.