4.1 Algorithmes quantiques de base

Les algorithmes quantiques exploitent des phénomènes comme la superposition, l'intrication et l'interférence pour résoudre certains problèmes avec une efficacité supérieure à celle des algorithmes classiques. Cette section explore trois algorithmes fondamentaux : Deutsch-Jozsa, la transformation de Fourier quantique (QFT) et l'algorithme de Grover.

4.1.1 Algorithme de Deutsch-Jozsa

Cet algorithme démontre le premier avantage exponentiel de la computation quantique sur les problèmes de décision. Il permet de distinguer entre une fonction constante et une fonction équilibrée en un seul appel à une oracle.

• Problème de classification : Déterminer si une fonction booléenne est constante ou équilibrée.
• Parallélisme quantique : L'état superposé permet d'évaluer toutes les entrées simultanément.
• Effet de rétroaction de phase : Les phases accumulées par l'oracle sont exploitées via des interférences.

L’implémentation Qiskit suit une architecture modulaire avec génération automatique de circuits pour différentes fonctions, simulation via Aer et visualisation des résultats.

class DeutschJozsaSolver:
    def __init__(self, n_qubits):
        self.n = n_qubits
        # Construction du circuit avec registres d'entrée, auxiliaire et de mesure
        self.circuit = QuantumCircuit(QuantumRegister(n_qubits, 'input'),
                                     QuantumRegister(1, 'aux'),
                                     ClassicalRegister(n_qubits, 'c'))

    def initialize(self):
        # Création d'une superposition uniforme sur les qubits d'entrée
        self.circuit.h(range(self.n))
        # Préparation de l'état |−⟩ sur le qubit auxiliaire
        self.circuit.x(0)
        self.circuit.h(0)

    def build_oracle(self, func_type, seed=None):
        if func_type == "constant":
            # Oracle constant : aucun changement effectué
            pass
        elif func_type == "balanced":
            # Fonction équilibrée : CNOT contrôlés selon un masque aléatoire
            mask = [random.randint(0, 1) for _ in range(self.n)]
            for i, bit in enumerate(mask):
                if bit:
                    self.circuit.cx(i, self.n)

    def finalize(self):
        # Appliquer Hadamard sur les qubits d'entrée pour mesurer
        self.circuit.h(range(self.n))
        self.circuit.measure(range(self.n), range(self.n))

    def run_simulation(self, shots=1024):
        simulator = AerSimulator()
        compiled = transpile(self.circuit, simulator)
        job = simulator.run(compiled, shots=shots)
        return job.result().get_counts()

La performance est analysée en fonction du nombre de qubits, montrant que la probabilité de mesurer |0...0⟩ est proche de 1 pour les fonctions constantes et près de 0 pour les équilibrées.

4.1.2 Transformation de Fourier Quantique (QFT)

La QFT est un outil central dans de nombreux algorithmes quantiques, notamment pour l’estimation de phase.

• Implémentation exacte vs aprochée : La version AQFT réduit la profondeur en tronquant les rotations.
• Estimation de phase : Utilise la QFT inverse pour extraire la phase d’un état propre.
• Analyse spectrale : Appliquée à des signaux périodiques, elle permet de détecter les fréquences dominantes.

Un exemple montre la reconstruction d’un signal composé de deux fréquences à l’aide de la QFT quantique, comparée au FFT classique.

