Exemples d’algorithme de Grover¶

Ce notebook présente des exemples montrant comment utiliser l’algorithme de recherche de Grover de Qiskit, en utilisant différents oracles.

Trouver des solutions à des problèmes 3-SAT¶

Examinons un exemple de problème 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 par une Forme normale conjonctive (FNC) et écrit dans le format DIMACS-CNF <http://www.satcompetition.org/2009/format-benchmarks2009.html> __. Par exemple :

[1]:

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 cette instance 3-SAT admet trois solutions satisfaisantes :

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

Ou, utilisant la notation DIMACS-CNF :

1 -2 3, or -1 -2 -3, or 1 2 -3.

En utilisant cet exemple de problème, nous créons ensuite l”oracle correspondant pour notre recherche par algorithme de Grover. En particulier, nous utilisons la classe PhaseOracle, qui prend en charge l’analyse syntaxique des chaînes de caractères au format DIMACS-CNF et la construction du circuit de l’oracle correspondant.

[2]:

import os
import tempfile
from qiskit.exceptions import MissingOptionalLibraryError
from qiskit.circuit.library.phase_oracle import PhaseOracle


fp = tempfile.NamedTemporaryFile(mode='w+t', delete=False)
fp.write(input_3sat_instance)
file_name = fp.name
fp.close()
oracle = None
try:
    oracle = PhaseOracle.from_dimacs_file(file_name)
except ImportError as ex:
    print(ex)
finally:
    os.remove(file_name)

"The 'tweedledum' library is required to use 'classical function oracles'. You can install it with 'pip install tweedledum'."

La variable oracle peut alors être utilisée pour créer une instance d’un problème de Grover :

[3]:

from qiskit.algorithms import AmplificationProblem

problem = None
if oracle is not None:
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)

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

[4]:

from qiskit.algorithms import Grover
from qiskit.primitives import Sampler

grover = Grover(sampler=Sampler())
result = None
if problem is not None:
    result = grover.amplify(problem)
    print(result.assignment)

Comme on l’a vu ci-dessus, la solution renvoyée est bien l’une des trois solutions satisfaisantes admises par notre problème.

Puisque nous avons utilisé le Sampler, le résultat de la mesure est également retourné, comme indiqué dans le graphique ci-dessous, où l’on voit que les chaînes binaires 000, 011, et 101 (notez l’ordre des bits dans chaque chaîne), correspondant aux trois solutions satisfaisantes qui sont toutes associées à des probabilités élevées.

[5]:

from qiskit.tools.visualization import plot_histogram

if result is not None:
    display(plot_histogram(result.circuit_results[0]))

Expressions logiques booléennes¶

La classe Grover de Qiskit peut également être utilisée pour effectuer une recherche quantique sur un Oracle construit à partir d’autres moyens, en plus d’une chaîne de caractères au format DIMACS-CNF. Par exemple, il est possible de configurer le PhaseOracle à l’aide d’expressions logiques booléennes arbitraires, comme montré ci-dessous.

[6]:

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
    grover = Grover(sampler=Sampler())
    result = grover.amplify(problem)
    display(plot_histogram(result.circuit_results[0]))
except MissingOptionalLibraryError as ex:
    print(ex)

"The 'tweedledum' library is required to use 'PhaseOracle'. You can install it with 'pip install tweedledum'."

Dans l’exemple ci-dessus, l’expression booléenne logique en entrée '(w ^ x) & ~(y ^ z) & (x & y & z)' devrait être assez explicite, où les opérateurs ^, ~ et & représentent respectivement les opérateurs logiques XOR, NON et ET. Il devrait être assez facile de trouver la solution satisfaisante en examinant ses composantes : w ^ x nécessite 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), ce qui est en accord avec notre résultat obtenu avec Grover.

[7]:

import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
`qiskit-terra`	0.23.3
`qiskit-aer`	0.12.0
`qiskit-ibmq-provider`	0.20.2
`qiskit`	0.42.1
System information
Python version	3.10.10
Python compiler	GCC 12.2.1 20230201
Python build	main, Mar 5 2023 22:26:53
OS	Linux
CPUs	32
Memory (Gb)	125.66083908081055
Thu May 04 15:38:15 2023 EDT

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.

[ ]: