# Grover's algorithm for 3SAT problem gives unexpected results

Based on SAT problem and Grover's algorithm, I've done some experiments. For the below example, I've received unexpected results:

1. Input: boolean function:

c example 4
p cnf 3 4
1 -2 -3 0
1 -2 3 0
1 2 -3 0
-1 -2 -3 0

2. Truth table of boolean function:

1. Histogram of results

According to the truth table, the results should be ['000', '001', '011', '101']. Why does the algorithm not return the expected solutions?

EDIT: Regarding the first comment. I've noticed that for boolean function:

c example 3
p cnf 3 3
1 -2 -3 0
1 -2 3 0
1 2 -3 0


We get the correct results. In this example $$M>N/2$$.Additionally, I've noticed that the first example is a balanced function and the second one is not. Is it relevant?

## 1 Answer

This issue happens because $$M \geq \frac{N}{2}$$, where $$M$$ is the number of solutions and $$N$$ is the search domain size. For more details see this answer.

A workaround is to double the search domain by adding a dummy variable:

c example 4
c Add one to <#vars> and <#clauses>
p cnf 4 5
1 -2 -3 0
1 -2 3 0
1 2 -3 0
-1 -2 -3 0
c Add a clause for the dummy variable
-4 0


For you second example, 3 out of 5 solutions will be returned if the optimal number of iterations is used ($$\Big\lfloor \frac{\pi}{4} \sqrt{N/M}\Big\rfloor$$). You can get all the solutions by changing the number of iterations:

grover = Grover(iterations = 2, quantum_instance=quantum_instance)


Doing the same for the first example will not work (see the figure in this answer). However, doubling search domain should always work.

• A workaround is working correclty, thanks. Feb 26 at 11:45
• I edited my question. Feb 26 at 11:59