Optimiseur de Grover¶

Introduction¶

La recherche adaptative de Grover (Grover Adaptive Search : GAS) a été explorée comme une solution possible aux problèmes d’optimisation combinatoire, aux côtés d’algorithmes variationnels tels que Variational Quantum Eigensolver (VQE) et Quantum Approximate Optimization Algorithm (QAOA). L’algorithme applique de façon itérative Grover Search pour trouver la valeur optimale d’une fonction objectif, en utilisant la meilleure valeur issue de l’exécution précédente comme seuil. L’oracle adaptatif utilisé dans GAS reconnaît toutes les valeurs au-dessus ou au-dessous du seuil actuel (respectivement pour max et min), diminuant la taille de l’espace de recherche à chaque itération pour laquelle le seuil est mis à jour, jusqu’à ce qu’un optimum soit trouvé.

Dans ce bloc-notes, nous explorerons chaque composant de GroverOptimizer, qui utilise les techniques décrites dans le GAS, en minimisant un problème de type QUBO (Quadratic Unconstrained Binary Optimization), tel que décrit dans [1]

Références¶

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

Recherche adaptative de Grover¶

Grover Search, l’élément central du GAS, a besoin de trois ingrédients :

Un opérateur de préparation d’état :math:` A ` pour construire une superposition de tous les états dans l’espace de recherche.
Un opérateur oracle :math:` O”, qui reconnaît les états d’intérêt et multiplie leurs amplitudes par -1.
L’opérateur de diffusion Grover :math:` D , qui multiplie l’amplitude du :math:`| 0rangle_n état par -1.

Bien que les implémentations de GAS varient en fonction du cas d’utilisation spécifique, le cadre général suit généralement les étapes décrites ci-dessous.

0d2af95e14a94821bf4fe31b83688a9a

GroverOptimizer utilise l’oracle QuadraticProgramToNegativeValueOracle pour construire \(A_y\) de telle sorte qu’il prépare un registre à \(n\)-qubit pour représenter la superposition égale de tous les états \(|x\rangle_n\) et un registre à \(m\)-qubit pour (approximativement) représenter l’état \(|Q(x)-y\rangle_m\). Ensuite, tous les états avec \((Q(x) - y)\) négatifs devraient être marqués par \(O_y\). Notez que dans l’implémentation discutée, l’opérateur Oracle est en fait indépendant de \(y\), mais ce n’est pas une exigence. Pour plus de clarté, nous appellerons l’oracle \(O\) lorsque l’oracle est indépendant de \(y\).

En termes plus formels, ` ` QuadraticProgramToNegativeValueOracle ` ` construit un :math:` A_y ` et :math:` O ` tel que:

fc8e03e8d47148aeb1a5ed283d50e98f

où l’état \(|x\rangle\) représente l’encodage binaire de l’entier \(x\).

A chaque itération dans laquelle le seuil \(y\) est mis à jour, nous adaptons \(A_y\) de sorte que les valeurs de fonction sont décalées vers le haut ou vers le bas (pour le minimum et le maximum respectivement) par \(y\). Par exemple, dans le contexte de la recherche du minimum, comme la valeur de \(y\) diminue, l’espace de recherche (valeurs négatives) diminue également, jusqu’à ce que seule la valeur minimale reste. Un exemple concret sera examiné dans la prochaine section.

Trouver le minimum d’un problème QUBO en utilisant GroverOptimizer¶

Voici un exemple de taille réduite d’un problème de minimisation.

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

Pour nos étapes initiales, nous créons un modèle docplex qui définit le problème ci-dessus, puis nous utilisons la fonction from_docplex() pour convertir le modèle en un QuadraticProgram, qui peut être utilisé pour représenter un QUBO dans Qiskit Optimisation.

[1]:

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

[2]:

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

Ensuite, nous créons un GroverOptimizer qui utilise 6 qubits pour coder la valeur, et se terminera après 10 itérations de GAS sans progression (c’est-à-dire que la valeur de \(y\) ne change plus). La fonction solve() prend le QuadraticProgram que nous avons créé plus tôt, et renvoie un objet qui contient les résultats de l’exécution.

[3]:

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

Il en résulte la solution optimale \(x_0 = 1\), \(x_1 = 0\), \(x_2 = 1\) et la valeur objective optimale de \(-6\) (la plupart du temps, puisqu’il s’agit d’un algorithme aléatoire). Dans ce qui suit, une visualisation de l’état quantique montre une possible exécution de GroverOptimizer appliqué à ce QUBO.

e862d17049af4d39aee9bfc3a1b4576e

Chaque graphique présente une itération unique de GAS, avec les valeurs actuelles de \(r\) (= compteur d’itération) et \(y\) (= seuil / décalage) figurant dans le titre. L’axe des X affiche l’équivalent entier de l’entrée (par exemple,”101” \(\rightarrow \) solutions possibles, qui sont affichées dans chaque graphique. L’intensité de la couleur indique la probabilité de mesurer un certain résultat (avec une intensité lumineuse étant la plus élevée), tandis que la couleur réelle indique la phase correspondante (voir la roue de couleur de phase ci-dessous). Notez que tant que \(y\) décroît, nous décalons toutes les valeurs de ce montant, ce qui signifie qu’il y a moins de valeurs négatives dans la distribution, jusqu’à ce qu’un seul reste (le minimum).

5a8961d2c7104c2383d11765f29c8bcd

Vérifiez que GroverOptimizer trouve la valeur correcte¶

Nous pouvons vérifier que l’algorithme fonctionne correctement en utilisant MinimumEigenOptimizer dans Qiskit.

[4]:

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

[5]:

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

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.

[ ]: