Algorithme de Deutsch–Jozsa & Algorithme de Bernstein–Vazirani

Algorithme de Deutsch–Jozsa

Le problème

On te donne une fonction f qui prend une chaîne de n bits en entrée et renvoie 0 ou 1. On te promet que f est soit constante (toujours 0, ou toujours 1 pour toutes les entrées), soit équilibrée (renvoie 0 pour exactement la moitié des entrées et 1 pour l’autre moitié). Ta mission : déterminer laquelle des deux.

Point clé : Classiquement, dans le pire cas il faut tester 2^(n-1) + 1 entrées. Avec n = 40, ça fait plus de 500 milliards d’appels à f. L’algorithme quantique le fait en 1 seul appel.

L’intuition — version 1 qubit (Deutsch)

Imagine que f prend 1 bit. Il y a 4 fonctions possibles : deux constantes (f(0)=f(1)=0 et f(0)=f(1)=1) et deux équilibrées (f(0)≠f(1)).

L’astuce : on met le qubit d’entrée en superposition avec une porte Hadamard, on applique l’oracle (qui encode f via le phase kickback vu au jour 13), puis on refait Hadamard. Le résultat de la mesure donne directement la réponse :

• Mesure |0⟩ → f est constante
• Mesure |1⟩ → f est équilibrée

Version n qubits

Le circuit se généralise naturellement :

• Étape 1 : Préparer n qubits d’entrée dans l’état |0⟩ et 1 qubit ancillaire dans l’état |1⟩.
• Étape 2 : Appliquer Hadamard sur tous les qubits (entrée + ancillaire). Cela crée une superposition uniforme sur les 2^n entrées possibles.
• Étape 3 : Appliquer l’oracle U_f — grâce au phase kickback, la phase de chaque terme de la superposition est modifiée selon f(x).
• Étape 4 : Re-appliquer Hadamard sur les n qubits d’entrée.
• Étape 5 : Mesurer les qubits d’entrée. Si on lit |00…0⟩, f est constante. Sinon, f est équilibrée.

Pourquoi ça marche ? Hadamard après l’oracle fait interférer les amplitudes. Si f est constante, toutes les phases sont identiques et l’interférence reconstruit |00…0⟩. Si f est équilibrée, les phases positives et négatives s’annulent sur |00…0⟩ et on mesure autre chose.

Code Q#

// Oracle : applique une phase -1 si f(x)=1
// Ici on simule une fonction équilibrée : f(x) = x[0] XOR x[1]
operation OracleDJ(input : Qubit[], ancilla : Qubit) : Unit {
    CNOT(input[0], ancilla);
    CNOT(input[1], ancilla);
}

operation DeutschJozsa(n : Int) : Bool {
    // Renvoie true si f est constante, false si équilibrée
    use (input, ancilla) = (Qubit[n], Qubit());
    X(ancilla);                        // ancilla → |1⟩
    ApplyToEach(H, input);             // superposition
    H(ancilla);
    OracleDJ(input, ancilla);          // appel oracle
    ApplyToEach(H, input);             // interférence
    let result = MeasureEachZ(input);  // mesure
    Reset(ancilla);
    return All(r -> r == Zero, result); // tout |0⟩ → constante
}

Code Qiskit

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

n = 2
qc = QuantumCircuit(n + 1, n)

# Étape 1 : ancilla en |1⟩
qc.x(n)

# Étape 2 : Hadamard sur tout
for i in range(n + 1):
    qc.h(i)

# Étape 3 : oracle (f équilibrée = XOR des bits)
qc.cx(0, n)
qc.cx(1, n)

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

# Étape 5 : mesure
qc.measure(range(n), range(n))

# Simulation
sim = AerSimulator()
result = sim.run(qc, shots=1024).result()
counts = result.get_counts()
print(counts)  # "00" → constante, autre → équilibrée

Attention : Deutsch–Jozsa est impressionnant en théorie, mais il résout un problème artificiel — en pratique, un algorithme probabiliste classique avec ~10 appels aléatoires donne la bonne réponse avec 99,9 % de certitude. L’intérêt est pédagogique : comprendre comment superposition + interférence battent le classique.

Algorithme de Bernstein–Vazirani

Le problème

On te donne un oracle qui calcule f(x) = s · x mod 2, où s est une chaîne secrète de n bits et · est le produit scalaire binaire (AND bit à bit, puis somme modulo 2). Ton but : trouver s.

Exemple concret avec s = 101 et x = 110 : on fait le AND bit à bit → 100, puis on somme les bits → 1. Donc f(110) = 1.

Point clé : Classiquement, il faut n appels à l’oracle — un par bit de s — en envoyant les vecteurs de base 100…0, 010…0, etc. Quantiquement, 1 seul appel suffit pour retrouver les n bits d’un coup.

Le circuit

La structure est quasi identique à Deutsch–Jozsa — c’est le même squelette H → Oracle → H → Mesure :

• Étape 1 : n qubits d’entrée en |0⟩, 1 ancillaire en |1⟩.
• Étape 2 : Hadamard sur tout.
• Étape 3 : Oracle — pour chaque bit i où s[i] = 1, appliquer un CNOT du qubit i vers l’ancillaire.
• Étape 4 : Hadamard sur les n qubits d’entrée.
• Étape 5 : Mesurer → le résultat est directement s !

Pourquoi ça marche ? L’oracle “marque” les qubits correspondant aux bits à 1 de s via le phase kickback. Hadamard transforme ces phases en valeurs mesurables. C’est comme si l’oracle imprimait s en négatif photographique, et Hadamard le révélait.

Analogie

Imagine une boîte noire avec n interrupteurs. Certains sont connectés à une lampe (ceux où s[i]=1), les autres ne font rien. Classiquement, tu testes chaque interrupteur un par un (n essais). Quantiquement, tu actionnes tous les interrupteurs en superposition et la lampe te “dit” lesquels sont connectés en un seul flash.

Code Q#

// Oracle pour s = "101" (secret sur 3 qubits)
operation OracleBV(input : Qubit[], ancilla : Qubit) : Unit {
    // s[0] = 1 → CNOT sur qubit 0
    CNOT(input[0], ancilla);
    // s[1] = 0 → rien
    // s[2] = 1 → CNOT sur qubit 2
    CNOT(input[2], ancilla);
}

operation BernsteinVazirani(n : Int) : Result[] {
    use (input, ancilla) = (Qubit[n], Qubit());
    X(ancilla);
    ApplyToEach(H, input);
    H(ancilla);
    OracleBV(input, ancilla);
    ApplyToEach(H, input);
    let secret = MeasureEachZ(input);  // → [One, Zero, One] = "101"
    Reset(ancilla);
    return secret;
}

Code Qiskit

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

secret = "101"
n = len(secret)
qc = QuantumCircuit(n + 1, n)

# Ancilla en |1⟩
qc.x(n)

# Hadamard sur tout
for i in range(n + 1):
    qc.h(i)

# Oracle : CNOT pour chaque bit à 1 dans secret
# Attention : Qiskit est little-endian, on inverse l'index
for i, bit in enumerate(reversed(secret)):
    if bit == '1':
        qc.cx(i, n)

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

# Mesure
qc.measure(range(n), range(n))

sim = AerSimulator()
result = sim.run(qc, shots=1024).result()
print(result.get_counts())  # → {'101': 1024}

Piège courant : En Qiskit, les qubits sont indexés en little-endian. Si ta chaîne secrète est "101", le bit de poids fort est le qubit d’index le plus élevé. Oublie ça et tu lis s à l’envers ! En Q#, l’ordre est big-endian côté API — vérifie toujours la convention.