Note

Cette page a été générée à partir de tutorials/algorithms/08_grover_examples.ipynb.

Exécuter en mode interactif dans le IBM Quantum lab.

Exemples avec l’algorithme de Grover

Ce bloc-notes présente des exemples montrant comment utiliser l’algorithme de recherche Qiskit `Grover <https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.Grover.html>”__, en utilisant différents oracles.

import pylab
import numpy as np
from qiskit import BasicAer
from qiskit.tools.visualization import plot_histogram
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components.oracles import LogicalExpressionOracle, TruthTableOracle

Trouver des solutions aux problèmes 3-SAT

Examinons un exemple de probleme de satisfaction 3-SAT et la façon dont nous pouvons utiliser l’algorithme de recherche quantique pour trouver ses solutions. Les problèmes 3-SAT sont habituellement exprimés dans le format Conjonctive Normal Forms (CNF) et écrit dans le format DIMACS-CNF <http://www.satcompetition.org/2009/format-benchmarks2009.html> __. Par exemple :

input_3sat_instance = '''
c example DIMACS-CNF 3-SAT
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
'''

Le CNF de cette instance 3-SAT contient 3 variables et 5 clauses :

\((\neg v_1 \vee \neg v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee v_3) \wedge (v_1 \vee v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee \neg v_3) \wedge (\neg v_1 \vee v_2 \vee v_3)\)

On peut vérifier que l’instance 3-SAT présente trois solutions satisfaisantes :

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((T, T, F)\)

Ou, exprimée à l’aide de la notation DIMACS :

1 -2 3, ou -1 -2 -3, ou 1 2 -3.

Avec cet exemple d’entrée de problème, nous créons ensuite l”oracle correspondant pour notre recherche Grover. En particulier, nous utilisons le composant LogicalExpressionOracle, qui prend en charge l’analyse syntaxique des chaînes de format DIMACS-CNF et la construction du circuit oracle correspondant.

oracle = LogicalExpressionOracle(input_3sat_instance)

L”oracle peut désormais être utilisé pour créer une instance de Grover:

grover = Grover(oracle)

Nous pouvons alors configurer le backend et exécuter l’instance de Grover pour obtenir le résultat :

backend = BasicAer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
result = grover.run(quantum_instance)
print(result.assignment)

[1, 2, -3]

Comme on l’a vu ci-dessus, une solution satisfaisante au problème du 3-SAT est obtenue, et c’est en effet l’une des trois solutions satisfaisantes.

Puisque nous avons utilisé le 'qasm_simulator', le résultat de la mesure est également retourné, comme indiqué dans le graphique ci-dessous, où il peut être vu que les chaînes binaires 000, 011, et 101 (notez l’ordre des bits dans chaque chaîne), correspondant aux trois solutions satisfaisantes ont toutes des probabilités élevées associées avec elles.

plot_histogram(result.measurement)

Expressions Logiques Booléennes

Grover peut également être utilisé pour effectuer une recherche quantique sur un Oracle construit à partir d’autres moyens, en plus de DIMACS. Par exemple, LogicalExpressionOracle peut en fait être configuré à l’aide d’expressions logiques booléennes arbitraires, comme indiqué ci-dessous.

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
oracle = LogicalExpressionOracle(expression)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

Dans l’exemple ci-dessus, l’expression logique en entrée Booléenne '(w ^ x) & ~(y ^ z) & (x & y & z)' devrait être assez explicite, où les opérateurs ^, ~ et & représentent respectivement les opérateurs Boolean logical XOR, NOT et AND. Il devrait être assez facile de trouver la solution satisfaisante en examinant ses composantes : w ^ x nécéssite que w et x aient des valeurs différents ; ~(y ^ z) impose que que y et z aient la même valeur; x & y & z impose que les trois valeurs soient à True. En combinant ces trois contraintes nous obtenons la solution satisfaisante (w, x, y, z) = (False, True, True, True), an accord avec notre résultat obtenu avec Grover.

Oracles à Table de Vérité

Avec Qiskit, les `` Oracle``s peuvent également être construit à partir de tables de vérité, ce qui signifie que nous pouvons également effectuer des recherches quantiques sur les tables de vérité. Même si cela peut sembler un point sans objet puisque nous rechererions essentiellement des entrées d’une table de vérité avec la valeur \(1\), c’est un bon exemple à des fins de démonstration.

truthtable = '1000000000000001'

Comme indiqué, la valeur truthtable est spécifiée avec une chaîne de bits contenant les valeurs de toutes les entrées de la table. Il a une longueur de \(16\), donc la table de vérité correspondante a \(4\) bits en entrée. Etant donné que les toutes premières et dernières valeurs sont \(1\), les entrées de la table de vérité correspondante sont 0000 et 1111.

Ensuite, nous pouvons configurer les objets Oracle et Grover pour effectuer l’algorithme de recherche quantique.

oracle = TruthTableOracle(truthtable)
grover = Grover(oracle)
result = grover.run(QuantumInstance(BasicAer.get_backend('qasm_simulator'), shots=1024))
plot_histogram(result.measurement)

Comme nous l’avons vu dans le graphique ci-dessus, le résultat de la recherche coïncide avec nos attentes.

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
Qiskit	0.23.0
Terra	0.16.0
Aer	0.7.0
Ignis	0.5.0
Aqua	0.8.0
IBM Q Provider	0.11.0
System information
Python	3.6.1 |Continuum Analytics, Inc.| (default, May 11 2017, 13:09:58) [GCC 4.4.7 20120313 (Red Hat 4.4.7-1)]
OS	Linux
CPUs	1
Memory (Gb)	5.827335357666016
Sun Nov 08 17:26:36 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.