From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP.
Has this been demonstrated or not?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Proving or disproving $\mathsf{NP} \not\subset \mathsf{BQP}$ would be a huge breakthrough and wikipedia would know about it $\endgroup$ – Thomas Dec 22 '18 at 23:00
-
2$\begingroup$ Even weaker result is not known: Is GI $\in$ BQP? $\endgroup$ – Mohammad Al-Turkistany Dec 23 '18 at 13:15
Add a comment
|
$\begingroup$
$\endgroup$
To the best of my knowledge this is still open.
