Algorithme de Grover

Estimation d'utilisation : moins d'une minute sur un processeur Eagle r3 (REMARQUE : il ne s'agit que d'une estimation. Ton temps d'exécution peut varier.)

Résultats d'apprentissage

Après avoir suivi ce tutoriel, tu devrais être en mesure de comprendre les éléments suivants :

• Comment construire des oracles de Grover qui marquent un ou plusieurs états de base computationnels
• Comment utiliser la fonction grover_operator() de la bibliothèque de circuits Qiskit
• Comment déterminer le nombre optimal d'itérations de Grover pour un problème donné
• Comment exécuter l'algorithme de Grover à l'aide de la primitive Sampler de Qiskit Runtime

Prérequis

Il est recommandé de se familiariser avec ces sujets :

• Fondamentaux des algorithmes quantiques : algorithme de Grover
• Bases de l'information quantique

Contexte

L'amplification d'amplitude est un algorithme quantique, ou sous-routine, à usage général qui peut être utilisé pour obtenir une accélération quadratique par rapport à plusieurs algorithmes classiques. L'algorithme de Grover a été le premier à démontrer cette accélération sur des problèmes de recherche non structurés. La formulation d'un problème de recherche de Grover nécessite une fonction oracle qui marque un ou plusieurs états de base computationnels comme étant les états que nous souhaitons trouver, ainsi qu'un circuit d'amplification qui augmente l'amplitude des états marqués, supprimant par conséquent les états restants.

Nous montrons ici comment construire des oracles de Grover et utiliser grover_operator() de la bibliothèque de circuits Qiskit pour configurer facilement une instance de recherche de Grover. La primitive Sampler du runtime permet une exécution fluide des circuits de Grover.

Prérequis matériels

Avant de commencer ce tutoriel, assure-toi d'avoir installé les éléments suivants :

• Qiskit SDK v2.0 ou ultérieur, avec le support de visualisation
• Qiskit Runtime v0.22 ou ultérieur (pip install qiskit-ibm-runtime)

Configuration

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib qiskit qiskit-ibm-runtime

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        zero_inds = [
            ind
            for ind in range(num_qubits)
            if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

Exemple à petite échelle sur simulateur

Dans cette section, nous déroulons chaque étape de l'algorithme de Grover à petite échelle à l'aide d'un simulateur local, avant d'exécuter le même problème sur du matériel quantique réel.

Étape 1 : Transposer les entrées classiques en un problème quantique

L'algorithme de Grover nécessite un oracle qui spécifie un ou plusieurs états de base computationnels marqués, où « marqué » signifie un état avec une phase de -1. Une porte Z contrôlée, ou sa généralisation multi-contrôlée sur $N$ qubits, marque l'état $2^{N}-1$ (chaîne de bits '1'*$N$). Marquer des états de base comportant un ou plusieurs '0' dans la représentation binaire nécessite l'application de portes X sur les qubits correspondants avant et après la porte Z contrôlée, ce qui équivaut à avoir un contrôle ouvert sur ce qubit. Dans le code suivant, nous définissons un oracle qui marque un ou plusieurs états de base d'entrée définis par leur représentation en chaîne de bits. La porte MCMT est utilisée pour implémenter la porte Z multi-contrôlée.

Instance spécifique de Grover

Maintenant que nous disposons de la fonction oracle, nous pouvons définir une instance spécifique de la recherche de Grover. Dans cet exemple, nous allons marquer deux états computationnels parmi les huit disponibles dans un espace computationnel à trois qubits :

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Opérateur de Grover

La fonction grover_operator() intégrée à Qiskit prend un circuit oracle et renvoie un circuit composé du circuit oracle lui-même et d'un circuit qui amplifie les états marqués par l'oracle. Ici, nous utilisons la méthode decompose() du circuit pour visualiser les portes au sein de l'opérateur :

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Les applications répétées de ce circuit grover_op amplifient les états marqués, en faisant les chaînes de bits les plus probables dans la distribution de sortie du circuit. Il existe un nombre optimal de telles applications, déterminé par le rapport entre les états marqués et le nombre total d'états computationnels possibles :

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

Circuit de Grover complet

Une expérience de Grover complète commence par une porte Hadamard sur chaque qubit, créant une superposition uniforme de tous les états de base computationnels, suivie de l'opérateur de Grover (grover_op) répété le nombre optimal de fois. Nous utilisons ici la méthode QuantumCircuit.power(INT) pour appliquer l'opérateur de Grover de manière répétée.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Étape 2 : Optimiser le problème pour l'exécution sur matériel quantique

Pour la simulation à petite échelle, nous transpilons le circuit sans cibler de matériel spécifique.

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Étape 3 : Exécuter à l'aide des primitives Qiskit

L'amplification d'amplitude est un problème d'échantillonnage adapté à l'exécution avec la primitive SamplerV2. Ici, nous utilisons le StatevectorSampler de qiskit.primitives pour la simulation locale.

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

Étape 4 : Post-traiter et renvoyer le résultat dans le format classique souhaité

plot_distribution(dist)

Exemple sur matériel réel

Étapes 1 à 4

L'algorithme de Grover est fondamentalement un algorithme tolérant aux fautes — les portes Z multi-contrôlées au cœur de l'oracle et de l'opérateur de diffusion entraînent des profondeurs de portes à deux qubits qui croissent très rapidement avec le nombre de qubits (comme nous le montrerons dans la section suivante). Cela signifie que l'algorithme ne s'adapte pas bien au matériel bruité actuel. Pour cette raison, nous démontrons l'exécution sur matériel à la même petite échelle que l'exemple sur simulateur ci-dessus, plutôt que d'essayer une taille de problème plus grande.

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Discussion : Mise à l'échelle de la profondeur des portes à deux qubits

L'une des principales raisons pour lesquelles l'algorithme de Grover est considéré comme un algorithme tolérant aux fautes est la croissance rapide de la profondeur des portes à deux qubits du circuit à mesure que le nombre de qubits augmente. La porte Z multi-contrôlée au cœur de l'oracle et de l'opérateur de diffusion se décompose en un nombre de portes à deux qubits qui croît exponentiellement avec le nombre de qubits de contrôle. Combiné au fait que le nombre optimal d'itérations de Grover lui-même croît en $O(\sqrt{2^n})$, la profondeur totale à deux qubits devient rapidement impraticable pour le matériel bruité.

Ci-dessous, nous construisons des circuits de Grover pour un nombre croissant de qubits, nous les transpilons et nous traçons la profondeur résultante des portes à deux qubits pour illustrer cette mise à l'échelle.

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()

n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Comme le montre le graphique, la profondeur des portes à deux qubits croît extrêmement rapidement avec le nombre de qubits — de manière quasi exponentielle. Cela rend l'algorithme de Grover impraticable sur le matériel quantique bruité actuel au-delà de très petites tailles de problème. L'algorithme reste une cible importante pour les futurs ordinateurs quantiques tolérants aux fautes, où la correction d'erreur permettra d'exécuter des circuits profonds de manière fiable.

Prochaines étapes

Recommandations

Si ce travail t'a intéressé, tu pourrais être intéressé par les ressources suivantes :

• Bibliothèque de circuits Qiskit : référence API grover_operator()
• Le tutoriel QAOA et la leçon QAOA à l'échelle utilitaire donnent des exemples d'optimisation à court terme avec des ordinateurs quantiques
• Pour un aperçu plus approfondi des algorithmes à court terme, voir le cours Informatique quantique en pratique