One of the purposes of quantum programming languages is to express quantum programs, however a possibly more important reason is to provide a framework for reasoning about the programs expressing quantum algorithms -- and hence about quantum computation in general.
Indeed, in classical computer science it is frequent to express the reasoning behind a program via several formally-defined logics. These logics provide important frameworks in which to reason and prove properties about the computational processes. Often they arise via the study of type systems for the language. Related to our motivation there is already a quantum logic, which was developed before quantum computing, and which is not known to have a clear relation to quantum programs and algorithms.
The Linear-Algebraic Lambda-Calculus extends the Lambda-Calculus with the possibility to make arbitrary linear combinations of terms a.t+b.u. We want to set up a type system for it which is capable of such handling vectorial notions, i.e. were types themselves form a vector space. This is needed at a practical level for instance in order to prove normalization and unitarity properties of terms. There is also the intriguing question as to what logical meaning we can give these `superposition types'.
Joint work with Pablo Arrighi.
We consider a graph having a single quantum system sitting at each node. The entire compound system evolves in discrete time steps by iterating a global evolution G. Moreover we require that this global evolution G be unitary, in accordance with quantum theory, and that this global evolution G be causal, in accordance with special relativity. By causal we mean that information can only ever be transmitted at a bounded speed, the speed bound being quite naturally that of one edge of the underlying graph per iteration of G. We show that under these conditions the operator G is local; i.e. it can be put into the form of a quantum circuit made up with more elementary, unitary gates -- each acting solely upon neighbouring nodes.
Joint work with Vincent Nesme and Reinhard Werner.
Rencontre annuelle du projet Types, au centre Paul Langevin à Aussois, du 12 au 15 mai.
Groupe de travail pour comprendre ce qu'on pourra de la théorie géométrique de la complexité à la Ketan Mulmuley. On se basera sur ses articles introductifs et les vidéos de ses conférences à l'Institute for Advanced Study en février 2009.
Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution globale de ce processus ne semble pas dépendre de la topologie du graphe: dans un premier temps des régions, pavées par des motifs dépendant de la topologie du graphe, se forment rapidement. Puis dans un deuxième temps, les frontières entre ces régions évoluent jusqu'à devenir relativement stables. Nous étudions ce processus sous différentes topologies: arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que même si ce processus se comporte à priori globalement de la même manière sur n'importe quel graphe, modifier la topologie influence la façon dont les régions sont pavées (rayures, damiers), la structure et les mouvements des frontières entre les régions, l'ensemble limite, le temps de relaxation (le temps nécessaire pour que le processus atteigne une configuration de l'ensemble limite). Ainsi, Minorité entraîne des comportements riches et variés qui se révèlent difficile à analyser. Comprendre cette règle simple est néanmoins nécessaire avant de considérer des règles plus compliquées.
Les mots (finis ou pas, en dimension 1 ou supérieure) peuvent être vus comme des modèles de formules de la logique monadique du second ordre (MSO), une formule définissant alors un langage. Cette approche a été suivie avec succès en dimension 1 par Büchi et Elgot dans les années 60 : les langages ainsi définis sont exactement les langages rationnels. De plus toute formule MSO est dans ce contexte équivalente à une formule EMSO (quantification existentielle au second ordre suivie d'une formule au premier ordre).
Plus récemment, Giammarresi, Restivo, Seibert et Thomas ont reconsidéré ces résultats dans le cas des figures'', c'est à dire des mots bidimensionnels finis avec bords marqués : cette fois les formules EMSO définissent exactement les langagessofiques'' (projections de langages locaux), mais elles ne suffisent plus à capturer tous les langages définissable par une formule MSO.
L'objectif de cet exposé est de développer cette approche, en dimension 2, pour les sous-shifts (ensembles de configurations fermés topologiquement et invariants par décalages). Nous verrons alors que les sous-shifts sofiques (introduits par Weiss dans les années 70) ne correspondent pas aux sous-shifts définissables par formules EMSO. Nous donnerons néanmoins une caractérisation logique des sous-shifts sofiques et, inversement, nous donnerons une caractérisation ``combinatoire'' des ensembles de configurations définissables dans EMSO.
Je présente l'approche algébrique au lambda-calcul basée sur les algèbres de lambda abstraction et sur les algèbres de Boole, qui a permis d'étudier la structure du treillis des lambda théories et d'obtenir des résultats d'incomplétude pour le sémantique du lambda calcul. Depuis, je présente mon dernier résultat: la lambda théorie minimum extensionelle n'est pas la théorie d'une domaine de Scott réflexive.
Voir la page dédiée.
TBA
Voir la page dédiée.
On montre comment trouver de façon naturelle des solutions à de nombreuses équations récursives en autorisant des boucles dans les arènes. On équipe ensuite les arènes de fonctions de gain et on s'intéresse aux stratégies totales et gagnantes. On présente alors deux fonctions de gain naturelles sur les arènes à boucles, qui premettent de construire respectivement des algèbres initiales et des coalgèbres finales à de nombreux endofoncteurs continus. Finalement on applique ces constructions pour donner un modèle correct (et complet, en un sens faible) d'un calcul des séquents intuitionniste, étendu par des constructions syntaxiques pour les plus petits et plus grands points fixes.
Voir la page dédiée.
After defining polynomial functors and introducing their calculus in terms of certain bridge diagrams, I will survey some examples related to logic: Girard's normal functors, Jay and Cockett's shapely types, the containers of Abbott, Altenkirch and Ghani, multicategories after Lambek, Burroni, and Leinster, and finally trees. (This talk is based on a paper in preparation with Nicola Gambino.)
L'analyse de la langue naturelle est toujours un problème ouvert au sens où il n'a pas à ce jour d'outils disponible resolvant ce problème (qui est pourtant fini si l'on considère que la longueur des phrases est bornées par la plus longue phrase de Proust). Certaines approches reposent sur des concepts théoriques avancés (automates, théorie des types, jusqu'à MELL ou IMELL dans certains articles). Est-ce la bonne approche ? Ou bien juste le fait que l'algorithme est trop complexe pour être écrit à la main ? On va montrer que dypgen (Emmanuel Onzon) permet d'aller assez loin, sans toutefois analyser le présent résumé, en utilisant juste une juxtaposition d'idées au dessus des techniques récentes de parsing pour les grammaires hors contexte. Note: je n'expliquerai pas ce qu'il y a sous le capot de dypgen ... Pour ça, il faudra inviter Emmanuel Onzon.
TBA
A monad with arities'' is a monad T on some category K together with some extra data expressing the basicshapes'' of the operations involved in the structure of a T-algebra. There is a general result, called the nerve theorem, which in the case where K is a presheaf category, shows that the notion of monad with arities is an efficient reformulation of the notion of limit sketch''. The nerve theorem is so named because it generalises the characterisation of the simplicial sets that arise as nerves of categories. Other interesting instances of this result relevant for higher dimensional algebra involvelocal right adjoint monads'' -- such a T comes with a canonical choice of arities. These examples formalise the passage between the operadic and simplicial approaches to higher category theory.
Parmi les nombreuses suites remarquables étudiées en combinatoire des mots figurent les suites sturmiennes. Elles interviennent dans plusieurs domaines: dynamique symbolique, géométrie discrète, astronomie, cristallographie, etc. Elles sont d'autant plus remarquables par le fait qu'elles possèdent plusieurs caractérisations équivalentes. Entre autres, elles décrivent les droites discrètes de pentes irrationnelles. Parmi ces droites, la classe des (demies) droites passant par l'origine, appelées des suites sturmiennes standards, admet une caractérisation supplémentaire: il est possible de les construire en utilisant la fermeture palindromique itérative. La fermeture palindromique d'un mot fini w consiste à trouver le mot palindromique le plus court ayant comme préfixe le mot w. La fermeture palindromique itérative d'un mot fini w, noté Pal(w), est définie par Pal(a)=a et Pal(w)=(Pal(w_0...w_{n-1})w_n)^+, où u^+ désigne la fermeture palindromique et a est une lettre de l'alphabet. Ainsi, à tout mot sur un alphabet à 2 lettres, on peut lui associer une suite sturmienne standard en appliquant l'opérateur de fermeture palindromique itérative. Plus récemment, cette notion a été généralisée à des pseudopalindromes, c'est-à-dire des mots restant stables non pas sous l'opération d'image miroir, mais plutôt sous l'action d'un antimorphisme involutif.
D'autre part, certaines suites points fixes sous un opérateur se sont révélées être bien mystérieuses; il suffit de penser au célèbre mot de Kolakoski K=221121221221121122... qui est le point fixe sous l'opérateur de codage par blocs (le mot est égal à ses longueurs de blocs de lettres: 2'' lettres 2,2'' lettres 1, 1'' lettre 2,1'' lettre 1, ...). Plusieurs propriétés combinatoires de ce mot sont encore inconnues: la fréquence des lettres, la récurrence des facteurs, la fermeture de l'ensemble de ses facteurs sous l'image miroir et la complémentation, etc.
Ainsi, avec D. Jamet et G. Richomme, nous nous sommes intéressés à l'étude des points fixes sous l'opérateur de fermeture pseudopalindromique itérative. Dans mon exposé, je vais présenter certains de nos résultats concernant les propriétés combinatoires de ces mots et faisant intervenir entre autres des développements en fractions continues et des morphismes. Je terminerai en proposant certains problèmes ouverts concernant l'algébricité de la ``pente'' de certains de ces points fixes et l'existence d'exposants critiques.
Voir la page dédiée.
Un problème fondamental dans la comparaison de différents modèles du parallélisme et de la concurrence est celui de définir la notion de codage, ou de traduction. A ce jour, parmi toutes les notions universellement acceptées de codage entre modèles concurrents, il n'en existe aucune qui s'impose nettement sur les autres. Nous proposons d'étudier la notion de codage en partant de la vision du calcul comme réécriture, et en utilisant des notions venant de la théorie des catégories d'ordre supérieur et de la théorie des structures d'évenemments de Winskel.