6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ No. ​ ​ ​ ​ BQP $\subseteq$ AWPP ​ is known to hold, but ​ P-uniform AC$^0$[6] ​ is not known to differ from PP. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 May 9 '16 at 6:48
  • $\begingroup$ @RickyDemer Then why do we believe that NP does not contain BQP? $\endgroup$ – tparker May 9 '16 at 23:34
6
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ related ​ ​ $\endgroup$ – user12859 May 10 '16 at 20:43
  • $\begingroup$ @RickyDemer I'm not certain enough of my "I don't think" to put it as an answer to that question. $\endgroup$ – Craig Gidney May 10 '16 at 21:29

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.