Nota
Esta página foi gerada, a partir de tutorials/algorithms/07_grover.ipynb.
Exemplos do algoritmo de Grover¶
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¶
Vamos ver um exemplo de problema de 3-Satisfiability (3-SAT) e descobrir como podemos usar a Busca Quântica para encontrar as soluções satisfatórias. Problemas 3-SAT geralmente são expressos em Formas Normais Conjuntivas (CNF) e escritos no formato DIMACS-CNF. Por exemplo:
[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 ImportError as ex:
print(ex)
finally:
os.remove(file_name)
"The 'tweedledum' library is required to use 'classical function oracles'. You can install it with 'pip install tweedledum'."
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)
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.
Como usamos o Sampler
, o resultado completo da medição também é retornado, conforme mostrado no gráfico abaixo, onde pode ser visto que as strings binárias 000
, 011
e ``101 `` (observe a ordem dos bits em cada string), correspondendo às três soluções satisfatórias, todas têm altas probabilidades associadas a elas.
[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¶
O Grover
do Qiskit também pode ser usado para executar a Busca Quântica em um Oráculo
construído a partir de outros meios, além de DIMACS. Por exemplo, o PhaseOracle
pode na verdade ser configurado usando expressões lógicas booleanas arbitrárias, como demonstrado abaixo.
[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'."
No exemplo acima, a expressão lógica booleana de entrada '(w ^ x) & ~(y ^ z) & (x & y & z)'
é auto-explicativa, onde ^
, ~
e &
representam os operadores booleanos XOR, NOT e AND respectivamente. É relativamente fácil descobrir a solução satisfatória examinando as suas partes: w ^ x
resulta em w
e x
tomando valores diferentes; ~(y ^ z)
requer que y
e z
sejam iguais; enquanto x & y & z
dita que todos os três sejam True
. Juntando isso, obtemos a solução satisfatória (w, x, y, z) = (False, True, True, True)
, que concorda com o resultado do nosso Grover
.
[7]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright
Version Information
Qiskit Software | Version |
---|---|
qiskit-terra | 0.23.3 |
qiskit-aer | 0.12.0 |
qiskit-ibmq-provider | 0.20.2 |
qiskit | 0.42.1 |
System information | |
Python version | 3.10.10 |
Python compiler | GCC 12.2.1 20230201 |
Python build | main, Mar 5 2023 22:26:53 |
OS | Linux |
CPUs | 32 |
Memory (Gb) | 125.66083908081055 |
Thu May 04 15:38:15 2023 EDT |
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.
[ ]: