Algorithme de Shor — détails du circuit & Simulation de hamiltoniens

Algorithme de Shor — détails du circuit

Rappel : l’algorithme de Shor factorise un entier N en trouvant la période r de la fonction f(x) = a^x mod N. Le circuit quantique accélère cette recherche de période grâce à l’estimation de phase (QPE), vue au jour 18.

Vue d’ensemble du circuit

Le circuit de Shor se compose de trois blocs principaux :

• Registre de comptage (~2n qubits, haut du circuit) : initialisé à |0⟩, ce registre subit des Hadamard puis la QFT inverse. C’est le « capteur de phase ».
• Registre de travail (n qubits, bas du circuit) : initialisé à |1⟩. L’exponentiation modulaire agit ici.
• Post-traitement classique : mesure du registre de comptage, puis algorithme des fractions continues pour extraire la période r.

Point clé : n = ⌈log₂(N)⌉. Pour factoriser un nombre de n bits, il faut ~2n qubits de comptage + n qubits de travail + des ancillaires pour l’arithmétique modulaire.

Exponentiation modulaire contrôlée

C’est le cœur coûteux du circuit. Pour chaque qubit j du registre de comptage, on applique l’opération « multiplier par a^(2^j) mod N » de façon contrôlée sur le registre de travail.

Analogie : imagine que chaque qubit du compteur « allume ou éteint » un multiplicateur de plus en plus gros — comme un interrupteur qui double, quadruple, octuple la mise à chaque étage.

Pourquoi les fractions continues ?

La mesure du registre de comptage donne un entier m. Le ratio m / 2^(2n) est une approximation de s/r (un multiple de l’inverse de la période). Les fractions continues sont un algorithme classique qui retrouve la fraction la plus simple s/r — comme retrouver 1/3 à partir de 0.33333…

Étapes de post-traitement

1. Mesurer le registre de comptage → obtenir m.
2. Calculer m / 2^(2n) et appliquer les fractions continues → candidat r.
3. Vérifier : a^r mod N = 1 ? Si oui, calculer pgcd(a^(r/2) ± 1, N).
4. Si pas de facteur non-trivial, relancer avec un autre a ou une autre mesure.

Code Q# — structure de l’estimation d’ordre

// Squelette simplifié de l'estimation d'ordre pour Shor
operation EstimerOrdre(a : Int, N : Int, nCompteur : Int) : Int {
    use compteur = Qubit[nCompteur];
    use travail = Qubit[BitSizeI(N)];

    // Étape 1 : initialiser le registre de travail à |1⟩
    X(travail[0]);

    // Étape 2 : superposition du registre de comptage
    for q in compteur {
        H(q);
    }

    // Étape 3 : exponentiation modulaire contrôlée
    for j in 0..nCompteur - 1 {
        Controlled ModularExp([compteur[j]], (a, 2^j, N, travail));
    }

    // Étape 4 : QFT inverse sur le registre de comptage
    Adjoint QFT(compteur);

    // Étape 5 : mesurer → post-traitement classique
    let resultat = MeasureInteger(compteur);
    ResetAll(travail);
    return resultat;
}

Code Qiskit — circuit simplifié

# Squelette simplifié — factorisation de 15 avec a=7
from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT

n_compteur = 8  # 2 * ceil(log2(15)) = 8
n_travail = 4   # ceil(log2(15)) = 4

qc = QuantumCircuit(n_compteur + n_travail, n_compteur)

# |1⟩ dans le registre de travail
qc.x(n_compteur)

# Hadamard sur le registre de comptage
for q in range(n_compteur):
    qc.h(q)

# Exponentiation modulaire contrôlée (simplifié)
for j in range(n_compteur):
    puissance = pow(7, 2**j, 15)
    # controlled_modular_multiply(qc, j, puissance, 15, ...)
    pass  # remplacer par la décomposition réelle

# QFT inverse
qc.append(QFT(n_compteur, inverse=True), range(n_compteur))
qc.measure(range(n_compteur), range(n_compteur))

Piège courant : l’exponentiation modulaire n’est PAS une simple mise au carré répétée classique. Chaque multiplication doit être réversible (unitaire), ce qui nécessite des qubits ancillaires et des portes de décomputation. C’est la partie la plus coûteuse — elle domine en O(n³).

Simulation de hamiltoniens

L’idée fondamentale : simuler un système quantique, c’est reproduire sur un ordinateur quantique comment un système physique évolue dans le temps. Richard Feynman l’avait prédit dès 1982 : simuler la physique quantique avec un ordinateur classique est exponentiellement coûteux, mais un ordinateur quantique pourrait le faire efficacement.

Analogie du cuisinier

Imagine une recette avec 3 étapes qui doivent se faire en même temps (mélanger, chauffer, remuer). Un cuisinier classique ne peut faire qu’une chose à la fois — il alterne rapidement entre les trois. Si l’alternance est assez rapide, le résultat est presque identique. C’est exactement ce que fait la trotterisation : découper l’évolution d’un système quantique complexe en petits pas alternés, chacun étant simple à réaliser.

Hamiltonien — l’opérateur d’énergie

Le hamiltonien H décrit l’énergie totale d’un système. En mécanique quantique, l’état évolue selon |ψ(t)⟩ = e^(−iHt)|ψ(0)⟩.

Intuition : H est la « recette » qui dicte comment le système change au fil du temps. Plus H est complexe (beaucoup de termes), plus le plat est élaboré.

Le problème de la non-commutation

Un hamiltonien H est souvent la somme de termes : H = H₁ + H₂ + … + Hₖ. Chaque Hⱼ est simple à simuler, mais e^(−iHt) ≠ e^(−iH₁t) · e^(−iH₂t) en général — les termes ne commutent pas.

Analogie : « marcher vers le nord puis vers l’est » n’est pas la même chose que « marcher vers le nord-est » si le terrain n’est pas plat.

Trotterisation (Lie–Trotter, ordre 1)

La formule de Trotter dit : e^(−iHt) ≈ (e^(−iH₁δ) · e^(−iH₂δ))^n avec δ = t/n. Plus n est grand, meilleure est l’approximation. L’erreur totale est en O(t²/n).

Suzuki (ordre 2) — symétriser pour gagner

On « symétrise » la séquence : demi-pas de H₁, pas complet de H₂, demi-pas de H₁. L’erreur passe en O(t³/n²) — bien mieux pour le même coût.

Application en chimie quantique

Le hamiltonien d’une molécule décrit les interactions entre électrons et noyaux. Simuler ces interactions permet de prédire les propriétés chimiques — un problème exponentiellement coûteux classiquement mais polynomial quantiquement grâce à la trotterisation. C’est un cas d’usage majeur pour les futurs ordinateurs quantiques tolérants aux fautes.

Code Q# — pas de Trotter pour 2 termes

// Simuler e^(-i(H1+H2)t) par trotterisation d'ordre 1
operation TrotterStep(
    H1 : (Qubit[] => Unit is Adj + Ctl),
    H2 : (Qubit[] => Unit is Adj + Ctl),
    qubits : Qubit[],
    nTrotter : Int,
    t : Double
) : Unit is Adj + Ctl {
    let delta = t / IntAsDouble(nTrotter);
    for _ in 0..nTrotter - 1 {
        H1(qubits);  // appliquer e^(-i H1 delta)
        H2(qubits);  // appliquer e^(-i H2 delta)
    }
}

// Ordre 2 (Suzuki) : symétriser les termes
operation SuzukiStep(
    H1 : (Qubit[] => Unit is Adj + Ctl),
    H2 : (Qubit[] => Unit is Adj + Ctl),
    qubits : Qubit[],
    nTrotter : Int,
    t : Double
) : Unit is Adj + Ctl {
    let delta = t / IntAsDouble(nTrotter);
    for _ in 0..nTrotter - 1 {
        H1(qubits);  // demi-pas H1
        H2(qubits);  // pas complet H2
        H1(qubits);  // demi-pas H1
    }
}

Code Qiskit — simulation d’un hamiltonien Ising

# Hamiltonien Ising à 2 qubits : H = J·Z⊗Z + h·(X⊗I + I⊗X)
from qiskit import QuantumCircuit

def trotter_ising_step(qc, J, h, dt, n_trotter):
    """Un pas de Trotter d'ordre 1 pour H_Ising."""
    delta = dt / n_trotter
    for _ in range(n_trotter):
        # Terme Z⊗Z : e^(-i J delta Z⊗Z)
        qc.cx(0, 1)
        qc.rz(2 * J * delta, 1)
        qc.cx(0, 1)

        # Terme X⊗I + I⊗X
        qc.rx(2 * h * delta, 0)
        qc.rx(2 * h * delta, 1)

qc = QuantumCircuit(2)
trotter_ising_step(qc, J=0.5, h=0.3, dt=1.0, n_trotter=10)
qc.measure_all()

Piège courant : plus on augmente n (pas de Trotter), plus le circuit est profond. Sur un matériel bruité (NISQ), un circuit trop profond accumule des erreurs de bruit qui annulent le gain de précision. Il faut trouver le bon compromis entre erreur de Trotter et erreur de bruit matériel.