The dagger lambda calculus

Philip Atzemoglou
(University of Oxford)

We present a novel lambda calculus that casts the categorical approach to the study of quantum protocols into the rich and well established tradition of type theory. Our construction extends the linear typed lambda calculus with a linear negation of "trivialised" De Morgan duality. Reduction is realised through explicit substitution, based on a symmetric notion of binding of global scope, with rules acting on the entire typing judgement instead of on a specific subterm. Proofs of subject reduction, confluence, strong normalisation and consistency are provided, and the language is shown to be an internal language for dagger compact categories.

In Bob Coecke, Ichiro Hasuo and Prakash Panangaden: Proceedings of the 11th workshop on Quantum Physics and Logic (QPL 2014), Kyoto, Japan, 4-6th June 2014, Electronic Proceedings in Theoretical Computer Science 172, pp. 217–235.
Published: 28th December 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.172.15 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org