0
$\begingroup$

On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly unlikely scenario that $BQP = PSPACE = NEXP$. What would the implications be? I assume this would render P vs NP completely irrelevant with a quantum computer as $NP \subset NEXPTIME$ and therefore, if $BQP = NEXP$, $NP \subset BQP$. Allowing us to not only solve $NP$ complete problems but even harder problems. I imagine this would be quite groundbreaking as that would mean things like solving chess would be very much possible. This is not at all likely but it cannot be entirely ruled out to my knowledge.

$\endgroup$

1 Answer 1

1
$\begingroup$

It is known that $BQP \subseteq PSPACE \subseteq EXP \subseteq NEXPTIME$.

If $BQP = NEXPTIME$ then $PSPACE = EXP $ and $ EXP = NEXPTIME $.

This would imply $L = P$ and $P = NP$.

$\endgroup$
1
  • $\begingroup$ Is it possible that PSPACE = NEXP but $P \neq NP$ and $EXP \neq NEXP$? $\endgroup$ Jan 14 at 20:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.