Algorithme de Simon & Transformée de Fourier quantique

Algorithme de Simon

Le problème

On te donne un oracle pour une fonction f : {0,1}ⁿ → {0,1}ⁿ avec une promesse forte : il existe une chaîne secrète s ≠ 0…0 telle que f(x) = f(y) si et seulement si y = x ⊕ s. Autrement dit, f est périodique dans l’espace des chaînes binaires — chaque sortie est partagée par exactement deux entrées qui diffèrent de s. Ta mission : retrouver s.

Point clé : Classiquement, retrouver s exige environ 2^(n/2) requêtes à l’oracle (paradoxe des anniversaires : il faut tomber sur deux entrées avec la même image). Simon le fait avec O(n) requêtes — un gain exponentiel prouvé dans le modèle d’oracle.

Le circuit en cinq étapes

• Étape 1 : deux registres de n qubits, tous initialisés à |0⟩.
• Étape 2 : Hadamard sur le premier registre → superposition uniforme sur les 2ⁿ entrées.
• Étape 3 : appel de l’oracle U_f. Il écrit f(x) dans le second registre. Comme f(x) = f(x⊕s), chaque valeur du second registre est partagée par deux entrées (x et x⊕s).
• Étape 4 : Hadamard à nouveau sur le premier registre — étape d’interférence.
• Étape 5 : mesurer le premier registre. Le résultat y est aléatoire mais satisfait toujours s · y ≡ 0 (mod 2), où · est le produit scalaire binaire (AND bit à bit puis somme modulo 2, comme à Bernstein–Vazirani).

Le post-traitement classique

Chaque exécution te donne une équation linéaire s · y = 0 dans F₂. Au bout de n − 1 équations linéairement indépendantes (~n exécutions en moyenne), tu résous le système par élimination de Gauss sur F₂. La seule solution non nulle, c’est s. La partie quantique sème les équations, le classique les résout.

Attention : les y mesurés peuvent être linéairement dépendants — il faut parfois plus de n exécutions. Et y = 0…0 est toujours possible : il satisfait l’équation trivialement et n’apporte aucune information, donc on le jette.

Code Q#

// Oracle pour s = "11" (n = 2) : f(x) = (x[0] XOR x[1], x[0] XOR x[1])
// Vérification : f(00) = f(11) = (0,0) et f(01) = f(10) = (1,1)
operation OracleSimon(input : Qubit[], output : Qubit[]) : Unit {
    // Première sortie = x[0] XOR x[1]
    CNOT(input[0], output[0]);
    CNOT(input[1], output[0]);
    // Deuxième sortie = x[0] XOR x[1]
    CNOT(input[0], output[1]);
    CNOT(input[1], output[1]);
}

operation SimonShot(n : Int) : Result[] {
    // Une exécution. À répéter ~n fois pour accumuler des équations.
    use (input, output) = (Qubit[n], Qubit[n]);
    ApplyToEach(H, input);            // Étape 2 : superposition
    OracleSimon(input, output);       // Étape 3 : oracle
    ApplyToEach(H, input);            // Étape 4 : interférence
    let y = MeasureEachZ(input);      // Étape 5 : équation s · y = 0
    ResetAll(output);
    return y;
}

Code Qiskit

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 3
qc = QuantumCircuit(2 * n, n)

# Étape 2 : Hadamard sur les n qubits d'entrée
for i in range(n):
    qc.h(i)

# Étape 3 : oracle pour s = "110"
#   f(x) = (x0 XOR x1, x0 XOR x1, x2)
qc.cx(0, n + 0); qc.cx(1, n + 0)
qc.cx(0, n + 1); qc.cx(1, n + 1)
qc.cx(2, n + 2)

# Étape 4 : Hadamard à nouveau
for i in range(n):
    qc.h(i)

# Étape 5 : mesure du registre d'entrée
qc.measure(range(n), range(n))

sim = AerSimulator()
counts = sim.run(qc, shots=8 * n).result().get_counts()
# Chaque y observé satisfait s · y = 0 mod 2.
# Élimination de Gauss sur F2 sur la liste des y → on retrouve s.
print(counts)

