IQRO35 · Informatique quantique et recherche opérationnelle¶

En FISA, c'est la seule UE de tout le cursus qui traite du quantique — sans UE d'introduction pour la précéder. Angle algorithmique et complexité, avec accès annoncé à de vraies machines. Cinq compétences cotées « Expert », et une partie pratique substantielle avec Qiskit sur de vraies machines.

Fiche signalétique¶


Code	IQRO35 (modules IQUA35 et AQRO35)
Crédits	5 ECTS
Semestre	5, spécialisation — vendredi après-midi
Responsable	WATEL Dimitri
Concurrentes sur le créneau	aucune sur ce créneau
Choix	Une des trois UE de spécialisation, en accord avec l'entreprise
Prérequis	Analyse, algèbre, théorie des graphes, programmation impérative, logique, optimisation mathématique. Recherche opérationnelle, modèles de calcul, compléments de RO et Optimisation 1 conseillés
Effectif max	30

Ce que dit la brochure¶

Objectifs cités :

« Ce cours a pour objectif de former les apprenants à l'informatique quantique. A l'issue du cours, les apprenants maîtriseront les concepts permettant de concevoir des algorithmes quantiques pour des problèmes de décision ou d'optimisation, d'estimer la complexité de ces algorithmes et la classe de complexité des problèmes étudiés, et d'utiliser les outils existants (langages de programmation, simulateurs et accès à de vraies machines quantiques), notamment pour résoudre des problèmes classiques de recherche opérationnelle. »

Module 1 · IQUA35, informatique quantique — « essentiellement théorique » :

Informatique quantique : quelques notions de mécanique quantique ; algèbre pour l'informatique quantique ; qubits, portes quantiques, algorithmes quantiques ; intérêts et limitations ; étude des algorithmes quantiques classiques (en particulier Deutsch-Jozsa, Grover et Shor) ; modèle alternatif des machines adiabatiques, recuit simulé quantique ; algorithme QAOA.

Complexité quantique : différence entre un algorithme probabiliste et un algorithme quantique ; machine de Turing quantique ; classes BQP et QMA.

Travaux pratiques : simulation des algorithmes avec Quirk.

Module 2 · AQRO35, algorithmes quantiques pour la recherche opérationnelle — « essentiellement constitué de travaux pratiques » :

apprentissage de Qiskit pour programmer des machines quantiques complexes ;
utilisation de Qiskit pour interroger des machines quantiques réelles ;
application de l'algorithme de Grover à la résolution exacte de problèmes de décision ou d'optimisation combinatoires ;
application de l'algorithme QAOA à la résolution approchée ;
petit état de l'art de la recherche en informatique quantique dans le domaine de la recherche opérationnelle.

Sur les grilles de compétences

La brochure FISA ne publie pas de grille de compétences par UE, contrairement à la brochure de la formation sous statut étudiant. Les cotations « Expert / Maîtrise / Intermédiaire » citées dans les éditions précédentes de ce document n'ont donc pas d'équivalent ici.

Ce que ça vaut pour le HPC¶

Faible en utilité directe, élevé en valeur intellectuelle.

Soyons clair : aucune compétition HPC étudiante ne comporte d'épreuve quantique, et l'UE ne vous fera pas gagner un seul GFLOPS. Mais trois choses valent d'être signalées.

1. La partie complexité est solide et transférable. Machines de Turing, classes de complexité, la distinction entre algorithme probabiliste et algorithme quantique, BQP et QMA. C'est de la théorie de la complexité rigoureuse, qui vous servira à raisonner sur la difficulté des problèmes bien au-delà du quantique. La distinction entre « ce problème est difficile » et « je ne connais pas d'algorithme efficace » est une compétence d'ingénieur.

2. L'accès à de vraies machines quantiques. La brochure l'annonce explicitement. C'est rare et c'est précieux : la différence entre un simulateur parfait et une machine NISQ bruitée est l'enseignement le plus important du domaine, et elle ne s'appréhende qu'en la constatant.

3. QAOA est du calcul hybride. L'algorithme fonctionne par boucle : un circuit quantique paramétré évalue une fonction de coût, un optimiseur classique ajuste les paramètres, et on itère. C'est donc un algorithme dont la performance dépend de la latence de communication entre le processeur classique et le processeur quantique — un problème d'architecture système, familier à quiconque a fait du GPU. Le pont avec le HPC est là, et il est intéressant à faire.

Ce que la formation sous statut étudiant ajoute, et que vous n'aurez pas

Les deux UE couvrent Shor, Grover, le recuit. Les angles diffèrent :

	INIQ24 — parcours étudiant	IQRO35 — votre UE
Orientation	Machines, matériel, intégration HPC/QC	Algorithmique, complexité, application à la RO
Public	Formation sous statut étudiant	Ouverte en FISA, spécialisation du S5
Outils	Émulateurs variés, recuit, Pasqal	Quirk puis Qiskit sur machines réelles
Théorie	Mécanique quantique, correction d'erreurs, BB84	Machine de Turing quantique, BQP, QMA
Application	IA quantique, intégration dans le HPC	Optimisation combinatoire

Le recouvrement est utile : voir deux fois Grover, une fois du point de vue du circuit et une fois du point de vue de la complexité, en consolide la compréhension.

Arriver prêt¶

⏱ 12 h :

Revoir la recherche opérationnelle. En FISA, ROFA24 (S4) et OSCO23 (S3) sont au tronc commun : vous avez donc déjà le socle. Ce qui manque et qui sert directement dans les TP, c'est la formulation QUBO — comment écrire un problème combinatoire en variables binaires quadratiques. Le recueil d'Andrew Lucas, Ising formulations of many NP problems, donne les formulations de dizaines de problèmes classiques. ⏱ 5 h.
Qiskit. Le tutoriel « Hello World » et la construction d'un premier circuit. ⏱ 4 h — comptez plus qu'en formation sous statut étudiant, où une UE d'introduction au quantique précédait celle-ci.
Créer un compte sur une plateforme d'accès à des machines quantiques (IBM Quantum propose un accès gratuit limité) et exécuter un circuit réel avant le cours. Constater le bruit. ⏱ 2 h.

Les prérequis conseillés, en FISA

IQRO35 conseille « Recherche opérationnelle, Modèles de calculs, Complément de recherche opérationnelle, Optimisation 1 ».

Bonne nouvelle : en FISA, ROFA24 (recherche opérationnelle) est au tronc commun du semestre 4, et OSCO23 (optimisation sans contrainte) au tronc commun du semestre 3. Le socle minimal existe donc pour tout le monde, contrairement à la formation sous statut étudiant où il fallait le combler seul.

Le point de friction : OPTU35, également conseillé, est une UE de spécialisation du lundi matin, en concurrence directe avec PDSP35. Vous ne pourrez pas avoir les deux. Si vous prenez PDSP35 — ce que ce document recommande —, complétez par la formulation QUBO et les problèmes combinatoires classiques, pour lesquels le recueil d'Andrew Lucas, Ising formulations of many NP problems, suffit largement.

Ressources¶

Priorité 1¶

La bibliographie de la fiche IQRO35 reste entièrement valable, en particulier Nielsen & Chuang et les notes de Watrous, ce dernier étant le plus orienté théorie de la complexité, donc le mieux ajusté à IQUA35.
Le Qiskit Textbook (Learn Quantum Computation using Qiskit), gratuit. C'est le support de la partie pratique.
Quirk (algassert.com/quirk), cité au programme, pour la simulation visuelle de circuits.

Priorité 2 — complexité et algorithmique¶

Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Le chapitre sur le calcul quantique (BQP, sa place par rapport à P, NP et PSPACE) est exactement au programme, et le reste du livre est la meilleure référence moderne en complexité.
Michael Sipser, Introduction to the Theory of Computation. Plus accessible, pour les machines de Turing et les classes de base.
Ryan O'Donnell, cours vidéo Quantum Computation and Information (Carnegie Mellon), orienté informatique théorique, c'est le meilleur cours vidéo pour cet angle.
Scott Aaronson, Quantum Computing Since Democritus, et son blog Shtetl-Optimized. Pour la culture critique du domaine : Aaronson est l'un des rares experts qui démonte publiquement les affirmations excessives, avec rigueur et humour.

Priorité 3 — QAOA, recuit, et l'optimisation quantique¶

