NP-completeness and BQP

1. Jul 30, 2008

Dragonfall

Do we know (or what we suspect to be) the relationship between NP-complete problems and BQP problems?

2. Jul 31, 2008

CRGreathouse

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.