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?

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

Simon's problem is not a pure NP problem, for two reasons:

  • 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.

So Simon's problem is not a problem in the formal complexity class NP; it's just something different. For the same reasons, it's not NP-intermediate, either.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.