Note

This page was generated from tutorials/algorithms/07_grover_examples.ipynb.

# Grover’s algorithm examples¶

This notebook has examples demonstrating how to use the Qiskit Grover search algorithm, with different oracles.

## Finding solutions to 3-SAT problems¶

Let’s look at an example 3-Satisfiability (3-SAT) problem and walk-through how we can use Quantum Search to find its satisfying solutions. 3-SAT problems are usually expressed in Conjunctive Normal Forms (CNF) and written in the DIMACS-CNF format. For example:

```
[1]:
```

```
input_3sat_instance = '''
c example DIMACS-CNF 3-SAT
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
'''
```

The CNF of this 3-SAT instance contains 3 variables and 5 clauses:

\((\neg v_1 \vee \neg v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee v_3) \wedge (v_1 \vee v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee \neg v_3) \wedge (\neg v_1 \vee v_2 \vee v_3)\)

It can be verified that this 3-SAT problem instance has three satisfying solutions:

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((T, T, F)\)

Or, expressed using the DIMACS notation:

`1 -2 3`

, or `-1 -2 -3`

, or `1 2 -3`

.

With this example problem input, we then create the corresponding `oracle`

for our `Grover`

search. In particular, we use the `PhaseOracle`

component, which supports parsing DIMACS-CNF format strings and constructing the corresponding oracle circuit.

```
[2]:
```

```
import os
import tempfile
from qiskit.exceptions import MissingOptionalLibraryError
from qiskit.circuit.library.phase_oracle import PhaseOracle
fp = tempfile.NamedTemporaryFile(mode='w+t', delete=False)
fp.write(input_3sat_instance)
file_name = fp.name
fp.close()
oracle = None
try:
oracle = PhaseOracle.from_dimacs_file(file_name)
except ImportError as ex:
print(ex)
finally:
os.remove(file_name)
```

```
No module named 'tweedledum'
```

The `oracle`

can now be used to create an Grover instance:

```
[3]:
```

```
from qiskit.algorithms import AmplificationProblem
problem = None
if oracle is not None:
problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
```

We can then configure the backend and run the Grover instance to get the result:

```
[4]:
```

```
from qiskit.algorithms import Grover
from qiskit.primitives import Sampler
grover = Grover(sampler=Sampler())
result = None
if problem is not None:
result = grover.amplify(problem)
print(result.assignment)
```

As seen above, a satisfying solution to the specified 3-SAT problem is obtained. And it is indeed one of the three satisfying solutions.

Since we used the `Sampler`

, the complete measurement result is also returned, as shown in the plot below, where it can be seen that the binary strings `000`

, `011`

, and `101`

(note the bit order in each string), corresponding to the three satisfying solutions all have high probabilities associated with them.

```
[5]:
```

```
from qiskit.tools.visualization import plot_histogram
if result is not None:
display(plot_histogram(result.circuit_results[0]))
```

## Boolean Logical Expressions¶

Qiskit’s `Grover`

can also be used to perform Quantum Search on an `Oracle`

constructed from other means, in addition to DIMACS. For example, the `PhaseOracle`

can actually be configured using arbitrary Boolean logical expressions, as demonstrated below.

```
[6]:
```

```
expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
try:
oracle = PhaseOracle(expression)
problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
grover = Grover(sampler=Sampler())
result = grover.amplify(problem)
display(plot_histogram(result.circuit_results[0]))
except MissingOptionalLibraryError as ex:
print(ex)
```

```
"The 'tweedledum' library is required to use 'PhaseOracle'. You can install it with 'pip install tweedledum'."
```

In the example above, the input Boolean logical expression `'(w ^ x) & ~(y ^ z) & (x & y & z)'`

should be quite self-explanatory, where `^`

, `~`

, and `&`

represent the Boolean logical XOR, NOT, and AND operators, respectively. It should be quite easy to figure out the satisfying solution by examining its parts: `w ^ x`

calls for `w`

and `x`

taking different values; `~(y ^ z)`

requires `y`

and `z`

be the same; `x & y & z`

dictates all three to be `True`

. Putting these
together, we get the satisfying solution `(w, x, y, z) = (False, True, True, True)`

, which our `Grover`

’s result agrees with.

```
[7]:
```

```
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
```

### Version Information

Qiskit Software | Version |
---|---|

`qiskit-terra` | 0.24.0 |

`qiskit-aer` | 0.12.0 |

`qiskit-ibmq-provider` | 0.20.2 |

`qiskit` | 0.43.0 |

`qiskit-nature` | 0.6.1 |

`qiskit-finance` | 0.3.4 |

`qiskit-optimization` | 0.5.0 |

`qiskit-machine-learning` | 0.6.1 |

System information | |

Python version | 3.8.16 |

Python compiler | GCC 11.3.0 |

Python build | default, Jan 11 2023 00:28:51 |

OS | Linux |

CPUs | 2 |

Memory (Gb) | 6.781208038330078 |

Wed May 31 14:20:36 2023 UTC |

### This code is a part of Qiskit

© Copyright IBM 2017, 2023.

This code is licensed under the Apache License, Version 2.0. You may

obtain a copy of this license in the LICENSE.txt file in the root directory

of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.

Any modifications or derivative works of this code must retain this

copyright notice, and modified files need to carry a notice indicating

that they have been altered from the originals.

```
[ ]:
```

```
```