French
Languages
English
Bengali
French
German
Japanese
Korean
Portuguese
Spanish
Tamil

Note

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

Algorithme de Grover et Amplification d’Amplitude

L’algorithme de Grover est l’un des algorithmes quantiques les plus célèbres introduits par Lov Grover en 1996 [1]. Il a d’abord été proposé pour des problèmes de recherche non structurés, c’est-à-dire pour trouver un élément marqué dans une base de données non structurée. Cependant, l’algorithme de Grover est maintenant une sous-routine de plusieurs autres algorithmes, tels que Grover Adaptive Search [2]. Pour les détails de l’algorithme de Grover, veuillez consulter Grover’s Algorithm dans le manuel Qiskit.

Qiskit implémente l’algorithme de Grover dans la classe Grover. Cette classe inclut également la version généralisée, Amplitude Amplification [3], et permet de définir des itérations individuelles et d’autres méta-paramètres à l’algorithme de Grover.

Références :

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

Algorithme de Grover

L’algorithme de Grover utilise l’opérateur Grover \(\mathcal{Q}\) pour amplifier les amplitudes des bons états :

\[\mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^ \dagger \mathcal{S_f}\]

Ici, * :math:` mathcal{A}` est l’état de recherche initial de l’algorithme, qui est juste un état de superposition de tous les qubits d’entrée obtenu par \(H ^ {\otimes n}\) pour la recherche de Grover générale, mais peut être plus élaboré pour l’amplification d’amplitude * :math:` mathcal{S_0}` est la réflexion par rapport à l’état où tous les qubits sont à l’état 0

\[\begin{split}|x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rAngle, &x = 0 \end{cases}\end{split}\]

*:math:mathcal{S_f} est l’oracle qui s’applique

\[|x\rangle \mapsto (-1)^{f(x)}|x\rangle\]

\(f (x)\) vaut 1 si \(x\) est un état recherché et sinon 0.

En un mot, l’algorithme de Grover applique différentes puissances de \(\mathcal{Q}\) et après chaque exécution vérifie si une bonne solution a été trouvée.

Exécution de l’algorithme de Grover

Pour exécuter l’algorithme de Grover à l’aide de la classe Grover, premièrement, nous devons spécifier un oracle. Dans l’exemple suivant, nous utilisons une instance de la classe QuantumCircuit comme oracle de l’algorithme de Grover. Cependant, il existe plusieurs autres classes que nous pouvons utiliser comme oracle. Nous en parlons plus loin dans ce tutoriel.

Notez que l’oracle de Grover doit être un oracle de phase-flip. En d’autres termes, il multiplie les amplitudes des états recherchés par un facteur \(-1\). Nous expliquons plus tard comment convertir un oracle de type bit-flip en oracle de type phase-flip.

[1]:
from qiskit import QuantumCircuit
from qiskit.algorithms import AmplificationProblem

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
problem = AmplificationProblem(oracle, is_good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
# (Algorithm circuits are wrapped in a gate to be appear in composition as a block
# so we have to decompose() the op to see it expanded into its component gates.)
problem.grover_operator.decompose().draw(output='mpl')
[1]:
../../_images/tutorials_algorithms_06_grover_2_0.png

Ensuite, nous spécifions un backend et nous appelons la méthode run de Grover. Le type de résultat renvoyé est un GroverResult.

Si la recherche a réussi, l’attribut oracle_evaluation du résultat sera True. Dans ce cas, la mesure la plus fréquemment obtenue, top_measurement, est l’un des états recherchés. Sinon, oracle_evaluation sera False.

[2]:
from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit.algorithms import Grover

aer_simulator = Aer.get_backend('aer_simulator')
grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)
Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

Dans cet exemple, le résultat de top_measurement est 11 qui est l’état recherché. Ainsi, nous avons réussi à trouver la réponse en utilisant Grover.

Utiliser les différents types de classes comme oracle de Grover

Dans l’exemple ci-dessus, nous avons utilisé la classe QuantumCircuit comme l’oracle de Grover. Cependant, nous pouvons également utiliser qiskit.aqua.components.oracles.Oracle, et qiskit.quantum_info.Statevector comme oracles. Dans les exemples suivants, l’état recherché est \(| 11\rangle\)

