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

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.

[ ]: