Nota

Esta página foi gerada a partir do tutoriais/otimizacao/3_minimum_eigen_optimizer.ipynb.

Execute interativamente no IBM Quantum lab.

Otimizador Eigen mínimo

Introdução

Uma interessante classe de problemas de otimização a serem abordados pela computação quântica são problemas de Otimização Quadrática Binária Irrestrita (QUBO). Encontrar a solução para um QUBO é equivalente a encontrar o estado fundamental de um Hamiltoniano de Ising correspondente, que é um problema importante não só na otimização, mas também na química quântica e na física. Para abordar esse tipo de problema, considera-se que as variáveis binárias com valores de \(\{0, 1\}\) são substituídas por variáveis spin tomando valores em \(\{-1, +1\}\), o que permite substituir as variáveis spin resultantes por matrizes de Pauli Z, e assim, um Hamiltoniano de Ising. Para obter mais detalhes sobre este mapeamento nós nos embasamos em [1].

Qiskit fornece conversão automática a partir de um QuadraticProgram adequado a um Hamiltoniano de Ising, que em seguida permite alavancar todos os MinimumEigenSolver tais como - VQE, - QAOA, ou - NumpyMinimumEigensolver (método exato clássico).

Qiskit fornece a tradução para um Hamiltoniano de Ising (no Qiskit Aqua também chamado de Operator), a chamada a um MinimumEigensolver, bem como a tradução dos resultados de volta para OptimizationResult no MinimumEigenOptimizer.

A seguir ilustramos primeiro a conversão de um QuadraticProgram para um Operator e, em seguida, mostramos como utilizar o MinimumEigenOptimizer com diferentes MinimumEigensolver para resolver um dado QuadraticProgram. Os algoritmos em Qiskit automaticamente tentam converter um determinado problema para a classe de problema suportado se possível, por exemplo, o MinimumEigenOptimizer irá traduzir automaticamente variáveis inteiras para variáveis binárias ou adicionar restrições lineares de igualdade como um termo de penalidade quadrática para o objetivo. Deve-se mencionar que Aqua lançará um QiskitOptimizationError se for tentada a conversão de um programa quadrático com variável inteira.

A profundidade do circuito de QAOA potencialmente tem de ser aumentada com o tamanho do problema, o que pode ser proibitivo para dispositivos quânticos de curto prazo. Uma possível solução alternativa é a QAOA Recursiva, como introduzido em [2]. O Qiskit generaliza este conceito para o RecursiveMinimumEigenOptimizer, que é introduzido no final deste tutorial.

Referências

[1] A. Lucas, Ising formulations of many NP problems, Front. Phys., 12 (2014).

[2] S. Bravyi, A. Kliesch, R. Koenig, E. Tang, Obstacles to State Preparation and Variational Optimization from Symmetry Protection, arXiv preprint arXiv:1910.08980 (2019).

Convertendo um QUBO para um Operador

from qiskit import BasicAer
from qiskit.aqua import aqua_globals, QuantumInstance
from qiskit.aqua.algorithms import QAOA, NumPyMinimumEigensolver
from qiskit.optimization.algorithms import MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer
from qiskit.optimization import QuadraticProgram

# create a QUBO
qubo = QuadraticProgram()
qubo.binary_var('x')
qubo.binary_var('y')
qubo.binary_var('z')
qubo.minimize(linear=[1,-2,3], quadratic={('x', 'y'): 1, ('x', 'z'): -1, ('y', 'z'): 2})
print(qubo.export_as_lp_string())

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

Minimize
 obj: x - 2 y + 3 z + [ 2 x*y - 2 x*z + 4 y*z ]/2
Subject To

Bounds
 0 <= x <= 1
 0 <= y <= 1
 0 <= z <= 1

Binaries
 x y z
End

A seguir traduzimos este QUBO em um operador de Ising. Isso resulta não apenas em um Operator mas também em um deslocamento constante a ser levado em conta para deslocar o valor resultante.

op, offset = qubo.to_ising()
print('offset: {}'.format(offset))
print('operator:')
print(op)

