1
$\begingroup$

I computed SAT formula with the Grover search algorithm on the Qiskit simulator with default parameters, but I don't understand why the incorrect solutions don't have a probability of 0?

The SAT formula is $(x_1 \vee x_2) \wedge (x_2 \vee x_3)$.

result

$\endgroup$
2
  • 1
    $\begingroup$ Hi! What was the sat formula you were using? $\endgroup$
    – met927
    Apr 23, 2020 at 12:34
  • 1
    $\begingroup$ Sorry @met927 , the formula is : (x1 v x2) ^ (x2 v x3) $\endgroup$ Apr 23, 2020 at 12:42

1 Answer 1

3
$\begingroup$

It seems that the algorithm works well. Your formula returns zero for inputs 000, 001 and 100. Those values have very low probability in comparison with others states in histogram you provided. Since there is some level of noise, the probabilities are not zero for 000, 001 and 100.

Note that even the simulator on IBM Q generates some noise because of finite precision of the simulator.

Overall, there is no mistake.

$\endgroup$
4
  • 1
    $\begingroup$ I read on this that the qasm simulator has no noise by default ? $\endgroup$ Apr 23, 2020 at 14:29
  • 1
    $\begingroup$ @julienrodriguez: Sorry for my inaccuracy, but the result is the same. That is the simulator does not corespond with theory 1:1. $\endgroup$ Apr 23, 2020 at 14:49
  • 1
    $\begingroup$ @julienrodriguez: I fixed the answer accordingly. $\endgroup$ Apr 23, 2020 at 14:51
  • $\begingroup$ Thank you @Martin :) $\endgroup$ Apr 23, 2020 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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