0
$\begingroup$

Quantum search differs from the standard boolean SAT as it is restricted to only oracle calls to a circuit (or CNF formula). Where SAT gives us the structure of a formula (however loosely defined that is), quantum search algorithms make queries to $U_f$.

It seems pretty clear that this oracle-only SAT problem is NP-hard. Of course, it isn't a decision problem, but rather it is an oracle problem, so my notion of reduction is $A \leq B \iff$ "an oracle to solve B can be used to solve A in polytime." (A Turing reduction).

If we had an oracle that solved quantum search, then we could just use this oracle to solve SAT.

But I'm curious on what is known about the inverse; i.e., if we had an oracle that solved SAT, could we solve quantum search? Has it been shown that this isn't true? Intuitively, this being true feels like it proves $P = NP$, but I'm not quite sure.

Also, it's pretty easy to see how quantum search can be verified in polynomial (constant) time. But I am asking if it can reduce to SAT, which is my definition of NP here.

Improve this question
$\endgroup$
3
  • $\begingroup$ Isn't it trivial to show Quantum Search isn't in P because to distinguish between a case where $U_f$ is identically 0 and when it's 1 at a single random point you'd have to query that particular point? $\endgroup$
    – Command Master
    May 1 at 1:40
  • $\begingroup$ @CommandMaster Yes that is true. But my question is if we know quantum search is not in NP. $\endgroup$
    – Loic Stoic
    May 1 at 6:40
  • $\begingroup$ If you can nondeterministically query the oracle then it is (just guess the solution), and if not I believe the previous argument still applies. $\endgroup$
    – Command Master
    May 1 at 13:07

0

Reset to default

Your Answer

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