# Known problems in BQP \ NP?

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?

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

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