Estimation de phase quantique (QPE) & Algorithme de Grover

Estimation de phase quantique (QPE)

Idée intuitive

Imagine un opérateur U (une transformation quantique) qui, appliqué à un certain état |ψ⟩, ne fait que le multiplier par un nombre complexe de module 1 : U|ψ⟩ = e^{2πiϕ}|ψ⟩. Le nombre ϕ (entre 0 et 1) est la phase propre. La QPE est l’algorithme qui “lit” cette phase ϕ en la convertissant en un nombre binaire.

Analogie : pense à un diapason. Tu ne “vois” pas sa fréquence, mais en le comparant à des notes de référence, tu peux déterminer sa fréquence exacte. La QPE fait pareil : elle compare U à des “notes de référence” (puissances de U) pour extraire ϕ.

Les ingrédients

• Registre de comptage (t qubits “ancillaires”) : plus tu mets de qubits, plus la précision de ϕ est grande (t bits de précision).
• Registre cible : contient l’état propre |ψ⟩ de U.
• Opérations U contrôlées : on applique U^{2^k} contrôlé par le qubit ancillaire k.
• QFT inverse : à la fin, on applique la transformée de Fourier quantique inverse sur le registre de comptage pour “lire” ϕ en binaire.

Le circuit pas à pas

1. Mettre tous les qubits ancillaires en superposition avec Hadamard.
2. Appliquer U^{2^0} contrôlé par le qubit ancillaire 0, U^{2^1} contrôlé par le qubit 1, etc.
3. Appliquer la QFT⁻¹ (QFT inverse) sur les qubits ancillaires.
4. Mesurer les qubits ancillaires → on obtient ϕ en binaire.

Code Qiskit (QPE manuelle)

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
import numpy as np

# Estimation de phase sur 3 qubits ancillaires
# U = porte T (phase π/4, donc ϕ = 1/8)
n_counting = 3
qc = QuantumCircuit(n_counting + 1, n_counting)

# Préparer l'état propre |1⟩ de T
qc.x(n_counting)

# Étape 1 : Hadamard sur tous les ancillaires
for i in range(n_counting):
    qc.h(i)

# Étape 2 : U^(2^k) contrôlé
# T^1 (phase π/4) contrôlé par qubit 0
qc.cp(np.pi / 4, 0, n_counting)
# T^2 = S (phase π/2) contrôlé par qubit 1
qc.cp(np.pi / 2, 1, n_counting)
# T^4 = Z (phase π) contrôlé par qubit 2
qc.cp(np.pi, 2, n_counting)

# Étape 3 : QFT inverse sur les qubits ancillaires
qc.append(QFT(n_counting, inverse=True), range(n_counting))

# Étape 4 : Mesure → résultat binaire de ϕ
qc.measure(range(n_counting), range(n_counting))
# Résultat attendu : |001⟩ → ϕ = 1/8 = 0.001 en binaire

Code Qiskit

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
import numpy as np

# QPE pour la porte T (phase = π/4, donc ϕ = 1/8)
n_counting = 3  # 3 qubits ancillaires
qc = QuantumCircuit(n_counting + 1, n_counting)

# Préparer l'état propre \|1⟩
qc.x(n_counting)

# Étape 1 : Hadamard sur les qubits de comptage
for i in range(n_counting):
    qc.h(i)

# Étape 2 : U^(2^k) contrôlé — T^(2^k)
repetitions = 1
for counting_qubit in range(n_counting):
    for _ in range(repetitions):
        qc.cp(np.pi / 4, counting_qubit, n_counting)  # Phase de T
    repetitions *= 2

# Étape 3 : QFT inverse sur les qubits de comptage
qc.append(QFT(n_counting, inverse=True), range(n_counting))

# Étape 4 : Mesure
qc.measure(range(n_counting), range(n_counting))
# Résultat attendu : \|001⟩ → ϕ = 1/8

⚠️ Piège courant : la QPE ne fonctionne parfaitement que si ϕ s’écrit exactement sur t bits. Si ϕ n’est pas un multiple exact de 1/2^t, le résultat est une approximation — et il faut plus de qubits ancillaires pour plus de précision. C’est comme mesurer une longueur avec une règle graduée : plus de graduations = plus de précision.

Algorithme de Grover

Idée intuitive

Tu cherches une aiguille dans une botte de foin de N éléments. Classiquement, il faut en moyenne N/2 essais. Grover le fait en seulement √N essais — un gain quadratique.

Analogie : imagine que tu cherches un livre dans une bibliothèque non triée de 1 million de livres. Classiquement : ~500 000 vérifications. Avec Grover : ~1 000 vérifications seulement.

Les deux ingrédients clés

• Oracle (O) : une boîte noire qui “marque” la bonne réponse en inversant son signe. Si |x⟩ est la solution, O|x⟩ = −|x⟩. Pour tous les autres : O|y⟩ = |y⟩. L’oracle ne “cherche” pas — il sait juste répondre “oui/non” pour un x donné.
• Opérateur de diffusion (D) : aussi appelé “inversion autour de la moyenne”. Il amplifie l’amplitude de la solution marquée et réduit celles des non-solutions.

Le circuit pas à pas

1. Préparer une superposition uniforme : H⊗n|0…0⟩ → tous les N = 2^n états ont la même amplitude 1/√N.
2. Répéter environ √N fois : (a) Appliquer l’oracle O (inverse le signe de la solution). (b) Appliquer l’opérateur de diffusion D (amplifie la solution).
3. Mesurer → on obtient la solution avec haute probabilité.

Nombre optimal d’itérations

Le nombre idéal d’itérations est environ π/4 × √N (arrondi à l’entier le plus proche). Attention : trop d’itérations fait baisser la probabilité de succès — l’amplitude “dépasse” la cible et redescend, comme un pendule qui va trop loin.

Code Qiskit (Grover)

from qiskit import QuantumCircuit

# Grover pour chercher |11⟩ parmi 4 états (2 qubits)
qc = QuantumCircuit(2, 2)
n_iterations = 1  # π/4 × √4 ≈ 1.57 → 1 itération

# Superposition uniforme
qc.h([0, 1])

for _ in range(n_iterations):
    # Oracle : marque |11⟩ en inversant son signe (CZ)
    qc.cz(0, 1)

    # Opérateur de diffusion (inversion autour de la moyenne)
    qc.h([0, 1])
    qc.x([0, 1])
    qc.cz(0, 1)
    qc.x([0, 1])
    qc.h([0, 1])

# Mesure
qc.measure([0, 1], [0, 1])
# Résultat attendu : |11⟩ avec probabilité ~100%

Code Qiskit

from qiskit import QuantumCircuit

# Grover pour chercher \|11⟩ parmi 4 états (2 qubits)
qc = QuantumCircuit(2, 2)

# Superposition uniforme
qc.h([0, 1])

# === Itération de Grover (1 seule suffit pour N=4) ===

# Oracle : marque \|11⟩ → CZ (inverse le signe de \|11⟩)
qc.cz(0, 1)

# Opérateur de diffusion
qc.h([0, 1])
qc.x([0, 1])
qc.cz(0, 1)
qc.x([0, 1])
qc.h([0, 1])

# Mesure
qc.measure([0, 1], [0, 1])
# Résultat attendu : \|11⟩ avec probabilité ~100%

⚠️ Piège courant : le gain de Grover est quadratique, pas exponentiel. Passer de N à √N, c’est impressionnant (1 million → 1 000), mais ce n’est pas le gain exponentiel de Shor. De plus, itérer trop de fois dégrade le résultat — il faut s’arrêter au bon moment.