Farhi, Goldstone, Gutmann, « A Quantum Approximate Optimization Algorithm » (2014), l'article fondateur de QAOA. Court et lisible.
Sur le recuit quantique et QUBO : la documentation de D-Wave Ocean, et les articles de synthèse sur la formulation de problèmes combinatoires en QUBO — le document de référence est le recueil de Andrew Lucas, « Ising formulations of many NP problems » (Frontiers in Physics, 2014), qui donne les formulations Ising ou QUBO de dizaines de problèmes classiques. Très utile pour les TP de l'UE.
La littérature critique : plusieurs travaux comparent rigoureusement QAOA et les solveurs classiques sur les mêmes instances, avec des conclusions souvent défavorables au quantique à l'échelle actuelle. Chercher « QAOA versus classical heuristics benchmark ». Citer ces travaux dans un rapport montre une maturité que les jurys apprécient.

Exercices¶

E1 · ★★ ⏱ 3 h — Grover pour SAT. Formuler une instance de 3-SAT à quelques variables, construire l'oracle correspondant en Qiskit, appliquer Grover, et vérifier qu'on retrouve une affectation satisfaisante. Compter les portes de l'oracle : vous constaterez que la construction de l'oracle est le coût dominant, ce qui est la limitation pratique majeure de Grover.

E2 · ★★ ⏱ 3 h — QUBO. Formuler trois problèmes combinatoires en QUBO, en suivant le recueil de Lucas : la coupe maximale (Max-Cut), le sac à dos, et la coloration de graphe. Résoudre les instances petites par force brute classique pour valider la formulation. C'est le prérequis de tout travail sur QAOA ou sur le recuit.

E3 · ★★★ ⏱ 4 h — QAOA sur Max-Cut. Implémenter QAOA en Qiskit pour une instance de Max-Cut sur un graphe de 6 à 10 sommets. Faire varier la profondeur \(p\) du circuit de 1 à 5 et mesurer le rapport d'approximation obtenu. Comparer à l'optimum exact et à une heuristique classique simple (recherche locale). Tracer le rapport d'approximation en fonction de \(p\), et le temps total (circuit plus optimisation classique).

E4 · ★★★ ⏱ 4 h — Simulateur parfait contre machine réelle. Exécuter le même circuit sur un simulateur sans bruit, sur un simulateur avec modèle de bruit, et sur une vraie machine quantique. Mesurer la distribution des résultats dans les trois cas et quantifier la dégradation. Puis augmenter progressivement la profondeur du circuit et déterminer à partir de quelle profondeur le résultat de la machine réelle devient indistinguable du bruit. C'est l'exercice le plus instructif de l'UE : il donne la mesure concrète de l'état de la technologie.

E5 · ★★★ ⏱ 4 h — Le comparatif honnête. Prendre un problème d'optimisation combinatoire de taille modeste, et le résoudre de quatre manières : un solveur de programmation linéaire en nombres entiers (GLPK ou un solveur libre équivalent), une métaheuristique classique (recuit simulé classique), QAOA en simulation, et QAOA sur machine réelle. Mesurer la qualité de la solution et le temps total. Rédiger la conclusion honnêtement — qui sera, à l'échelle actuelle, favorable aux méthodes classiques. Documenter cela rigoureusement vaut mieux qu'un rapport enthousiaste.

E6 · ★★★★ ⏱ 5 h — BQP et sa place. Exercice théorique : rédiger une note de quatre pages expliquant la position de BQP par rapport à P, BPP, NP et PSPACE, ce qui est démontré et ce qui est conjecturé, et pourquoi « BQP contient NP » n'est pas connu et pourquoi la plupart des spécialistes pensent que c'est faux. Sources : Arora & Barak, et le blog d'Aaronson. C'est l'exercice qui vous rendra capable de ne plus jamais dire de bêtise sur le sujet.

Projet¶

Projet IQRO35 · L'étude comparative quantique-classique

⏱ 30 h · ★★★

Sujet. Choisir un problème d'optimisation combinatoire et produire une étude comparative rigoureuse des approches classiques et quantiques.

Choisir un problème ayant une formulation QUBO connue : Max-Cut, coupe minimale multi-terminale, partitionnement de graphe, ordonnancement à machines parallèles, ou un problème issu d'un contexte HPC — par exemple le placement de processus MPI sur une topologie réseau, qui est un vrai problème de partitionnement de graphe et qui fait un lien élégant avec PRPA23.

Les six parties :

