TypiCal

Intervenant: Simon Perdix

Date et lieu: 30/04/09 à 14h, salle de séminaires du LPTP

Résumé: Le calcul quantique par mesures, introduit par Briegel et Raussendorf, est non seulement une des plus prometteuses propositions de réalisation physique de l'ordinateur quantique, mais ouvre aussi de nouvelles perspectives théoriques, notamment en termes de parallélisation des opérations quantiques. Dans cet exposé, je présenterai le measurement calculus, introduit par Danos, Kashefi et Panangaden, un cadre formel permettant d'étudier les propriétés du calcul quantique par mesures. La mesure, brique de base de ce modèle, a une évolution fondamentalement probabiliste. Aussi, l'existence d'une évolution globalement déterministe dépend de l'état initial du calcul qui est représenté par un graphe. Nous montrons que l'existence d'un flot généralisé dans ce graphe est une condition nécessaire et suffisante à l'existence d'une exécution globalement déterministe. De plus, nous introduisons un algorithme classique efficace permettant de décider si un graphe donné admet un flot généralisé.