3
$\begingroup$

Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item.

However, when checking whether a given formula is in 3-SAT, I don't know how many items match the search criterion (i.e. how many interpretations satisfy the formula) and I just want to know whether there is at least one. So, what steps have to be taken in order to make Grover's algorithm suitable for 3-SAT?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\begingroup$

Grover's algorithm is already suitable. It promises that if there is at least one match, then it will output at least one match. It doesn't promise to output all matches, but you don't need all matches.

It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases. If there are multiple matches, the algorithm will still work and will still find a match; and the running time will remain the same.

Improve this answer
$\endgroup$
4
  • $\begingroup$ ??? grovers algorithm is for db search, so how is it applied to SAT? a fundamentally different problem... $\endgroup$
    – vzn
    Apr 21, 2015 at 1:03
  • 2
    $\begingroup$ @vzn You are searching a database. The database is indexed by truth assignments, and each cell contains the truth value of the formula under the assignment. $\endgroup$
    – Yuval Filmus
    Apr 21, 2015 at 5:11
  • $\begingroup$ ok this seems to be invoking the use of oracles & maybe is not exactly in line with the original conception of the algorithm. "When applications of Grover's algorithm are considered, it should be emphasized that the database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index." grover algorithm / wikipedia. anyway think a ref that specifically discusses combining Grover + SAT would be helpful. $\endgroup$
    – vzn
    Apr 21, 2015 at 16:06
  • 2
    $\begingroup$ @vzn On the contrary. If you are given an arbitrary list of length $n$, Grover's algorithm doesn't help you – you have to check all entries, and this takes linear time. The list (or database) has to be given implicitly through an oracle for the speedup (and the algorithm) to make sense. $\endgroup$
    – Yuval Filmus
    Apr 21, 2015 at 18:07
4
$\begingroup$

Notwithstanding D.W.'s answer, the other option, if all you knew about Grover's algorithm is that it requires unique solutions, is to use the work of Valiant and Vazirani. Without getting into details, the idea is like this. Suppose that there are roughly $2^k$ solutions. We add random constraints that "kill" a solution with probability $2^{-k}$. With constant probability, the resulting instance has a unique solution. While we don't know $k$, there are only polynomially many possible $k$s, so we can enumerate over all of them.

Improve this answer
$\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.