offset: 1.5
operator:
SummedOp([
  -0.5 * IIZ,
  0.25 * IZI,
  -1.75 * ZII,
  0.25 * IZZ,
  -0.25 * ZIZ,
  0.5 * ZZI
])

Às vezes, um QuadraticProgram também pode ser dado diretamente na forma de um Operator. Para tais casos, o Qiskit também fornece um conversor de um Operator de volta a um QuadraticProgram, que ilustramos a seguir.

qp=QuadraticProgram()
qp.from_ising(op, offset, linear=True)
print(qp.export_as_lp_string())

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

Minimize
 obj: x_0 - 2 x_1 + 3 x_2 + [ 2 x_0*x_1 - 2 x_0*x_2 + 4 x_1*x_2 ]/2
Subject To

Bounds
 0 <= x_0 <= 1
 0 <= x_1 <= 1
 0 <= x_2 <= 1

Binaries
 x_0 x_1 x_2
End

Este conversor permite, por exemplo, traduzir um Operator para um QuadraticProgram e, em seguida, resolver o problema com outros algoritmos que não se baseiam na representação do Hamiltoniano de Ising, como o GroverOptimizer.

Resolvendo um QUBO com o MinimumEigenOptimizer

Iniciamos inicializando o MinimumEigensolver que queremos utilizar.

aqua_globals.random_seed = 10598
quantum_instance = QuantumInstance(BasicAer.get_backend('statevector_simulator'),
                                   seed_simulator=aqua_globals.random_seed,
                                   seed_transpiler=aqua_globals.random_seed)
qaoa_mes = QAOA(quantum_instance=quantum_instance, initial_point=[0., 0.])
exact_mes = NumPyMinimumEigensolver()

Em seguida, utilizamos o MinimumEigensolver para criar o MinimumEigenOptimizer.

qaoa = MinimumEigenOptimizer(qaoa_mes)   # using QAOA
exact = MinimumEigenOptimizer(exact_mes)  # using the exact classical numpy minimum eigen solver

Utilizamos primeiramente o MinimumEigenOptimizer baseado no NumPyMinimumEigensolver clássico exato para obter a solução de referência ideal para este pequeno exemplo.

exact_result = exact.solve(qubo)
print(exact_result)

optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS

A seguir, aplicamos o MinimumEigenOptimizer baseado no QAOA para o mesmo problema.

qaoa_result = qaoa.solve(qubo)
print(qaoa_result)

optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS

RecursiveMinimumEigenOptimizer

O RecursiveMinimumEigenOptimizer recebe um MinimumEigenOptimizer como entrada e aplica o esquema de otimização recursiva para reduzir o tamanho do problema uma variável de cada vez. Uma vez que o tamanho do problema intermediário gerado esteja abaixo de um determinado limite (min_num_vars), o RecursiveMinimumEigenOptimizer utiliza outro solucionador (min_num_vars_optimizer), por exemplo, um solucionador clássico exato como o CPLEX ou o MinimumEigenOptimizer baseado no NumPyMinimumEigensolver.

A seguir, mostramos como usar o RecursiveMinimumEigenOptimizer usando os dois MinimumEigenOptimizer introduzidos antes.

Primeiramente, nós construímos o RecursiveMinimumEigenOptimizer que reduz o tamanho do problema de 3 variáveis para 1 variável e depois usa o solucionador exato para a última variável. Então chamamos solve para otimizar o problema considerado.

rqaoa = RecursiveMinimumEigenOptimizer(min_eigen_optimizer=qaoa, min_num_vars=1, min_num_vars_optimizer=exact)

rqaoa_result = rqaoa.solve(qubo)
print(rqaoa_result)

optimal function value: -2.0
optimal value: [0. 1. 0.]
status: SUCCESS

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	None
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.1
IBM Q Provider	0.10.0
System information
Python	3.7.4 (default, Aug 13 2019, 15:17:50) [Clang 4.0.1 (tags/RELEASE_401/final)]
OS	Darwin
CPUs	2
Memory (Gb)	12.0
Wed Nov 11 11:22:40 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.