Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1904.08785 · ACM/IEEE Symposium on Logic in Computer Science (LICS)

Realizability in the Unitary Sphere

Alejandro Díaz-Caro, Mauricio Guillermo, Alexandre Miquel, Benoît Valiron

Published Jun 1, 2019• 32 citations
arXivHTMLPDF

Abstract

In this paper we present a semantics for a linear algebraic lambda-calculus based on realizability. This semantics characterizes a notion of unitarity in the system, answering a long standing issue. We derive from the semantics a set of typing rules for a simply-typed linear algebraic lambda-calculus, and show how it extends both to classical and quantum lambda-calculi.

DOI
10.1109/lics.2019.8785834

Related papers

Quantum Control in the Unitary Sphere: Lambda-S1 and its Categorical Model

Alejandro Díaz-Caro, Octavio Malherbe

In a recent paper, a realizability technique has been used to give a semantics of a quantum lambda calculus. Such a technique gives rise to an infinite number of valid typing rules, without giving preference to any subset of those. In this paper, we introduce a valid subset of typing rules, defining an expressive enough quantum calculus. Then, we propose a categorical semantics for it. Such a semantics consists of an adjunction between the category of distributive-action spaces of value distributions (that is, linear combinations of values in the lambda calculus), and the category of sets of value distributions.

arXiv:2012.05887•Logical Methods in Computer Science•Sep 12, 2022•19 citations

A concrete model for a typed linear algebraic lambda calculus

Alejandro Díaz-Caro, Octavio Malherbe

Abstract We give an adequate, concrete, categorical-based model for Lambda- ${\mathcal S}$ , which is a typed version of a linear-algebraic lambda calculus, extended with measurements. Lambda- ${\mathcal S}$ is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi: to forbid duplication of variables and to consider all lambda-terms as algebraic linear functions. The type system of Lambda- ${\mathcal S}$ has a superposition constructor S such that a type A is considered as the base of a vector space, while SA is its span. Our model considers S as the composition of two functors in an adjunction relation between the category of sets and the category of vector spaces over $\mathbb C$ . The right adjoint is a forgetful functor U, which is hidden in the language, and plays a central role in the computational reasoning.

arXiv:1806.09236•Mathematical Structures in Computer Science•Nov 21, 2023•9 citations

A Concrete Categorical Semantics of Lambda- S

Alejandro Díaz-Caro, Octavio Malherbe

Lambda- S is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi. One is to forbid duplication of variables, while the other is to consider all lambda-terms as algebraic linear functions. The type system of Lambda- S have a constructor S such that a type A is considered as the base of a vector space while S ( A ) is its span. A first semantics of this calculus have been given when first presented, with such an interpretation: superposed types are interpreted as vectors spaces while non-superposed types as their basis. In this paper we give a concrete categorical semantics of Lambda- S , showing that S is interpreted as the composition of two functors in an adjunction relation between the category of sets and the category of vector spaces over C . The right adjoint is a forgetful functor U , which is hidden in the language, and plays a central role in the computational reasoning.

Electronic Notes in Theoretical Computer Science•Aug 1, 2019•6 citations

Linear-algebraic lambda-calculus

Pablo J. Arrighi, Gilles Dowek

With a view towards models of quantum computation and/or the interpretation of linear logic, we define a functional language where all functions are linear operators by construction. A small step operational semantic (and hence an interpreter/simulator) is provided for this language in the form of a term rewrite system. The linear-algebraic lambda-calculus hereby constructed is linear in a different (yet related) sense to that, say, of the linear lambda-calculus. These various notions of linearity are discussed in the context of quantum programming languages. KEYWORDS: quantum lambda-calculus, linear lambda-calculus, $λ$-calculus, quantum logics.

arXiv:quant-ph/0501150•Jan 25, 2005•11 citations

Scalar System F for Linear-Algebraic Lambda-Calculus: Towards a Quantum Physical Logic

Pablo J. Arrighi, Alejandro Díaz-Caro

The Algebraic lambda-calculus and the Linear-Algebraic lambda-calculus extend the lambda-calculus with the possibility of making arbitrary linear combinations of terms. In this paper we provide a fine-grained, System F-like type system for the linear-algebraic lambda-calculus. We show that this type system enjoys both the subject-reduction property and the strong-normalisation property, our main technical results. The latter yields a significant simplification of the linear-algebraic lambda-calculus itself, by removing the need for some restrictions in its reduction rules. But the more important, original feature of this scalar type system is that it keeps track of 'the amount of a type' that is present in each term. As an example of its use, we shown that it can serve as a guarantee that the normal form of a term is barycentric, i.e that its scalars are summing to one.

arXiv:0903.3741•Logical Methods in Computer Science•Mar 22, 2009•4 citations

A Lambda Calculus for Quantum Computation

André van Tonder

