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$– ThomasDec 22 '18 at 23:00
-
2$\begingroup$ Even weaker result is not known: Is GI $\in$ BQP? $\endgroup$– Mohammad Al-TurkistanyDec 23 '18 at 13:15
Add a comment
|
$\begingroup$
$\endgroup$
1
To the best of my knowledge this is still open.
-
$\begingroup$ The grand authority utilizes the best of Kodlu's knowledge. $\endgroup$– TurboMar 26 '21 at 3:33