The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\text{BQP} \not\subset \text{NP}$? Are there any specific problems known or suspected to be in $\text{BQP}$ but outside of $\text{NP}$? If so, what's the simplest known example?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ No. BQP $\subseteq$ AWPP is known to hold, but P-uniform AC$^0$[6] is not known to differ from PP. $\endgroup$– user12859May 9, 2016 at 6:48
-
$\begingroup$ @RickyDemer Then why do we believe that NP does not contain BQP? $\endgroup$– tparkerMay 9, 2016 at 23:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is also still an open problem.
It is suspected that $\text{BQP} \not\subset \text{NP}$. In fact it's suspected that $\text{BQP} \not\subset \text{PH}$ via the "Recursive Fourier Sampling" problem. But proving separations between complexity classes is surprisingly hard. I don't think anyone's even managed to show that $\text{BQP} \not\subset$ $\text{LSPACE}$.
-
-
$\begingroup$ @RickyDemer I'm not certain enough of my "I don't think" to put it as an answer to that question. $\endgroup$ May 10, 2016 at 21:29