Game semantics for quantum programming

Clairambault, Pierre and De Visme, Marc and Winskel, Glynn (2019) Game semantics for quantum programming. Proceedings of the ACM on Programming Languages (PACMPL), 3 (POPL). 32. ISSN 2475-1421 (https://doi.org/10.1145/3290345)

[thumbnail of Clairambault-etal-PAPL-2019-Game-semantics-for-quantum]
Preview
 Text. Filename: Clairambault_etal_PAPL_2019_Game_semantics_for_quantum.pdf
Final Published Version
License: Creative Commons Attribution 4.0 logo
Download (481kB)| Preview

Abstract

Quantum programming languages permit a hardware independent, high-level description of quantum algo rithms. In particular, the quantum lambda-calculus is a higher-order programming language with quantum primitives, mixing quantum data and classical control. Giving satisfactory denotational semantics to the quantum lambda-calculus is a challenging problem that has attracted significant interest in the past few years. Several models have been proposed but for those that address the whole quantum λ-calculus, they either do not represent the dynamics of computation, or they lack the compositionality one often expects from denotational models. In this paper, we give the first compositional and interactive model of the full quantum lambda-calculus, based on game semantics. To achieve this we introduce a model of quantum games and strategies, combining quantum data with a representation of the dynamics of computation inspired from causal models of concurrent systems. In this model we first give a computationally adequate interpretation of the affine fragment. Then, we extend the model with a notion of symmetry, allowing us to deal with replication. In this refined setting, we interpret and prove adequacy for the full quantum lambda-calculus. We do this both from a sequential and a parallel interpretation, the latter representing faithfully the causal independence between sub-computations.

  • Item type:Article
    ID code:74273
    Dates:
    Date
    Event
    2 January 2019
    Published
    9 October 2018
    Accepted
    Keywords:concurrent games, denotational semantics, game semantics, quantum lambda-calculus, Electronic computers. Computer science, Computational Theory and Mathematics
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:15 Oct 2020 12:57
    Last modified:05 Dec 2022 09:58
    URI:https://strathprints.strath.ac.uk/id/eprint/74273
CORE (COnnecting REpositories)