Ejemplos del algoritmo de Grover¶

Este cuaderno tiene ejemplos que demuestran cómo usar el algoritmo de búsqueda de Grover de Qiskit, con diferentes oráculos.

Encontrar soluciones a los problemas 3-SAT¶

Veamos un ejemplo de problema de 3-Satisfabilidad (3-SAT) y veamos cómo podemos usar la búsqueda cuántica para encontrar sus soluciones satisfactorias. Los problemas de 3-SAT generalmente se expresan en Formas normales conjuntivas (Conjunctive Normal Forms, CNF) y se escriben en el formato DIMACS-CNF. Por ejemplo:

[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
'''

El CNF de esta instancia 3-SAT contiene 3 variables y 5 cláusulas:

\((\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)\)

Se puede verificar que esta instancia de problema 3-SAT tiene tres soluciones satisfactorias:

\((v_1, v_2, v_3) = (T, F, T)\) o \((F, F, F)\) o \((T, T, F)\)

O expresado usando la notación DIMACS:

1 -2 3, o -1 -2 -3, o 1 2 -3.

Con esta entrada de problema de ejemplo, creamos el oracle correspondiente para nuestra búsqueda de Grover. En particular, utilizamos el componente PhaseOracle, que admite el análisis de cadenas de formato DIMACS-CNF y la construcción del correspondiente circuito de oráculo.

[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'."

El oracle ahora se puede usar para crear una instancia de Grover:

[3]:

from qiskit.algorithms import AmplificationProblem

problem = None
if oracle is not None:
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)

Luego podemos configurar el backend y ejecutar la instancia de Grover para obtener el 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 se vio anteriormente, se obtiene una solución satisfactoria al problema 3-SAT especificado. Y de hecho es una de las tres soluciones satisfactorias.

Dado que usamos el Sampler, también es devuelto el resultado completo de la medición, como se muestra en la gráfica siguiente, donde se puede ver que las cadenas binarias 000`, 011, y 101 (observa el orden de los bits en cada cadena), correspondientes a las tres soluciones satisfactorias, tienen todas altas probabilidades asociadas.

[5]:

from qiskit.tools.visualization import plot_histogram

if result is not None:
    display(plot_histogram(result.circuit_results[0]))

Expresiones Lógicas Booleanas¶

El Grover de Qiskit también se puede utilizar para realizar búsquedas cuánticas en un Oracle construido a partir de otros medios, además de DIMACS. Por ejemplo, el PhaseOracle se puede configurar utilizando expresiones lógicas booleanas arbitrarias, como se muestra a continuación.

[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'."

En el ejemplo anterior, la expresión lógica booleana de entrada '(w ^ x) & ~(y ^ z) & (x & y & z)' debería ser bastante autoexplicativa, donde ^, ~, y & representan los operadores lógicos booleanos XOR, NOT y AND, respectivamente. Debería ser bastante fácil descubrir la solución satisfactoria examinando sus partes: w ^ x requiere que w y x tomen valores diferentes; ~(y ^ z) requiere que y y z sean iguales; x & y & z dicta que los tres sean True. Al juntarlos, obtenemos la solución satisfactoria (w, x, y, z) = (False, True, True, True), con lo que el resultado de nuestro Grover concuerda.

[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.

[ ]: