Algorithmes quantiques : recherche de Grover et applications

remarque

Atsushi Matsuo (10 mai 2024)

Télécharger le PDF du cours original. Attention, certains extraits de code peuvent être obsolètes car ce sont des images statiques.

Le temps QPU approximatif pour exécuter cette expérience est de 2 secondes.

1. Introduction à l'algorithme de Grover

Ce notebook est le quatrième d'une série de cours sur le chemin vers l'utilité en informatique quantique. Dans ce notebook, nous allons découvrir l'algorithme de Grover.

L'algorithme de Grover est l'un des algorithmes quantiques les plus connus en raison de son accélération quadratique par rapport aux méthodes de recherche classiques. En informatique classique, rechercher dans une base de données non triée de $N$ éléments requiert une complexité temporelle de $O(N)$, ce qui signifie que dans le pire des cas, il faut potentiellement examiner chaque élément individuellement. L'algorithme de Grover, lui, permet d'effectuer cette recherche en $O(\sqrt{N})$, en tirant parti des principes de la mécanique quantique pour identifier l'élément cible plus efficacement.

L'algorithme utilise l'amplification d'amplitude, un processus qui augmente l'amplitude de probabilité de l'état solution dans une superposition quantique, permettant ainsi de le mesurer avec une probabilité plus élevée. Cette accélération rend l'algorithme de Grover précieux dans diverses applications au-delà de la simple recherche en base de données, notamment lorsque la taille du jeu de données est importante. Des explications détaillées de l'algorithme sont disponibles dans le notebook sur l'algorithme de Grover.

La structure de base de l'algorithme de Grover

L'algorithme de Grover comprend quatre composants principaux :

1. Initialisation : mise en place de la superposition sur tous les états possibles.
2. Oracle : application d'une fonction oracle qui marque l'état cible en renversant sa phase.
3. Opérateur de diffusion : application d'une série d'opérations pour amplifier la probabilité de l'état marqué.

Chacune de ces étapes joue un rôle essentiel dans le bon fonctionnement de l'algorithme. Des explications détaillées pour chaque étape sont fournies plus loin.

2. Implémentation de l'algorithme de Grover

2.1 Préparation

Importe les bibliothèques nécessaires et configure l'environnement pour exécuter le circuit quantique.

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

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

Étape 1 : Modéliser le problème en circuits et opérateurs quantiques

Considère une liste de 4 éléments, dont l'objectif est d'identifier l'index d'un élément qui satisfait une condition donnée. Par exemple, on cherche l'index de l'élément égal à 2. Dans cet exemple, l'état quantique $|01\rangle$ représente l'index de l'élément qui satisfait cette condition, car il pointe vers la position où la valeur 2 est située.

Étape 2 : Optimiser pour le matériel cible

1 : Initialisation

Dans l'étape d'initialisation, on crée une superposition de tous les états possibles. Cela s'obtient en appliquant une porte Hadamard à chaque qubit d'un registre de n qubits, ce qui produit une superposition uniforme de $2^n$ états. Mathématiquement, cela peut être représenté comme :

$$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

où $N = 2^n$ est le nombre total d'états possibles. On change également l'état du bit ancilla en $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2 : Oracle

L'oracle est un élément clé de l'algorithme de Grover. Il marque l'état cible en appliquant un déphasage, ce qui renverse typiquement le signe de l'amplitude associée à cet état. L'oracle est souvent spécifique au problème et construit en fonction des critères d'identification de l'état cible. En termes mathématiques, l'oracle applique la transformation suivante :

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

Ce déphasage est obtenu en appliquant un signe négatif à l'amplitude de l'état cible via le phase kickback.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3 : Opérateur de diffusion

Le processus d'amplification d'amplitude est ce qui distingue l'algorithme de Grover d'une recherche classique. Une fois que l'oracle a marqué l'état cible, on applique une série d'opérations qui augmentent l'amplitude de cet état marqué, le rendant plus probable lors de la mesure. Ce processus est réalisé grâce à l'opérateur de diffusion, qui effectue en pratique une inversion autour de l'amplitude moyenne. L'opération mathématique est la suivante :

$D = 2|\psi\rangle\langle\psi| - I$

où $D$ est l'opérateur de diffusion, $I$ est la matrice identité et $|\psi\rangle$ est l'état de superposition uniforme. La combinaison de l'oracle et de l'opérateur de diffusion est appliquée environ $\sqrt{N}$ fois pour atteindre la probabilité maximale de mesurer l'état marqué.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Un exemple de recherche de Grover à 2 qubits

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Expérimentation avec des simulateurs

Étape 3 : Exécution du circuit

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Étape 4 : Post-traitement des résultats

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

On a obtenu la bonne réponse $|01\rangle$. Note que l'ordre des qubits est important.

3. Expérimentation avec de vrais appareils

Étape 2 : Optimiser pour le matériel cible

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

En transpilant le circuit, il a été converti en un circuit utilisant les portes de base natives de l'appareil.

Étape 3 : Exécution du circuit

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Étape 4 : Post-traitement des résultats

plot_histogram(result_real[0].data.meas.get_counts())

4. Une recherche de Grover à 3 qubits

Essayons maintenant un exemple de recherche de Grover à 3 qubits.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Cette fois, $|111\rangle$ est le « bon » état.

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ est observé avec la probabilité la plus élevée, comme attendu. Note que deux itérations sont optimales dans ce cas. Cependant, la probabilité d'obtenir la bonne réponse n'est pas de 100 %, ce qui est habituel dans la recherche de Grover.

Que se passe-t-il si on itère 3 fois ?

Essayons maintenant d'itérer 3 fois.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ est toujours observé avec la probabilité la plus élevée, bien que la probabilité d'obtenir la bonne réponse ait légèrement diminué.

Et avec 4 itérations ?

Essayons maintenant d'itérer 4 fois.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ est observé avec la probabilité la plus faible, et la probabilité d'obtenir la bonne réponse a encore diminué. Cela démontre l'importance de choisir le nombre d'itérations optimal pour l'algorithme de Grover afin d'obtenir les meilleurs résultats.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'