[3]:
from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=['11'])

grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)
Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

En interne, le vecteur d’état est projeté sur circuit quantique :

[4]:
problem.grover_operator.oracle.decompose().draw(output='mpl')
[4]:
../../_images/tutorials_algorithms_06_grover_9_0.png

Qiskit permet de construire facilement des oracles plus complexes: * PhaseOracle : pour l’analyse d’expressions logiques telles que '~ a | b'. Ceci est particulièrement utile pour résoudre les problèmes 3-SAT et est démontré dans le tutoriel  » Grover Exemples <07_grover_examples.ipynb> ` __.

Dans cet exemple simple, nous allons utiliser PhaseOracle pour trouver l’état \(| 11\rangle\), qui correspond à 'a & b'.

[5]:
from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit.exceptions import MissingOptionalLibraryError

# `Oracle` (`PhaseOracle`) as the `oracle` argument
expression = '(a & b)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle)
    display(problem.grover_operator.oracle.decompose().draw(output='mpl'))
except MissingOptionalLibraryError as ex:
    print(ex)
../../_images/tutorials_algorithms_06_grover_11_0.png

Nous observons que cet oracle implémente une inversion de phase pour l’état :math:`|11rangle `

Comme mentionné ci-dessus, l’algorithme de Grover nécessite un oracle de phase . Un oracle de bit-flip change l’état d’un qubit auxiliaire si les autres qubits satisfont à la condition. Pour utiliser ces types d’oracles avec Grover’s nous avons besoin de convertir l’oracle de bit-flip à un oracle de phase-flip oracle en prenant en sandwich le qubit auxiliaire de l’oracle de bt-fliip par des portes \(X\) et \(H\).

Note: Cette transformation d’un oracle de bit-flip en oracle de phase-flip est valable en general et vous pouvez l’utiliser pour convertir votre oracle vers la bonne représentation.

Amplification de l’amplitude

L’algorithme de Grover utilise des portes de Hadamard pour créer la superposition uniforme de tous les états au début de l’opérateur de Grover \(\mathcal{Q}\). Si certaines informations sur les états recherchés sont disponibles, il peut être utile de ne pas démarrer dans une superposition uniforme mais d’initialiser uniquement des états spécifiques. Cette version, généralisée, de l’algorithme de Grover est appelée Amplification d’Amplitude.

Dans Qiskit, l’état de superposition initial peut facilement être ajusté en définissant l’argument state_preparation.

Préparation de l’état

Un argument state_preparation est utilisé pour spécifier un circuit quantique préparant un état quantique pour le point de départ de l’amplification de l’amplitude. Par défaut, un circuit avec \(H^{\otimes n}\) est utilisé pour préparer une superposition uniforme (ce sera donc l’algorithme de Grover). Le circuit de diffusion de l’amplification d’amplitude est généré automatiquement par state_preparation.

[6]:
import numpy as np

# Specifying `state_preparation`
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.h(2)
oracle.ccx(0,1,2)
oracle.h(2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
problem = AmplificationProblem(oracle, state_preparation=state_preparation, is_good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
problem.grover_operator.state_preparation.draw(output='mpl')
state preparation circuit:
[6]:
../../_images/tutorials_algorithms_06_grover_14_1.png
[7]:
grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)
Success!
Top measurement: 111

Flexibilité totale

Pour une utilisation plus avancée, il est également possible de spécifier l’opérateur Grover en définissant l’argument grover_operator. Cela peut être utile si vous connaissez une implémentation plus efficace pour \(\mathcal{Q}\) que la construction par défaut via la réflexion zéro, l’oracle et la préparation de l’état.

La classe qiskit.circuit.library.GroverOperator peut être un bon point de départ et offre plus d’options pour une construction automatisée de l’opérateur de Grover. Vous pouvez par exemple * définir le mcx_mode * ignorer les qubits dans la réflexion autour de zéro en définissant reflection_qubits * explicitement échanger les opérations \(\mathcal{S_f}, \mathcal{S_0}\) et \(\mathcal{A}\) à l’aide des arguments oracle, zero_reflection et state_preparation

Par exemple, imaginez que le bon état soit l’état à trois qubits \(|111\rangle\) et que nous ayons utilisé 2 qubits supplémentaires en tant que qubits auxiliaires.

[8]:
from qiskit.circuit.library import GroverOperator, ZGate

oracle = QuantumCircuit(5)
oracle.append(ZGate().control(2), [0, 1, 2])
oracle.draw(output='mpl')
[8]:
../../_images/tutorials_algorithms_06_grover_18_0.png

Alors, par défaut, l’opérateur Grover implémentera la réflexion autour de zéro sur les cinq qubits.

[9]:
grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.decompose().draw(output='mpl')
[9]:
../../_images/tutorials_algorithms_06_grover_20_0.png

Mais nous savons que nous devons seulement considérer les trois premiers :

[10]:
grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.decompose().draw(output='mpl')
[10]:
../../_images/tutorials_algorithms_06_grover_22_0.png

Détails sur d’autres arguments de Grover

Grover admet des arguments autres que oracle et state_preparation. Nous les expliquerons dans cette section.

Spécification de good_state

good_state est utilisé pour vérifier si le résultat de mesure est correct ou non. Il peut s’agir d’une liste de chaînes binaires, d’une liste de nombres entiers, d’une instance de Statevector ou d’un Callable. Si l’entrée est une liste de chaînes de binaire, chaque chaîne de la liste représente un état correct à rechercher. Si l’entrée est une liste d’entiers, chaque entier représente l’indice du qubit qui doit être à \(|1\rangle\). S’il s’agit d’une instance de Statevector``alors tous les états à rechercher doivent être en superposition dans l'instance de ``Statevector passée.

[11]:
# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))
True
[12]:
# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))
True
[13]:
from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))
True
[14]:
# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))
True

Le nombre d’itérations (iteration)

Le nombre de répétitions d’application de l’opérateur Grover est important pour obtenir le résultat correct avec l’algorithme de Grover. Le nombre d’itérations peut être défini par l’argument iteration de Grover. Les entrées suivantes sont prises en charge : * un entier pour spécifier le nombre d’itérations de l’opérateur Grover qui doivent être appliquées * ou une liste d’entiers, représentant les itérations de l’opérateur Grover à exécuter consécutivement et entre lesquelles nous pouvons vérifier si une solution correcte a été trouvée

De plus, il y a l’argument sample_from_iterations. Quand il est à True, au lieu d’appliquer le nombre d’itérations spécifiées, un nombre entier aléatoire compris entre 0 et la valeur de iteration est utilisé comme nombre d’itérations de l’opérateur de Grover. Cette approche est utile lorsque nous ne connaissons pas le nombre de solutions.

Pour plus de détails sur l’algorithme utilisant sample_from_iterations, voir [4].

Références :

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

[15]:
# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=1)
[16]:
# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3])
[17]:
# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3], sample_from_iterations=True)

Lorsque le nombre de solutions est connu, nous pouvons également utiliser une méthode statique optimal_num_iterations pour obtenir le nombre optimal d’itérations. Notez que le nombre d’itérations ainsi obtenu est une valeur approximative. Lorsque le nombre de qubits est faible, ce nombre d’itérations peut ne pas être optimal.

[18]:
iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations
[18]:
12

Application du post_processing

Nous pouvons appliquer un post-traitement optionnel à la mesure la plus courante pour faciliter la lecture. Ce post-traitement peut être utilisé, par exemple, pour convertir la représentation binaire de la mesure [ 1, 0, 1 ] à un format DIMACS CNF [ 1, -2, 3 ].

[19]:
def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'], post_processing=to_DIAMACS_CNF_format)
problem.post_processing([1, 0, 1])
[19]:
[1, -2, 3]
[20]:
import qiskit.tools.jupyter
%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
qiskit-terra0.20.0
qiskit-aer0.8.2
qiskit-ignis0.6.0
qiskit-ibmq-provider0.17.0
qiskit-aqua0.9.4
qiskit0.28.0
System information
Python version3.9.7
Python compilerGCC 11.2.0
Python builddefault, Sep 10 2021 14:59:43
OSLinux
CPUs4
Memory (Gb)15.478507995605469
Sun Jan 09 15:41:49 2022 MST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

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.