Transformée de Fourier quantique (QFT)

L’idée en une phrase

La QFT est la version quantique de la transformée de Fourier discrète (DFT). Elle transforme les amplitudes de chaque état de base d’un registre en une combinaison périodique d’amplitudes. Là où la DFT révèle les fréquences cachées dans un signal numérique, la QFT révèle les périodes cachées dans une superposition quantique — exactement ce dont Shor a besoin pour casser RSA.

Point clé : La QFT sur n qubits coûte O(n²) portes (un Hadamard puis quelques rotations contrôlées par qubit). La FFT classique coûte O(n · 2ⁿ) opérations sur des amplitudes explicites. Mais on ne peut pas lire directement les amplitudes après QFT — il faut combiner avec QPE, Shor, etc.

Le circuit, sans douleur

Sur n qubits indexés du plus significatif (q₀) au moins significatif (q_{n-1}), le circuit canonique enchaîne :

• Pour chaque qubit q_i (i = 0, 1, …, n−1) :
  • Appliquer Hadamard sur q_i.
  • Pour chaque qubit suivant q_j (j > i) : appliquer une rotation de phase contrôlée CR_k, où k = j − i + 1 et R_k = diag(1, e^(2iπ/2^k)).
• Enfin, inverser l’ordre des qubits avec des SWAP — la QFT « renverse » l’endianness.

Analogie : les aiguilles d’horloges

Imagine que chaque qubit est l’aiguille d’une horloge avec un cadran différent (1 tour, 1/2 tour, 1/4 de tour, …). La QFT règle chaque aiguille avec une vitesse de plus en plus fine selon sa position : le premier qubit fait un tour complet pour parcourir toutes les bases, le deuxième un demi-tour, etc. À l’arrivée, l’orientation collective des aiguilles encode la fréquence dominante du signal initial. Les portes CR_k sont exactement le mécanisme qui synchronise ces vitesses.

Piège fréquent : la QFT n’« accélère pas la FFT ». Comme on ne peut lire qu’un seul état à la fois (mesure projective), l’information de toutes les amplitudes reste inaccessible. La QFT n’est utile que composée avec un algorithme qui sait exploiter la structure périodique avant la mesure — d’où son rôle clé dans QPE, Shor et la recherche d’ordre.

Code Q#

open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;

// QFT canonique construite à la main (Big-endian : qs[0] = poids fort)
operation ApplyMyQFT(qs : Qubit[]) : Unit is Adj + Ctl {
    let n = Length(qs);
    for i in 0 .. n - 1 {
        H(qs[i]);
        for j in i + 1 .. n - 1 {
            // R1Frac applique diag(1, exp(2iπ · num / 2^denomBits))
            // Ici on veut une phase 2π / 2^(j - i + 1)
            Controlled R1Frac([qs[j]], (1, j - i + 1, qs[i]));
        }
    }
    // Étape finale : inverser l'ordre des qubits
    SwapReverseRegister(qs);
}

// La librairie standard fournit déjà QFT et son inverse :
//   Microsoft.Quantum.Canon.ApplyQuantumFourierTransform(qs)
//   Adjoint Microsoft.Quantum.Canon.ApplyQuantumFourierTransform(qs)

Code Qiskit

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

n = 3
qc = QuantumCircuit(n)

# Construction manuelle (pour comprendre la mécanique)
for i in range(n):
    qc.h(i)
    for j in range(i + 1, n):
        angle = np.pi / (2 ** (j - i))    # = 2π / 2^(j-i+1)
        qc.cp(angle, j, i)                 # rotation de phase contrôlée

# Renversement de l'ordre des qubits (SWAP)
for i in range(n // 2):
    qc.swap(i, n - 1 - i)

# Équivalent en une ligne avec la librairie standard
qc_lib = QuantumCircuit(n)
qc_lib.append(QFT(n), range(n))            # do_swaps=True par défaut