Relationship between NP-complete and BQP problems

  • Level: Graduate 
  • Thread starter Dragonfall
  • Start date
1 reply · 4K views · last reply
Dragonfall
Messages
1,023
Reaction score
5
Do we know (or what we suspect to be) the relationship between NP-complete problems and BQP problems?
 
I don't.

It would seem, though, that BQP \ P is inside NP-intermediate. This, of course, should be at least as hard as P =? NP to prove/disprove.