The classical lambda calculus may be regarded both as a programming language and as a formal algebraic system for reasoning about computation. It provides a computational model equivalent to the Turing machine and continues to be of enormous benefit in the classical theory of computation. We propose that quantum computation, like its classical counterpart, may benefit from a version of the lambda calculus suitable for expressing and reasoning about quantum algorithms. In this paper we develop a quantum lambda calculus as an alternative model of quantum computation, which combines some of the benefits of both the quantum Turing machine and the quantum circuit models. The calculus turns out to be closely related to the linear lambda calculi used in the study of linear logic. We set up a computational model and an equational proof system for this calculus, and we argue that it is equivalent to the quantum Turing machine.

arXiv:quant-ph/0307150•SIAM Journal on Computing•Jan 1, 2004•206 citations
In this paper we present a semantics for a linear algebraic lambda-calculus based on realizability. This semantics characterizes a notion of unitarity in the system, answering a long standing issue. We derive from the semantics a set of typing rules for a simply-typed linear algebraic lambda-calculus, and show how it extends both to classical and quantum lambda-calculi.
In a recent paper, a realizability technique has been used to give a semantics of a quantum lambda calculus. Such a technique gives rise to an infinite number of valid typing rules, without giving preference to any subset of those. In this paper, we introduce a valid subset of typing rules, defining an expressive enough quantum calculus. Then, we propose a categorical semantics for it. Such a semantics consists of an adjunction between the category of distributive-action spaces of value distributions (that is, linear combinations of values in the lambda calculus), and the category of sets of value distributions.
Abstract We give an adequate, concrete, categorical-based model for Lambda- S{\mathcal S}S , which is a typed version of a linear-algebraic lambda calculus, extended with measurements. Lambda- S{\mathcal S}S is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi: to forbid duplication of variables and to consider all lambda-terms as algebraic linear functions. The type system of Lambda- S{\mathcal S}S has a superposition constructor S such that a type A is considered as the base of a vector space, while SA is its span. Our model considers S as the composition of two functors in an adjunction relation between the category of sets and the category of vector spaces over C\mathbb CC . The right adjoint is a forgetful functor U, which is hidden in the language, and plays a central role in the computational reasoning.
Lambda- S is an extension to first-order lambda calculus unifying two approaches of non-cloning in quantum lambda-calculi. One is to forbid duplication of variables, while the other is to consider all lambda-terms as algebraic linear functions. The type system of Lambda- S have a constructor S such that a type A is considered as the base of a vector space while S ( A ) is its span. A first semantics of this calculus have been given when first presented, with such an interpretation: superposed types are interpreted as vectors spaces while non-superposed types as their basis. In this paper we give a concrete categorical semantics of Lambda- S , showing that S is interpreted as the composition of two functors in an adjunction relation between the category of sets and the category of vector spaces over C . The right adjoint is a forgetful functor U , which is hidden in the language, and plays a central role in the computational reasoning.
With a view towards models of quantum computation and/or the interpretation of linear logic, we define a functional language where all functions are linear operators by construction. A small step operational semantic (and hence an interpreter/simulator) is provided for this language in the form of a term rewrite system. The linear-algebraic lambda-calculus hereby constructed is linear in a different (yet related) sense to that, say, of the linear lambda-calculus. These various notions of linearity are discussed in the context of quantum programming languages. KEYWORDS: quantum lambda-calculus, linear lambda-calculus, λλλ-calculus, quantum logics.
The Algebraic lambda-calculus and the Linear-Algebraic lambda-calculus extend the lambda-calculus with the possibility of making arbitrary linear combinations of terms. In this paper we provide a fine-grained, System F-like type system for the linear-algebraic lambda-calculus. We show that this type system enjoys both the subject-reduction property and the strong-normalisation property, our main technical results. The latter yields a significant simplification of the linear-algebraic lambda-calculus itself, by removing the need for some restrictions in its reduction rules. But the more important, original feature of this scalar type system is that it keeps track of 'the amount of a type' that is present in each term. As an example of its use, we shown that it can serve as a guarantee that the normal form of a term is barycentric, i.e that its scalars are summing to one.
The classical lambda calculus may be regarded both as a programming language and as a formal algebraic system for reasoning about computation. It provides a computational model equivalent to the Turing machine and continues to be of enormous benefit in the classical theory of computation. We propose that quantum computation, like its classical counterpart, may benefit from a version of the lambda calculus suitable for expressing and reasoning about quantum algorithms. In this paper we develop a quantum lambda calculus as an alternative model of quantum computation, which combines some of the benefits of both the quantum Turing machine and the quantum circuit models. The calculus turns out to be closely related to the linear lambda calculi used in the study of linear logic. We set up a computational model and an equational proof system for this calculus, and we argue that it is equivalent to the quantum Turing machine.