Wave-Style Token Machines and Quantum Lambda Calculi

Ugo Dal Lago
(Università di Bologna & INRIA)
Margherita Zorzi
(Università di Verona)

Particle-style token machines are a way to interpret proofs and programs, when the latter are written following the principles of linear logic. In this paper, we show that token machines also make sense when the programs at hand are those of a simple quantum lambda-calculus with implicit qubits. This, however, requires generalising the concept of a token machine to one in which more than one particle travel around the term at the same time. The presence of multiple tokens is intimately related to entanglement and allows us to give a simple operational semantics to the calculus, coherently with the principles of quantum computation.

In Sandra Alves and Iliano Cervesato: Proceedings Third International Workshop on Linearity (LINEARITY 2014), Vienna, Austria, 13th July, 2014, Electronic Proceedings in Theoretical Computer Science 176, pp. 64–78.
Published: 16th February 2015.

ArXived at: http://dx.doi.org/10.4204/EPTCS.176.6 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org