Le problème : définition formelle, classe de complexité, taille des instances réalistes.
Les formulations : PLNE, QUBO ou Ising, et la traduction en circuit QAOA. Compter les variables, les contraintes, les qubits nécessaires.
Les méthodes classiques de référence : un solveur exact, une métaheuristique, et si elle existe une heuristique gloutonne avec garantie d'approximation.
Les méthodes quantiques : QAOA en simulation à profondeur variable, QAOA sur machine réelle si l'accès le permet, et le recuit si vous avez accès à une machine adiabatique.
Le protocole expérimental : instances générées aléatoirement selon un modèle décrit, plusieurs tailles, plusieurs répétitions, métriques explicites (qualité de la solution, temps, nombre d'évaluations).
La conclusion : à quelle taille d'instance, si elle existe, la méthode quantique devient-elle compétitive ? Si elle ne l'est jamais dans votre étude, dire pourquoi : nombre de qubits insuffisant, bruit, coût de la boucle d'optimisation classique.

Ce qui fait la qualité du travail : la rigueur du protocole et l'honnêteté de la conclusion. Un rapport qui conclut « à l'échelle accessible en 2026, les méthodes classiques dominent, et voici précisément pourquoi et à partir de quel seuil cela pourrait changer » est un bon travail d'ingénieur. Un rapport qui conclut à l'avantage quantique sans protocole solide n'en est pas un.

Pourquoi ce projet. Parce que la capacité à évaluer une technologie émergente sans se laisser emporter est une compétence d'ingénieur rare et précieuse, et parce que l'exercice est transférable : vous ferez la même chose dans dix ans avec une autre technologie.

Erreurs fréquentes¶

Cinq erreurs

Oublier le coût de l'oracle. Grover donne \(O(\sqrt{N})\) évaluations de l'oracle, mais construire l'oracle peut coûter plus cher que résoudre le problème classiquement. C'est la limitation la plus sous-estimée.
Compter les qubits logiques en oubliant les qubits physiques. Un circuit de 50 qubits logiques tolérants aux fautes demanderait des dizaines de milliers de qubits physiques.
Comparer un QAOA simulé à un solveur classique. Une simulation de circuit quantique tourne sur un processeur classique : le comparatif « QAOA simulé plus rapide qu'un solveur » est absurde. Seule une exécution sur machine réelle, ou un comptage d'opérations élémentaires à architecture hypothétique, a un sens.
Ignorer la boucle d'optimisation classique. Dans QAOA, l'optimiseur classique fait des centaines à des milliers d'évaluations du circuit. Le coût total inclut la latence de chaque aller-retour, qui domine souvent.
Confondre garantie d'approximation et performance observée. QAOA à profondeur 1 sur Max-Cut a un rapport d'approximation démontré modeste, mais les performances observées sont parfois meilleures. Distinguer les deux est important, et c'est précisément le genre de nuance que l'UE demande.

Comment l'UE s'articule avec le reste¶

UE ou chapitre	Lien
IQRO35	L'UE d'introduction qui précède IQRO35 en formation sous statut étudiant, et que vous n'aurez pas
APMA11, APMA12 (1A)	Algèbre, probabilités, optimisation mathématique
ROFA24 (S4) et OSCO23 (S3)	Les prérequis de RO, au tronc commun FISA : acquis pour tout le monde
PRPA23 (S3)	Le placement de processus est un problème de partitionnement de graphe
MALE24 (S4, tronc commun) et MALE35 (S5)	Le pont avec l'apprentissage automatique

À retenir¶

IQRO35 en trois phrases

Aucune utilité en compétition, mais une valeur intellectuelle réelle : la partie complexité (machine de Turing quantique, BQP, QMA) est transférable, et l'accès annoncé à de vraies machines quantiques permet de mesurer soi-même l'écart entre le simulateur parfait et la réalité NISQ. Attention au trou de prérequis : en FISA le socle de recherche opérationnelle est acquis au tronc commun (ROFA24, OSCO23), mais il faut apprendre seul la formulation QUBO (recueil de Lucas, Ising formulations of many NP problems) et venir avec Qiskit déjà en main, aucune UE d'introduction au quantique ne précédant celle-ci. La qualité d'un travail dans cette UE se mesure à l'honnêteté du comparatif quantique-classique.

Fiche voisine : GIIG35 · Green IT.