Note

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

Run interactively in the IBM Quantum lab.

# 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 BasicAer
from qiskit.tools.visualization import plot_histogram
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle, TruthTableOracle
```

## 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 `LogicalExpressionOracle`

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

```
[3]:
```

```
oracle = LogicalExpressionOracle(input_3sat_instance)
```

The `oracle`

can now be used to create an Grover instance:

```
[4]:
```

```
grover = Grover(oracle)
```

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

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

```
[5]:
```

```
backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = grover.run(quantum_instance)
print(result.assignment)
```

```
/home/runner/work/qiskit/qiskit/.tox/docs/lib/python3.8/site-packages/qiskit/aqua/quantum_instance.py:135: DeprecationWarning: The class qiskit.aqua.QuantumInstance is deprecated. It was moved/refactored to qiskit.utils.QuantumInstance (pip install qiskit-terra). For more information see <https://github.com/Qiskit/qiskit-aqua/blob/master/README.md#migration-guide>
warn_class('aqua.QuantumInstance',
```

```
[1, -2, 3]
```

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 `'qasm_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]:
```

```
plot_histogram(result.measurement)
```

```
[6]:
```

## 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 `LogicalExpressionOracle`

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

```
[7]:
```

```
expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)
```

```
[7]:
```

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.

## TruthTable Oracles¶

With Qiskit, `Oracle`

s can also be constructed from truth tables, meaning we can also perform Quantum Search on truth tables. Even though this might seem like a moot point as we would be essentially searching for entries of a truth table with the \(1\) value, it’s a good example for demonstrative purpose.

```
[8]:
```

```
truthtable = '1000000000000001'
```

As shown, the `truthtable`

is specified with a bitstring containing values of all entries in the table. It has length \(16\), so the corresponding truth table is of \(4\) input bits. Since the very first and last values are \(1\), the corresponding truth table target entries are `0000`

and `1111`

.

Next, we can setup the `Oracle`

and `Grover`

objects to perform Quantum Search as usual.

```
[9]:
```

```
oracle = TruthTableOracle(truthtable)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)
```

```
[9]:
```

As seen in the above plot the search result coincides with our expectation.

```
[10]:
```

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

### Version Information

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

Qiskit | 0.25.4 |

Terra | 0.17.2 |

Aer | 0.8.2 |

Ignis | 0.6.0 |

Aqua | 0.9.1 |

IBM Q Provider | 0.12.3 |

System information | |

Python | 3.8.10 (default, May 4 2021, 07:16:51) [GCC 9.3.0] |

OS | Linux |

CPUs | 2 |

Memory (Gb) | 6.791343688964844 |

Wed May 05 19:46:13 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.

```
[ ]:
```

```
```