# Is Simon's problem a good NP-intermediate candidate?

We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$ (Though we have the proof that BQP $!=$ BPP with an oracle)

Since Simon's problem (as factoring) it's easily solvable by a quantum computer, and in exponential time complexity solvable by a classical computer, that's a hint of the separation between BQP and BPP and therefore this can be a pure NP problem. Am I right?

• What research and self-study have you done? There are lots of sources that talk about this topic. – D.W. Apr 21 '14 at 14:49

• It is an oracle problem. We are given an oracle for some function $f$. That's not something that you can do within the definition of a NP problem.
• It is a promise problem. We are given the promise that $f$ will satisfy a particular property (it is two-to-one, and has a particular structure). That too is not something you can do within the definition of a NP problem.