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

// Estimation de phase sur 3 qubits ancillaires
// U = porte T (phase π/4, donc ϕ = 1/8)
operation EstimatePhaseT() : Int {
    use counting = Qubit[3];   // 3 qubits ancillaires → 3 bits de précision
    use target = Qubit();      // état propre \|1⟩ de T

    X(target);                 // Prépare \|1⟩ (état propre de T)

    // Étape 1 : Hadamard sur tous les ancillaires
    ApplyToEach(H, counting);

    // Étape 2 : U^(2^k) contrôlé
    Controlled T([counting[0]], target);          // T^1
    Controlled S([counting[1]], target);          // T^2 = S
    Controlled Z([counting[2]], target);          // T^4 = Z

    // Étape 3 : QFT inverse (simplifiée pour 3 qubits)
    SWAP(counting[0], counting[2]);
    H(counting[0]);
    Controlled R1([counting[1]], (PI() / 2.0, counting[0]));
    H(counting[1]);
    Controlled R1([counting[2]], (PI() / 2.0, counting[1]));
    Controlled R1([counting[2]], (PI() / 4.0, counting[0]));
    H(counting[2]);

    // Étape 4 : Mesure → résultat binaire de ϕ
    let result = MeasureInteger(LittleEndian(counting));
    Reset(target);
    return result;  // Devrait donner 1 (car ϕ = 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 Q#

// Grover pour chercher \|11⟩ parmi 4 états (2 qubits)
operation GroverSearch() : Result[] {
    use qubits = Qubit[2];
    let nIterations = 1;  // π/4 × √4 ≈ 1.57 → 1 itération

    // Superposition uniforme
    ApplyToEach(H, qubits);

    for _ in 1..nIterations {
        // Oracle : marque \|11⟩ en inversant son signe
        Controlled Z([qubits[0]], qubits[1]);

        // Opérateur de diffusion (inversion autour de la moyenne)
        ApplyToEach(H, qubits);
        ApplyToEach(X, qubits);
        Controlled Z([qubits[0]], qubits[1]);
        ApplyToEach(X, qubits);
        ApplyToEach(H, qubits);
    }

    // Mesure
    let results = [M(qubits[0]), M(qubits[1])];
    ResetAll(qubits);
    return results;  // Devrait donner [One, One] = \|11⟩
}

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.