Note

Cette page a été générée à partir de tutorials/optimization/3_minimum_eigen_optimizer.ipynb.

Exécuter en mode interactif dans le ` IBM Quantum lab <https://quantum-computing.ibm.com/jupyter/tutorial/optimization/3_minimum_eigen_optimizer.ipynb>` _.

Optimiseur de Valeure Propre Minimale

Introduction

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 propose une conversion automatique de QuadraticProgram vers un hamiltonien d’Ising, qui permet ensuite de tirer parti de tous les MinimumEigenSolver tels que VQE, -QAOA, ou -NumpyMinimumEigensolver (qui est la méthode classique exacte).

Qiskit fournit la traduction vers un Hamiltonien Ising (dans Qiskit Aqua également appelé ` ` Operator ` `), l’appel à un ` ` MinimumEigensolver ` ` ainsi que la traduction des résultats vers ` ` OptimizationResult ` ` dans ` ` MinimumEigenOptimizer ` `.

Dans ce qui suit, nous illustrons d’abord la conversion d’un QuadraticProgram à un Operator, puis montrons comment utiliser MinimumEigenOptimizer avec le MinimumEigensolver pour résoudre un QuadraticProgram donné. Les algorithmes de Qiskit tentent automatiquement de convertir un problème donné en classe d’incident prise en charge si possible, par exemple, le MinimumEigenOptimizer traduira automatiquement les variables entières en variables binaires ou ajoutera une contrainte d’égalité linéaire en tant que terme de pénalité quadratique à l’objectif. Il convient de mentionner que Aqua va passer par une erreur QiskitOptimizationError si la conversion d’un programme quadratique avec une variable entière est tentée.

La profondeur du circuit QAOA pourrait augmenter avec la taille du problème, ce qui pourrait être prohibitif à court terme pour les ordinateurs quantiques. Une solution possible est la QAOA récursive, telle qu’elle a été introduite dans le [2]. Qiskit généralise ce concept à RecursiveMinimumEigenOptimizer, qui est introduit à la fin de ce tutoriel.

Références

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

Conversion d’un QUBO en opérateur

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

Ensuite, nous traduisons ce QUBO en un opérateur Ising. Le résultat consiste non seulement dans un Operator mais aussi dans un décalage constant à prendre en compte pour recaler la valeur résultante.

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
])

Parfois, un QuadraticProgram peut également être donné directement sous la forme d’un Operator. Dans de tels cas, Qiskit fournit un convertisseur depuis un Operator vers un QuadraticProgram, que nous illustrons dans ce qui suit.

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

Ce convertisseur permet, par exemple de traduire un Operator en un QuadraticProgram puis de résoudre le problème avec d’autres algorithmes qui ne sont pas basés sur la représentation d’Ising Hamiltonien, comme le GroverOptimizer.

Résoudre un QUBO avec le MinimumEigenOptimizer

Nous commençons par initialiser le MinimumEigensolver que nous voulons utiliser.

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

Ensuite, nous utilisons le MinimumEigensolver pour créer MinimumEigenOptimizer.

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

Nous utilisons d’abord le MinimumEigenOptimizer basé sur le NumPyMinimumEigensolver classique pour obtenir la solution de benchmark optimale pour ce petit exemple.

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

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

Ensuite, nous appliquons le MinimumEigenOptimizer basé sur QAOA au même problème.

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

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

RecursiveMinimumEigenOptimizer

Le RecursiveMinimumEigenOptimizer prend un MinimumEigenOptimizer en entrée et applique le schéma d’optimisation récursive pour réduire la taille du problème une variable à la fois. Une fois que la taille du problème intermédiaire généré est inférieure à un seuil donné (min_num_vars), le RecursiveMinimumEigenOptimizer utilise un autre solveur (min_num_vars_optimizer) par exemple un solveur classique tel que CPLEX ou le MinimumEigenOptimizer basé sur le NumPyMinimumEigensolver.

Dans ce qui suit, nous montrons comment utiliser le RecursiveMinimumEigenOptimizer en utilisant les deux MinimumEigenOptimizer introduits avant.

Tout d’abord, nous construisons le RecursiveMinimumEigenOptimizer de telle sorte qu’il réduit la taille du problème de 3 variables à 1 variable et utilise ensuite le solveur exact pour la dernière variable. Puis nous appelons solve pour optimiser le problème considéré.

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.