Nota

Esta página foi gerada a partir do ‘tutoriais/otimizacao/4_otimizador_grover.ipynb’__.

Execute interativamente no IBM Quantum lab.

Otimizador de Grover

Introdução

O GAS (Grover Adaptive Search) tem sido explorado como uma possível solução para problemas de otimização combinatória, ao lado de algoritmos variacionais como o VQE (Variational Quantum Eigensolver) e o QAOA (Quantum Aproximaximate Optimization Algorithm). O algoritmo aplica iterativamente Grover Search para encontrar o valor ótimo de uma função objetivo, ao utilizar o melhor valor conhecido da execução anterior como um limitante. O oráculo adaptado usado no GAS reconhece todos os valores acima ou abaixo do limitante atual (para máximo e mínimo respectivamente), diminuindo o tamanho do espaço de busca a cada iteração o limitante é atualizado, até que seja encontrado um valor ótimo.

Neste notebook exploraremos cada componente do ` ` GroverOptimizer ` `, que utiliza as técnicas descritas no GAS, minimizando um problema do QUBO (Quadratic Unconstrained Binary Optimization), conforme descrito em [1]

Referências

[1] A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization, arXiv preprint arXiv:1912.04088 (2019).

Busca Adaptativa de Grover

A busca de Grover, elemento principal do GAS, precisa de três ingredientes:

1. Um operador de preparação de estado \(A\) para construir uma superposição de todos os estados no espaço de busca.

2. Operador do oráculo \(O\), que reconhece os estados de interesse e multiplica suas amplitudes por -1.

3. O operador de difusão de Grover \(D\), que multiplica a amplitude do estado de \(|0\rangle_n\), por -1.

Enquanto as implementações de GAS variam em torno de um caso de uso específico, o framework geral ainda segue livremente os passos descritos abaixo.

GroverOptimizer uses QuadraticProgramToNegativeValueOracle para construir \(A_y\) tal que ele prepara um registo de \(n\)-qubit para representar a superposição igual de todos os \(|x\rangle_n\) e um registo de \(m\)-qubit (aproximadamente) que representa o correspondente \(|Q(x)-y\rangle_m\). Em seguida, todos os estados com \((Q (x)-y)\) negativos devem ser sinalizados por \(O_y\). Observe que na implementação discutida, o oráculo operador é efetivamente independente de \(y\), mas este não é um requisito. Para a clareza, nos referiremos ao oráculo como \(O\) quando o oráculo for independente de \(y\).

Por formalidade, QuadraticProgramToNegativeValueOracle constrói um \(A_y\) e \(O\) tal que:

onde :math:` |xrangle` é a codificação binária do número inteiro :math:` x `.

A cada iteração em que o limitante \(y\) é atualizado, adaptamos \(A_y\) tal que os valores da função são deslocados para cima ou para baixo (para mínimos e máximos, respectivamente) por \(y\). Por exemplo, no problema de encontrar o mínimo, como o valor de \(y\) diminui, o espaço de busca (valores negativos) também diminui, até que apenas o valor mínimo permaneça. Um exemplo concreto será explorado na próxima seção.

Encontre o Mínimo de um Problema QUBO usando o otimizador de Grover

A seguir, um exemplo simples de um problema de minimização.

\begin{eqnarray} \min_{x \in \{0, 1\}^3} -2x_1x_3 - x_2x_3 - 1x_1 + 2x_2 - 3x_3. \end{eqnarray}

Para as nossas etapas iniciais, criamos um modelo de docplex que define o problema acima e, em então, utilize a função from_docplex () para converter o modelo em um QuadraticProgram, que pode ser usado para representar um QUBO na Otimização do Qiskit.

from qiskit.aqua.algorithms import NumPyMinimumEigensolver
from qiskit.optimization.algorithms import GroverOptimizer, MinimumEigenOptimizer
from qiskit.optimization.problems import QuadraticProgram
from qiskit import BasicAer
from docplex.mp.model import Model

backend = BasicAer.get_backend('statevector_simulator')

model = Model()
x0 = model.binary_var(name='x0')
x1 = model.binary_var(name='x1')
x2 = model.binary_var(name='x2')
model.minimize(-x0+2*x1-3*x2-2*x0*x2-1*x1*x2)
qp = QuadraticProgram()
qp.from_docplex(model)
print(qp.export_as_lp_string())

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: docplex_model1

Minimize
 obj: - x0 + 2 x1 - 3 x2 + [ - 4 x0*x2 - 2 x1*x2 ]/2
Subject To

Bounds
 0 <= x0 <= 1
 0 <= x1 <= 1
 0 <= x2 <= 1

Binaries
 x0 x1 x2
End

Em seguida, criamos um GroverOptimizer que usa 6 qubits para codificar o valor, e terminará depois que houver 10 iterações de GAS sem progresso (ou seja, o valor de \(y\) não muda). A função solve() recebe o QuadraticProgram que criamos anteriormente, e retorna um objeto resultante que contém informações sobre a execução.

grover_optimizer = GroverOptimizer(6, num_iterations=10, quantum_instance=backend)
results = grover_optimizer.solve(qp)
print("x={}".format(results.x))
print("fval={}".format(results.fval))

x=[1 0 1]
fval=-6.0

Este resultado é a solução ótima \(x_0=1\), \(x_1=0\), \(x_2=1\) e o valor objetivo de \(-6\) (na maioria das vezes, considerando que é um algoritmo randomizado). Posteriormente, uma visualização customizada do estado quântico mostra uma possível execução de GroverOptimizer aplicada a este QUBO.

Cada gráfico mostra uma única iteração do GAS, com os valores atuais de \(r\) (= contador de iteração) e \(y\) (= limite/deslocamento) mostrado no título. O eixo X exibe o equivalente inteiro da entrada (por exemplo, ‘101’ \(\rightarrow\) 5), e o eixo Y mostra os possíveis valores da função. Como existem 3 variáveis binárias, há \(2^3=8\) possíveis soluções, que são mostradas em cada gráfico. A intensidade da cor indica a probabilidade de medir um determinado resultado (com a maior intensidade de brilho sendo a mais alta), enquanto que a própria cor indica a fase correspondente (veja a roda de cores da fase abaixo). Observe que conforme \(y\) diminui, nós deslocamos todos os valores para cima por essa quantidade, significando que há cada vez menos valores negativos na distribuição, até que apenas um permaneça (o mínimo).

Verifique se o otimizador de Grover encontra o valor correto

Podemos verificar se o algoritmo está funcionando corretamente usando o MinimumEigenOptimizer no Qiskit.

exact_solver = MinimumEigenOptimizer(NumPyMinimumEigensolver())
exact_result = exact_solver.solve(qp)
print("x={}".format(exact_result.x))
print("fval={}".format(exact_result.fval))

x=[1. 0. 1.]
fval=-6.0

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.20.0
Terra	0.15.1
Aer	0.6.1
Ignis	0.4.0
Aqua	0.7.5
IBM Q Provider	0.8.0
System information
Python	3.8.5 (default, Jul 21 2020, 10:48:26) [Clang 11.0.3 (clang-1103.0.32.62)]
OS	Darwin
CPUs	2
Memory (Gb)	8.0
Wed Aug 12 19:54:42 2020 JST

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.