In this thesis, we present a new model for higher-order quantum programming languages. The proposed model is an adaptation of the probabilistic game semantics developed by Danos and Harmer: we expand it with quantum strategies which enable one to represent quantum states and quantum operations. Some of the basic properties of these strategies are established and then used to construct denotational semantics for three quantum programming languages. The first of these languages is a formalisation of the measurement calculus proposed by Danos et al. The other two are new: they are higher-order quantum programming languages. Previous attempts to define a denotational semantics for higher-order quantum programming languages have failed. We identify some of the key reasons for this and base the design of our higher-order languages on these observations. The game semantics proposed in this thesis is the first denotational semantics for a lambda-calculus equipped with quantum types and with extra operations which allow one to program quantum algorithms. The results presented validate the two different approaches used in the design of these two new higher-order languages: a first one where quantum states are used through references and a second one where they are introduced as constants in the language. The quantum strategies presented in this thesis allow one to understand the constraints that must be imposed on quantum type systems with higher-order types. The most significant constraint is the fact that abstraction over part of the tensor product of many unknown quantum states must not be allowed. Quantum strategies are a new mathematical model which describes the interaction between classical and quantum data using system-environment dialogues. The interactions between the different parts of a quantum system are described using the rich structure generated by composition of strategies. This approach has enough generality to be put in relation with other work in qu / Nous présentons dans cette thèse un nouveau modèlepour les langages de programmation quantique. Notre modèle est uneadaptation de la sémantique de jeux probabilistes définie par Danos etHarmer: nous y ajoutons des stratégies quantiquespour permettre la représentation des états et des opérations quantiques.Nous établissons quelques propriétés de base de ces stratégies. Cespropriétés sont ensuite utilisées pour construire des sémantiquesdénotationnelles pour trois langages de programmation quantique. Le premierlangage est une formalisation du calcul par mesures proposé par Danoset al. Les deux autres langages sont nouveaux: ce sont deslangages quantiques d'ordre supérieur dont la syntaxe a été construiteà partir d'observations expliquant l'échec des tentatives précédentespour construire une sémantique dénotationnelle pour de tels langages. La sémantique de jeux présentée dans cette thèseest la première sémantique dénotationnelle pour de telslambda-calculs équipés de types et d'opérations supplémentairespermettant la programmation d'algorithmes quantiques. Les résultatsprésentés valident les deux approches différentes utilitées dans laconception de ces deux nouveaux languages d'ordre supérieur: une premièreoù les états quantiques sont indirectement accessibles via desréférences et une seconde où ils sont introduit directement comme desconstantes dans le langage. Les stratégies quantiques présentéespermettent de comprendre les contraintes devant êtreimposées aux systèmes de type quantique comportant des types d'ordresupérieurs. La contrainte la plus importante est le fait que l'abstractionsur une partie d'un état quantique comportant plusieurs qbits inconnus doitêtre prohibée. Les stratégies quantiques constituent un nouveau modèle mathématique quidécrit l'interaction entre les données classiques et quantiques par desdialogues entre système et environnement. L'interaction entre les differentespar
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.40670 |
| Date | January 2009 |
| Creators | Delbecque, Yannick |
| Contributors | Prakash Panangaden (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0098 seconds