2
$\begingroup$

We know that $\text{BPP} \subseteq \text{BQP}$ but we have no proof that $\text{BPP} \subset \text{BQP}$ (though we have proof that $\text{BQP} \neq \text{BPP}$ with an oracle).

Since Simon's problem (as factoring) is 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?

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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