8
$\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$
2
  • $\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, 2016 at 6:48
  • $\begingroup$ @RickyDemer Then why do we believe that NP does not contain BQP? $\endgroup$
    – tparker
    May 9, 2016 at 23:34

1 Answer 1

9
$\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$
2
  • $\begingroup$ related ​ ​ $\endgroup$
    – user12859
    May 10, 2016 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$ May 10, 2016 at 21:29

Your Answer

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

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