Nota
Esta página foi gerada, a partir de tutorials/algorithms/07_grover.ipynb.
Grover’s algorithm examples¶
Este notebook tem exemplos demonstrando como usar o algoritmo de busca de Grover do Qiskit com diferentes oráculos.
Encontrando soluções para problemas 3-SAT¶
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
'''
O CNF desta instância de 3-SAT contém 3 variáveis e 5 cláusulas:
:math:` (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_2 vee v_ 3) `
Pode-se verificar que esta instância do problema de 3-SAT tem três soluções satisfatórias:
:math:` (v_1, v_2, v_ 3) = (T, F, T) ` ou :math:` (F, F, F) ` ou :math:` (T, T, F) `
Ou, expresso usando a notação DIMACS:
1 -2 3
, or -1 -2 -3
, or 1 2 -3
.
Com este exemplo de problema de entrada, criamos então o oráculo
correspondente para a nossa busca de Grover
. Em particular, utilizamos a componente PhaseOracle
, que suporta a interpretação de strings no formato DIMACS-CNF e a construção do circuito do oráculo correspondente.
[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 MissingOptionalLibraryError as ex:
print(ex)
finally:
os.remove(file_name)
O oráculo
agora pode ser usado para criar uma instância de Grover:
[3]:
from qiskit.algorithms import AmplificationProblem
problem = None
if oracle is not None:
problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
Podemos, então, configurar o backend e executar a instância de Grover para obter o resultado:
[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)
000
Como visto acima, uma solução satisfatória para o problema de 3-SAT especificado é obtida. E é de fato uma das três soluções satisfatórias.
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]))

Expressões Lógicas Booleanas¶
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)

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.
[16]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
Version Information
Qiskit Software | Version |
---|---|
qiskit-terra | 0.22.2 |
qiskit-aer | 0.11.1 |
qiskit-ibmq-provider | 0.19.2 |
qiskit | 0.39.2 |
qiskit-optimization | 0.4.0 |
System information | |
Python version | 3.9.10 |
Python compiler | Clang 13.1.6 (clang-1316.0.21.2.5) |
Python build | main, Aug 9 2022 18:26:17 |
OS | Darwin |
CPUs | 10 |
Memory (Gb) | 64.0 |
Thu Nov 17 09:09:08 2022 JST |
This code is a part of Qiskit
© Copyright IBM 2017, 2022.
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.
[ ]: