Ce micro-stage offert en collaboration avec l'entreprise Multiverse Computing et l'Institut Quantique de l'Université Sherbrooke.

Cette activité est offerte en anglais.

Un micro-stage complété te permet d’obtenir une attestation de réussite de l'Université Sherbrooke.

L’algorithme de Grover, élaboré en 1996 par Lov Grover, est souvent présenté comme pouvant effectuer une recherche dans une base de données non ordonnée avec un gain quadratique en efficacité par rapport à un algorithme classique équivalent. En particulier, cet algorithme est bien adapté à la résolution de problème de satisfiabilité (SAT), c’est-à-dire un problème qui fait intervenir un certain nombre de variables booléennes (vrai ou faux) mise en relation par des opérateurs logiques (et, ou, non) pour générer des propositions logiques. Si, pour un ensemble de valeurs des variables, toutes les propositions (critères) sont respectées, on dit que le problème est satisfait. Dans ce micro-stage nous allons voir et comprendre ce jargon en appliquant l’algorithme de Grover à des problèmes de satisfiabilité bien concrets.

Accueil et présentation de l’Institut quantique 

Perspectives d’emploi dans le domaine de la programmation quantique par l’entreprise 

Partie 1 : Théorie 

• Les problèmes de satisfiabilité
  • Formules logiques
  • Forme normale conjonctive (CNF)
• L’algorithme de Grover
  • L’oracle
  • Le diffuseur
  • Le principe de fonctionnement de l’algorithme
• La construction d’un oracle pour un problème de satisfiabilité
  • Règle de De Morgan
  • Logique booléenne et circuit quantique

Partie 2 : Mise en pratique 

Programmation sur un simulateur d’ordinateur quantique incluant des exercices pratiques et les sujets suivants :

• Construction du diffuseur
• Construction d’un oracle spécifique à un problème
• Survol d’un compilateur d’oracle pour CNF