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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: NP-completeness and BQP
  1. NP-hard or NP-Complete (Replies: 3)

  2. P=np refuted (Replies: 3)

  3. P = np formula (Replies: 7)

  4. A proof for P vs NP (Replies: 8)

  5. P Versus NP Problem (Replies: 5)