I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all.

However, what I still don't get is how to determine whether a satisfying variable assignment was found after having applied Grover's algorithm. The final step (as described in wikipedia) is to measure $λ_ω$ which in the case of solving 3-SAT would give me an assignment for the variables of my formula. Do I need to check manually whether this assignment is indeed a satisfying assignment? Or is there any better way to find out whether there exists at least one match?


1 Answer 1


"Measuring", in quantum computation, is the act reading the quantum state along some basis. This will cause the the quantum state to collapse. The quantum state after grovers algorithm is such that it collapses with very high probability to the desired result (in this case an assignment). Perhaps you should check the result because it might just be a bad case, that is just unlikely, but you don't have to check the result to get the output of grovers algorithm. You just have to measure it. To determine with high probability weather or not the formula was SAT you should check the assignment that it gave out.

  • 1
    $\begingroup$ So the steps are: 1) Apply Grover's algorithm 2) Measure the output of Grover's algorithm 3) Check whether the output in fact satisfies the formula. If so, the formula is in SAT, if not, we have a high probability that it is not. Have I understood that correctly? $\endgroup$
    – vauge
    Apr 21, 2015 at 19:07
  • $\begingroup$ Yes, that is correct. $\endgroup$
    – Jake
    Apr 21, 2015 at 19:12

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.