Nota

Esta página foi gerada, a partir do tutorials/algorithms/08_grover_examples.ipynb.

Execute interativamente no IBM Quantum lab.

Exemplos do algoritmo de Grover

Este notebook tem exemplos demonstrando como usar o algoritmo de busca de Grover do Qiskit com diferentes oráculos.

import pylab
import numpy as np
from qiskit import BasicAer
from qiskit.tools.visualization import plot_histogram
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle, TruthTableOracle

Encontrando soluções para problemas de 3-SAT

Vamos olhar um exemplo de problema de 3-Satisfiability (3-SAT) e avançar em como podemos usar a Busca Quântica para encontrar as soluções satisfatórias. Problemas de 3-SAT geralmente são expressos em Formulários Normais Conjuntivos (CNF) e escritos no formato DIMACS-CNF. Por exemplo:

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:

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

Pode-se verificar que esta instância do problema de 3-SAT tem três soluções satisfatórias:

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((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 entrada do problema, criamos então o oracle correspondente para a nossa busca de Grover. Em particular, utilizamos a componente LogicalExpressionOracle, que suporta a interpretação de strings no formato DIMACS-CNF e a construção do circuito do oráculo correspondente.

oracle = LogicalExpressionOracle(input_3sat_instance)

O oracle agora pode ser usado para criar uma instância de Grover:

grover = Grover(oracle)

Podemos, então, configurar o backend e executar a instância de Grover para obter o resultado:

backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = grover.run(quantum_instance)
print(result.assignment)

[1, 2, -3]

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 'qasm_simulator', o resultado completo da medição também é retornado, como mostrado no gráfico abaixo, onde pode ser visto que as strings binárias 000, 011, e 101 (note a ordem dos bits em cada string) correspondetes às três soluções satisfatórias têm todas altas probabilidades associadas a elas.

plot_histogram(result.measurement)

Expressões Lógicas Booleanas

O Grover do Qiskit também pode ser usado para executar a Busca Quântica em um Oracle construído a partir de outros meios, além de DIMACS. Por exemplo, o LogicalExpressionOracle pode na verdade ser configurado usando expressões lógicas Booleanas arbitrárias, como demonstrado abaixo.

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

No exemplo acima, a expressão lógica booleana de entrada '(w ^ x) & ~(y ^ z) & (x & y & z)' deve ser bastante auto-explicativa, onde ^, ~ e & representam os operadores booleanos XOR, NOT e AND respectivamente. Deve ser 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 o mesmo; 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.

Oráculos TruthTable

Com Qiskit, Oracle s também podem ser construídos a partir de tabelas verdade, significando que também podemos realizar a Busca Quântica em tabelas verdade. Ainda que isso possa parecer um ponto discutível já que nós estaremos essencialmente buscando entradas de uma tabela verdade com o valor \(1\), é um bom exemplo para fins demonstrativos.

truthtable = '1000000000000001'

Como mostrado, a truthtable é especificada com uma bitstring contendo valores de todas as entradas na tabela. Ela tem tamanho \(16\), então a tabela de verdade correspondente tem \(4\) bits de entrada. Como o primeiro e o último valor são \(1\), as entradas alvo da tabela verdade são 0000 e 1111.

Em seguida, podemos configurar os objetos Oracle e Grover para executar a Busca Quântica como de costume.

oracle = TruthTableOracle(truthtable)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

Como visto no gráfico acima, o resultado da pesquisa coincide com nossas expectativas.

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.23.0
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.0
IBM Q Provider	0.11.0
System information
Python	3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OS	Linux
CPUs	1
Memory (Gb)	5.827335357666016
Sun Nov 08 17:26:36 2020 EST

This code is a part of Qiskit

© Copyright IBM 2017, 2020.

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.