def apply_qft(circuit, qubits, inverse=False):
    n = len(qubits)
    for i in range(n):
        # Hadamard sur chaque qubit
        circuit.h(qubits[i])
        # Rotations contrôlées
        for j in range(1, n - i):
            angle = np.pi / (2 ** j)
            if inverse:
                angle = -angle
            circuit.cp(angle, qubits[i + j], qubits[i])
    # Inversion des bits si nécessaire
    for i in range(n // 2):
        circuit.swap(qubits[i], qubits[n - 1 - i])

Des analyses de précision montrent que la fidélité diminue lorsque les angles de rotation sont imparfaits, soulignant la sensibilité des algorithmes quantiques aux erreurs matérielles.

4.1.3 Algorithme de Grover

Grover offre une accélération quadratique pour la recherche dans une base de données non structurée.

• Amplification d'amplitude : Le diffusateur itère pour renforcer les états marqués.
• Interprétation géométrique : L’état évolue dans un plan formé par les états marqués et non-marqués.
• Optimisation des itérations : Le nombre optimal d’itérations est π/4√(N/M).

Une implémentation pour 3 qubits illustre la variation de la proabbilité de succès selon le nombre d’itérations, confirmant la théorie.

def build_grover_circuit(n, marked_states, iterations):
    qr = QuantumRegister(n, 'q')
    cr = ClassicalRegister(n, 'c')
    circ = QuantumCircuit(qr, cr)
    
    # Initialisation uniforme
    circ.h(qr)
    
    # Itérations de Grover
    for _ in range(iterations):
        # Oracle : appliquer -1 à l’état marqué
        for state in marked_states:
            bin_str = format(state, f'0{n}b')
            for i, b in enumerate(bin_str):
                if b == '0':
                    circ.x(i)
            circ.cz(*[i for i in range(n)])
            for i, b in enumerate(bin_str):
                if b == '0':
                    circ.x(i)
        
        # Diffuseur
        circ.h(qr)
        circ.x(qr)
        circ.cz(*[i for i in range(n)])
        circ.x(qr)
        circ.h(qr)
    
    circ.measure(qr, cr)
    return circ

Une analyse de scalabilité confirme que le nombre d’itérations croît comme √N, tandis que la profondeur du circuit augmente lentement.

4.2 Algorithme de Shor et estimation de phase

Shor transforme le problème de factorisation en une recherche de période, exploitant la QPE.

• Construction du circuit : Implémentation optimisée de U^x mod N pour petits N.
• Post-traitement classique : Algorithme des fractions continues extrait la période.
• Complexité ressource : Exige un grand nombre de qubits et une faible erreur.

Le code simule la factorisation de 15 et 21, illustrant la capacité de l'algorithme à retrouver les facteurs via l'estimation de phase.

def build_shor_circuit(N, a):
    n_count = 2 * math.ceil(math.log2(N))
    count_reg = QuantumRegister(n_count, 'count')
    work_reg = QuantumRegister(math.ceil(math.log2(N)), 'work')
    classical_reg = ClassicalRegister(n_count, 'result')
    
    circ = QuantumCircuit(count_reg, work_reg, classical_reg)
    
    # Superposition initiale
    circ.h(count_reg)
    circ.x(work_reg[0])
    
    # Oracle modulaire
    for i in range(n_count):
        angle = 2 * np.pi * (a ** (2**i)) / N
        circ.cp(angle, count_reg[i], work_reg[0])
    
    # QFT inverse
    iqft = QFT(num_qubits=n_count, inverse=True)
    circ.compose(iqft, qubits=count_reg, inplace=True)
    
    circ.measure(count_reg, classical_reg)
    return circ

Une analyse NISQ montre que même avec des architectures actuelles, les algorithmes quantiques comme Shor restent hors de portée sans correction d'erreurs.

4.2.2 Analyse de précision de l’estimation de phase

La qualité de l’estimation dépend du nombre de qubits utilisés et de la fiabilité des opérations.

• Relation précision-ressources : Plus de qubits → meilleure précision.
• IPEA : Algorithme itératif qui réduit la charge en qubits au prix de plusieurs exécutions.
• Faisabilité NISQ : Les limitations matérielles rendent les applications pratiques difficiles aujourd'hui.

Un comparatif entre QPE standard et IPEA montre un compromis entre profondeur, nombre de qubits et complexité classique.

def iterative_phase_estimation(phi, t_bits):
    measured_bits = []
    for k in range(t_bits):
        # Mesure d'un bit de phase à la fois
        angle = 2 * np.pi * phi * (2 ** (t_bits - k - 1))
        # Correction basée sur les bits précédents
        ...
        measured_bits.append(result_bit)
    return ''.join(measured_bits)

Les simulations montrent qu’une fidélité élevée nécessite des ressources considérables, mettant en évidence les défis à surmonter avant une mise en œuvre pratique.