Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory - Archive ouverte HAL Access content directly
Conference Papers Year : 2020

Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory

(1, 2, 3) , (3, 2, 4) , (5) , (4, 2, 3)
1
2
3
4
5

Abstract

Inductive datatypes in programming languages allow users to define useful data structures such as natural numbers, lists, trees, and others. In this paper we show how inductive datatypes may be added to the quantum programming language QPL. We construct a sound categorical model for the language and by doing so we provide the first detailed semantic treatment of user-defined inductive datatypes in quantum programming. We also show our denotational interpretation is invariant with respect to big-step reduction, thereby establishing another novel result for quantum programming. Compared to classical programming, this property is considerably more difficult to prove and we demonstrate its usefulness by showing how it immediately implies computational adequacy at all types. To further cement our results, our semantics is entirely based on a physically natural model of von Neumann algebras, which are mathematical structures used by physicists to study quantum mechanics.

Dates and versions

hal-02995410 , version 1 (09-11-2020)

Identifiers

Cite

Romain Péchoux, Simon Perdrix, Mathys Rennela, Vladimir Zamdzhiev. Quantum Programming with Inductive Datatypes: Causality and Affine Type Theory. International Conference on Foundations of Software Science and Computation Structures, Apr 2020, Dublin, Ireland. pp.562-581, ⟨10.1007/978-3-030-45231-5_29⟩. ⟨hal-02995410⟩
74 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More