Note

# 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

/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 SoftwareVersion
qiskit-terra0.18.3
qiskit-aer0.9.1
qiskit-ignis0.6.0
qiskit-ibmq-provider0.17.0
qiskit-aqua0.9.5
qiskit0.31.0
qiskit-nature0.2.2
qiskit-finance0.2.1
qiskit-optimization0.2.3
qiskit-machine-learning0.2.1
System information
Python3.8.12 (default, Sep 13 2021, 08:28:12) [GCC 9.3.0]
OSLinux
CPUs2
Memory (Gb)6.790924072265625
Thu Oct 21 17:47:24 2021 UTC

### This code is a part of Qiskit

[ ]: