Going quantum: using Grover’s algorithm to generate worlds
Tags: quantumcomputing, generativeart
Published: 2024-04-06 09:53:00

[Image credits](https://unsplash.com/it/@profwicks?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash)
  
_Formalizing the algorithm to generate worlds from a set of rules as a SAT problem opens the solution to a “quantum twist”_

As seen in [the previous article](https://dev.to/antigones/trying-to-bridge-the-gap-between-wfc-even-simpler-tiled-model-and-constraint-satisfaction-problem-csp-propositional-rules-1oka), it is possible to express the problem of generating worlds from a set of rules as a boolean SAT problem.

Grover’s algorithm can be used to solve such problems in the quantum computing domain (https://qiskit-community.github.io/qiskit-algorithms/tutorials/06_grover.html). Starting from a set of equiprobable states (Hadamard), Grover’s algorithm is a process capable of “making good states emerge” among all the others.

Let’s try to generate a 1x2 map starting from the following constraints, expressed as propositional formulae:

```
{
  C_00: S_10 & ~C_10 & ~L_10, # C00 iif S_10 and not C_10 and not L_10
  C_10: L_00 & ~C_00 & ~S_00,
  L_00: ~S_10 & (C_10 | L_10),
  L_10: L_00 & ~C_00 & ~S_00,
  S_00: S_10 & ~C_10 & ~L_10,
  S_10: ~L_00 & (C_00 | S_00)
  (C_00 | L_00 | S_00), # you have to choose at least a value
  (C_10 | L_10 | S_10)
}
```

We first need to express those constraints in Conjunctive Normal Form (CNF) and we can use sympy to obtain it:

```
from sympy.logic.boolalg import to_cnf
   c = to_cnf(model_ruleset)
   print(c)
```

The formula expressed as CNF is the following:

```
(L_00 | ~C_10) & (L_00 | ~L_10) & (S_10 | ~C_00) & (S_10 | ~S_00) & 
(C_00 | L_00 | S_00) & (C_10 | L_10 | S_10) & (~C_00 | ~C_10) & 
(~C_00 | ~L_10) & (~C_10 | ~S_00) & (~L_00 | ~S_10) & (~L_10 | ~S_00) & 
(C_00 | S_00 | ~S_10) & (C_10 | L_10 | ~L_00) & 
(L_00 | S_10 | ~C_00) & (L_00 | S_10 | ~C_10) & 
(L_00 | S_10 | ~L_10) & (L_00 | S_10 | ~S_00) & 
(C_00 | C_10 | L_10 | ~S_10) & (C_00 | C_10 | S_00 | ~L_00) & 
(C_00 | L_10 | S_00 | ~L_00) & (C_10 | L_10 | S_00 | ~S_10)
```

Let’s also remap variables with the following equivalence in order to use them with Qiskit:

```
a = L_00
b = L_10
c = C_00
d = C_10
e = S_00
f = S_10
```

Now it’s time to use Grover:

```
from qiskit import MissingOptionalLibraryError
from qiskit.tools.visualization import plot_histogram
from qiskit.primitives import Sampler
from qiskit.algorithms import Grover
from qiskit.circuit.library import PhaseOracle
from qiskit.algorithms import AmplificationProblem

expression = '(a | ~d) & (a | ~b) & (f | ~c) & (f | ~e) & (c | a | e) & (d | b | f) & (~c | ~d) & (~c | ~b) & (~d | ~e) & (~a | ~f) & (~b | ~e) & (c | e | ~f) & (d | b | ~a) & (a | f | ~c) & (a | f | ~d) & (a | f | ~b) & (a | f | ~e) & (c | d | b | ~f) & (c | d | e | ~a) & (c | b | e | ~a) & (d | b | e | ~f)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
    grover = Grover(sampler=Sampler())
    result = grover.amplify(problem)
    print(result)
    display(plot_histogram(result.circuit_results[0]))
except MissingOptionalLibraryError as ex:
    print(ex)
```

In this script, PhaseOracle constructs a quantum circuit which is equivalent to the logical expression in input.

AmplificationProblem builds a problem which is suitable to be elaborated by Grover’s algorithm and specifies a function to evaluate if a state is good.

The script plots the following histogram:

![Quasi-probabilities for states](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ieliwyxjahtu42ot3zr4.png)

The states seem to be mapped in the order they are encountered in the CNF:

```
adbfce
000111
111000
```

Even if the histogram isn’t so much clear, printing the quasi-probabilities as a dictionary shows that the two states with maximum quasi-probability are:

```
S_10, C_00, S_00 (000111)
L_00, C_10, L_10 (111000)
```

Which are equivalent to the following rows in the truth table we previously found for this little 1x2 world:

```
C_00,L_00,S_00,C_10,L_10,S_10
[False, True, False, True, True, False]
[True, False, True, False, False, True]
```