1
$\begingroup$

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

From the BBBV lower bound for quantum search [6], 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 [6], 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.