The Geometry of Parallelism: Classical, Probabilistic, and Quantum Effects

Ugo Dal Lago (1, 2) , Claudia Faggian (3) , Benoît Valiron (4, 5) , Akira Yoshimizu (6)

1 DISI - Dipartimento di Scienze dell'Informazione [Bologna]
2 FOCUS - Foundations of Component-based Ubiquitous Systems
3 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
4 MODHEL - LRI - Modélisation hétérogène (LRI)
5 CentraleSupélec
6 UTokyo - The University of Tokyo

We introduce a Geometry of Interaction model for higher-order quantum computation, and prove its adequacy for a full quantum programming language in which entanglement, duplication, and recursion are all available. Our model comes with a multi-token machine, a proof net system, and a PCF-style language. The approach we develop is not specific to quantum computation, and our model is an instance of a new framework whose main feature is the ability to model commutative effects in a parallel setting. Being based on a multi-token machine equipped with a memory, it has a concrete nature which makes it well suited for building low-level operational descriptions of higher-order languages.

Domaines: Logique en informatique [cs.LO]; Informatique et langage [cs.CL]; Physique Quantique [quant-ph]

Ugo Dal Lago, Claudia Faggian, Benoît Valiron, Akira Yoshimizu. The Geometry of Parallelism: Classical, Probabilistic, and Quantum Effects. POPL 2017 - 44th ACM SIGPLAN Symposium on Principles of Programming Languages, Jan 2017, Paris, France. pp.833-845, ⟨10.1145/3009837.3009859⟩. ⟨hal-01474620⟩