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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$.
-
$\begingroup$ Is it possible that PSPACE = NEXP but $P \neq NP$ and $EXP \neq NEXP$? $\endgroup$ Commented Jan 14, 2022 at 20:02