Algorithme de Grover

Estimation du temps d'exécution : moins d'une minute sur un processeur Eagle r3 (REMARQUE : il s'agit uniquement d'une estimation. (Votre temps d'exécution peut varier.)

Résultats d'apprentissage

À l'issue de ce tutoriel, vous devriez être en mesure de comprendre les points suivants :

• Comment construire des oracles de Grover qui marquent un ou plusieurs états de la base de calcul
• Comment utiliser la grover_operator() fonction de la bibliothèque de circuits Qiskit
• Comment déterminer le nombre optimal d'itérations de Grover pour un problème donné
• Comment mettre en œuvre l'algorithme de Grover à l'aide de la primitive « Sampler » de l' IBM Quantum

Prérequis

Nous vous recommandons de vous familiariser avec les sujets suivants :

• Principes fondamentaux des algorithmes quantiques : l'algorithme de Grover
• Notions de base sur l’information quantique

Arrière-plan

L'amplification d'amplitude est un algorithme quantique polyvalent, ou sous-programme, qui permet d'obtenir un gain de vitesse quadratique par rapport à plusieurs algorithmes classiques. L'algorithme de Grover a été le premier à démontrer ce gain de vitesse pour les problèmes de recherche non structurés. Pour formuler un problème de recherche de Grover, il faut une fonction oracle qui identifie un ou plusieurs états de la base de calcul comme étant ceux que l'on cherche à trouver, ainsi qu'un circuit d'amplification qui augmente l'amplitude des états identifiés, supprimant ainsi les états restants.

Nous montrons ici comment construire des oracles de Grover et utiliser la bibliothèque de circuits Qiskit pour mettre en place facilement une instance de recherche de Grover grover_operator() de la bibliothèque de circuits Qiskit pour mettre en place facilement une instance de recherche de Grover. La primitive Sampler permet l'exécution transparente des circuits Grover.

Exigences

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

• Qiskit SDK v2.0 ou version ultérieure, avec prise en charge de la visualisation
• Qiskit Runtime v0.22 ou version ultérieure (pip install qiskit-ibm-runtime)

Configuration

# 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-ibm-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 de simulateur à petite échelle

Dans cette section, nous passons en revue chaque étape de l'algorithme de Grover à petite échelle à l'aide d'un simulateur local, avant d'appliquer ce même problème à du matériel quantique réel.

Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique

L'algorithme de Grover nécessite un oracle qui spécifie un ou plusieurs états de base de calcul « marqués », le terme « marqué » désignant un état dont la phase est égale à -1. Une porte à Z contrôlé, ou sa généralisation à contrôles multiples sur des qubits d' $N$, définit l'état d' $2^{N}-1$ ('1'*chaîne de bits $N$ ). Pour marquer les états de base avec un ou plusieurs '0' dans la représentation binaire, il faut appliquer des portes X aux qubits correspondants avant et après la porte Z contrôlée, ce qui revient à appliquer une commande ouverte à ce qubit. Dans le code suivant, nous définissons un oracle qui identifie un ou plusieurs états de base d'entrée définis par leur représentation sous forme de chaîne binaire. Cette MCMT porte sert à mettre en œuvre la porte Z à commandes multiples.

Cas 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 marquerons deux états de calcul sur les huit disponibles dans un espace de calcul à trois qubits :

marked_states = ["011", "100"]

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

Output:

opérateur Grover

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

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

Output:

Les applications répétées de ce circuit grover_op amplifient les états marqués, ce qui en fait les chaînes de bits les plus probables dans la distribution de sortie du circuit. Le nombre optimal de ces applications est déterminé par le rapport entre les états marqués et le nombre total d'états de calcul possibles :

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

Circuit Grover complet

Une expérience de Grover complète commence par une porte de Hadamard sur chaque qubit, créant une superposition paire de tous les états de base de calcul, 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 de manière répétée l'opérateur de Grover.

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

Output:

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

Pour la simulation à petite échelle, nous compilons le circuit sans le destiner à un 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")

Output:

Étape 3 : Exécutez à l'aide d' Qiskit primitives

L'amplification d'amplitude est un problème d'échantillonnage qui se prête bien à une exécution à l'aide de la SamplerV2 primitive. 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-traitement et restitution du résultat dans le format classique souhaité

plot_distribution(dist)

Output:

Exemple de matériel

Étapes 1 à 4

L'algorithme de Grover est fondamentalement un algorithme tolérant aux pannes : les portes Z à contrôles multiples qui constituent le cœur de l'oracle et de l'opérateur de diffusion entraînent des profondeurs de porte à deux qubits qui augmentent 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 actuel, souvent sujet à des interférences. C'est pourquoi nous présentons l'exécution matérielle à la même petite échelle que l'exemple de simulation ci-dessus, plutôt que de nous attaquer à un problème de plus grande envergure.

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

Output:

Discussion : Évolution 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 pannes réside dans la croissance rapide de la profondeur des portes à deux qubits du circuit à mesure que le nombre de qubits augmente. La porte Z à contrôles multiples, qui est au cœur à la fois de l'oracle et de l'opérateur de diffusion, se décompose en un nombre de portes à deux qubits qui croît de manière exponentielle avec le nombre de qubits de contrôle. Si l'on ajoute à cela le fait que le nombre optimal d'itérations de Grover augmente lui-même selon une loi de l'ordre de $O(\sqrt{2^n})$, la profondeur totale à deux qubits devient rapidement irréalisable sur du matériel sujet au bruit.

Ci-dessous, nous construisons des circuits de Grover pour un nombre croissant de qubits, nous les transposons, puis nous représentons graphiquement la profondeur des portes à deux qubits obtenue afin d'illustrer cette évolutivité.

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

Output:

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 augmente extrêmement rapidement avec le nombre de qubits — de manière à peu près exponentielle. Cela rend l'algorithme de Grover inutilisable sur le matériel quantique actuel, sujet au bruit, sauf pour des problèmes de très petite taille. Cet algorithme reste un objectif majeur pour les futurs ordinateurs quantiques tolérants aux pannes, où la correction d'erreurs permettra d'exécuter de manière fiable des circuits complexes.

Etapes suivantes