5
$\begingroup$

If $P = NP$, does it follow that $BQP = NP^{BQP}$?

I came up with this question when I was thinking about how $P = NP$ can be described as "does every decision problem where a proof for YES can be verified in time polynomial of the input size on a TM, also have an algorithm that can solve the general problem in time polynomial of the input size on a TM?"

That made me wonder what the relationship is for a BQP equivalent, i.e. whether decision problems that can be verified in BQP can be solved in BQP. Now, because quantum states can't be copied, it's obviously nonsensical for there to be a nondeterministic quantum Turing machine, hence why I made it using NP with BQP oracle--NP to generate every possible proof in poly time, BQP to check them.

I presume the negation would also have interesting security implications, because it would imply that quantum computers can encrypt things in polynomial time that they cannot break in polynomial time even if classical computers cannot.

Is this something that people are actually working on?

$\endgroup$
3

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.