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

An interesting class of optimization problems to be addressed by quantum computing are Quadratic Unconstrained Binary Optimization (QUBO) problems. Finding the solution to a QUBO is equivalent to finding the ground state of a corresponding Ising Hamiltonian, which is an important problem not only in optimization, but also in quantum chemistry and physics. For this translation, the binary variables taking values in \(\{0, 1\}\) are replaced by spin variables taking values in \(\{-1, +1\}\), which allows to replace the resulting spin variables by Pauli Z matrices, and thus, an Ising Hamiltonian. For more details on this mapping we refer to [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.