0
$\begingroup$

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:

enter image description here

  1. Histogram of results

enter image description here

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ A workaround is working correclty, thanks. $\endgroup$
    – SmileDay
    Feb 26 at 11:45
  • $\begingroup$ I edited my question. $\endgroup$
    – SmileDay
    Feb 26 at 11:59

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.