If you want to make money online : Register now

[Solved]: Evaluating Grover's algorithm on 3-SAT

, , No Comments
Problem Detail: 

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?

Asked By : vauge

Answered By : Jake

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41663

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback