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.

```
[1]:
```

```
import pylab
import numpy as np
from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit.tools.visualization import plot_histogram
from qiskit.algorithms import Grover, AmplificationProblem
from qiskit.circuit.library.phase_oracle import PhaseOracle
```

## 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:

```
[2]:
```

```
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.

```
[3]:
```

```
import os
import tempfile
from qiskit.exceptions import MissingOptionalLibraryError
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 MissingOptionalLibraryError as ex:
print(ex)
finally:
os.remove(file_name)
```

The `oracle`

can now be used to create an Grover instance:

```
[4]:
```

```
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:

```
[5]:
```

```
backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
grover = Grover(quantum_instance=quantum_instance)
result = None
if problem is not None:
result = grover.amplify(problem)
print(result.assignment)
```

```
101
```

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 `'aer_simulator'`

, 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.

```
[6]:
```

```
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.

```
[7]:
```

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

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.

```
[8]:
```

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

```
/home/runner/work/qiskit/qiskit/.tox/docs/lib/python3.8/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
warn_package('aqua', 'qiskit-terra')
```

### Version Information

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

`qiskit-terra` | 0.18.3 |

`qiskit-aer` | 0.9.1 |

`qiskit-ignis` | 0.6.0 |

`qiskit-ibmq-provider` | 0.17.0 |

`qiskit-aqua` | 0.9.5 |

`qiskit` | 0.31.0 |

`qiskit-nature` | 0.2.2 |

`qiskit-finance` | 0.2.1 |

`qiskit-optimization` | 0.2.3 |

`qiskit-machine-learning` | 0.2.1 |

System information | |

Python | 3.8.12 (default, Sep 13 2021, 08:28:12) [GCC 9.3.0] |

OS | Linux |

CPUs | 2 |

Memory (Gb) | 6.790924072265625 |

Thu Oct 21 17:47:24 2021 UTC |

### This code is a part of Qiskit

© Copyright IBM 2017, 2021.

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.

```
[ ]:
```

```
```