Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

NP-completeness and BQP

  1. Jul 30, 2008 #1
    Do we know (or what we suspect to be) the relationship between NP-complete problems and BQP problems?
  2. jcsd
  3. Jul 31, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook