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

Electronic Notes in Theoretical Computer Science

Towards a Quantum Calculus

Philippe Jorrand, Simon Perdrix

Published Jul 1, 2008• 2 citations
Publisher

Abstract

The aim of this paper is to introduce a general model of quantum computation, the quantum calculus: both unitary transformations and projective measurements are allowed; furthermore a complete classical control, including conditional structures and loops, is available. Complementary to its operational semantics, we introduce a pure denotational semantics for the quantum calculus. Based on probabilistic power domains [Jones, C. and G. D. Plotkin, A probabilistic powerdomain of evaluations, in: LICS, 1989, pp. 186–195. URL http://homepages.inf.ed.ac.uk/gdp/publications/Prob_Powerdomain.pdf], this pure denotational semantics associates with any description of a computation in the quantum calculus its action in a mathematical setting. Adequacy between operational and pure denotational semantics is established. Additionally to this pure denotational semantics, an observable denotational semantics is introduced. Following the work by Selinger, this observable denotational semantics is based on density matrices and super-operators. Finally, we establish an exact abstraction connection between these two semantics.

DOI
10.1016/j.entcs.2008.04.019

Related papers

On a Fully Abstract Model for a Quantum Linear Functional Language

Peter Selinger, Benoît Valiron

This paper studies the linear fragment of the programing language for quantum computation with classical control described in [Selinger, P. and B. Valiron, A lambda calculus for quantum computation with classical control, in: P. Urzyczyn, editor, Proceedings of the Seventh International Conference on Typed Lambda Calculi and Applications (TLCA 2005), Lecture Notes in Computer Science 3461 (2005), pp. 354–368]. We sketch the language, and discuss equivalence of terms. We also describe a fully abstract denotational semantics based on completely positive maps.

Electronic Notes in Theoretical Computer Science•Jul 1, 2008•52 citations

On a measurement-free quantum lambda calculus with classical control

Ugo Dal Lago, Andrea Masini, Margherita Zorzi

We study a measurement-free, untyped λ-calculus with quantum data and classical control. This work arises from previous proposals by Selinger and Valiron, and Van Tonder. We focus on operational and expressiveness issues, rather than (denotational) semantics. We prove subject reduction and confluence, and a standardisation theorem. Moreover, we prove the computational equivalence of the proposed calculus with a suitable class of quantum circuit families.

Mathematical Structures in Computer Science•Feb 16, 2009•21 citations

Semantics for a higher-order functional programming language for quantum computation

Benoît Valiron

The objective of this thesis is to develop a semantics for higher-order quantum information. Following the work done in the author's M.Sc. thesis, we study a lambda calculus for quantum computation with classical control. The language features two important properties. The first one, arising from the so-called no-cloning theorem of quantum computation, is the need for a distinction between duplicable and non-duplicable elements. For keeping track of duplicability at higher order, we use a type system inspired by the resource-sensitive linear logic. The second important aspect is the probability inherent to measurement, the only operation for retrieving classical data from quantum data. This forces us into choosing a reduction strategy for being able to define an operational semantics. We address the question of a denotational semantics in two respects. First, we restrict the study to the strictly linear aspect of the language. Doing so, we suppress the need for distinguishing between duplicable and non-duplicable elements and we can focus on the description of quantum features at higher order. Using the category of completely positive maps as a framework, we build a fully abstract denotational model of the strictly linear fragment of the language. The study of the full language is more demanding. For dealing with the probabilistic aspect of the language, we use a method inspired by Moggi and build a computational model with a distinction between values and computations. For the distinction between duplicability and non-duplicability in the calculus, we adapt Bierman's linear category, where the duplication is considered as a comonad with specific properties. The resulting model is what we call a linear category for duplication. Finally, we only focus on the fragment of the language that contains the aforementioned elements, and remove the classical Boolean and quantum Boolean features to get a generic computational linear lambda-calculus. In this idealized setting, we show that such a language have a full and complete interpretation in a linear category for duplication.

•Jan 1, 2008•9 citations

Full abstraction for the quantum lambda-calculus

Pierre Clairambault, Marc de Visme

Quantum programming languages permit a hardware independent, high-level description of quantum algorithms. In particular, the quantum λ-calculus is a higher-order language with quantum primitives, mixing quantum data and classical control. Giving satisfactory denotational semantics to the quantum λ-calculus is a challenging problem that has attracted significant interest. In the past few years, both static (the quantum relational model) and dynamic (quantum game semantics) denotational models were given, with matching computational adequacy results. However, no model was known to be fully abstract. Our first contribution is a full abstraction result for the games model of the quantum λ-calculus. Full abstraction holds with respect to an observational quotient of strategies, obtained by summing valuations of all states matching a given observable. Our proof method for full abstraction extends a technique recently introduced to prove full abstraction for probabilistic coherence spaces with respect to probabilistic PCF. Our second contribution is an interpretation-preserving functor from quantum games to the quantum relational model, extending a long line of work on connecting static and dynamic denotational models. From this, it follows that the quantum relational model is fully abstract as well. Altogether, this gives a complete denotational landscape for the semantics of the quantum λ-calculus, with static and dynamic models related by a clean functorial correspondence, and both fully abstract.

Proceedings of the ACM on Programming Languages•Dec 20, 2019•37 citations

A Hierarchy of Quantum Semantics

Simon Perdrix

Several domains [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004; B. Coecke and K. Martin. A partial order on classical and quantum states. Technical report, PRG-RR-02-07, 2002; Ph. Jorrand and S. Perdrix. Towards a quantum calculus. In To appear in Proceedings of the 4th International Workshop on Quantum Programming Languages, ENTCS, 2006; P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004] can be used to define the semantics of quantum programs. Among them Abramsky [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004] has introduced a semantics based on probabilistic power domains, whereas the one by Selinger [P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004] associates with every program a completely positive map. In this paper, we mainly introduce a semantical domain based on admissible transformations, i.e. multisets of linear operators. In order to establish a comparison with existing domains, we introduce a simple quantum imperative language (QIL), equipped with three different denotational semantics, called pure, observable, and admissible respectively. The pure semantics is a natural extension of probabilistic (classical) semantics and is similar to the semantics proposed by Abramsky [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004]. The observable semantics, à la Selinger [P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004], associates with any program a superoperator over density matrices. Finally, we introduce an admissible semantics which associates with any program an admissible transformation. These semantics are not equivalent, but exact abstraction [P. Cousot. Types as abstract interpretations. In POPL, pages 316–331, 1997] or interpretation relations are established between them, leading to a hierarchy of quantum semantics.

Electronic Notes in Theoretical Computer Science•Nov 1, 2008•6 citations

The measurement calculus

Vincent Danos, Elham Kashefi, Prakash Panangaden

Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements and expressiveness theorems. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.

arXiv:0704.1263•Journal of the ACM•Apr 1, 2007•234 citations
The aim of this paper is to introduce a general model of quantum computation, the quantum calculus: both unitary transformations and projective measurements are allowed; furthermore a complete classical control, including conditional structures and loops, is available. Complementary to its operational semantics, we introduce a pure denotational semantics for the quantum calculus. Based on probabilistic power domains [Jones, C. and G. D. Plotkin, A probabilistic powerdomain of evaluations, in: LICS, 1989, pp. 186–195. URL http://homepages.inf.ed.ac.uk/gdp/publications/Prob_Powerdomain.pdf], this pure denotational semantics associates with any description of a computation in the quantum calculus its action in a mathematical setting. Adequacy between operational and pure denotational semantics is established. Additionally to this pure denotational semantics, an observable denotational semantics is introduced. Following the work by Selinger, this observable denotational semantics is based on density matrices and super-operators. Finally, we establish an exact abstraction connection between these two semantics.
This paper studies the linear fragment of the programing language for quantum computation with classical control described in [Selinger, P. and B. Valiron, A lambda calculus for quantum computation with classical control, in: P. Urzyczyn, editor, Proceedings of the Seventh International Conference on Typed Lambda Calculi and Applications (TLCA 2005), Lecture Notes in Computer Science 3461 (2005), pp. 354–368]. We sketch the language, and discuss equivalence of terms. We also describe a fully abstract denotational semantics based on completely positive maps.
The objective of this thesis is to develop a semantics for higher-order quantum information. Following the work done in the author's M.Sc. thesis, we study a lambda calculus for quantum computation with classical control. The language features two important properties. The first one, arising from the so-called no-cloning theorem of quantum computation, is the need for a distinction between duplicable and non-duplicable elements. For keeping track of duplicability at higher order, we use a type system inspired by the resource-sensitive linear logic. The second important aspect is the probability inherent to measurement, the only operation for retrieving classical data from quantum data. This forces us into choosing a reduction strategy for being able to define an operational semantics. We address the question of a denotational semantics in two respects. First, we restrict the study to the strictly linear aspect of the language. Doing so, we suppress the need for distinguishing between duplicable and non-duplicable elements and we can focus on the description of quantum features at higher order. Using the category of completely positive maps as a framework, we build a fully abstract denotational model of the strictly linear fragment of the language. The study of the full language is more demanding. For dealing with the probabilistic aspect of the language, we use a method inspired by Moggi and build a computational model with a distinction between values and computations. For the distinction between duplicability and non-duplicability in the calculus, we adapt Bierman's linear category, where the duplication is considered as a comonad with specific properties. The resulting model is what we call a linear category for duplication. Finally, we only focus on the fragment of the language that contains the aforementioned elements, and remove the classical Boolean and quantum Boolean features to get a generic computational linear lambda-calculus. In this idealized setting, we show that such a language have a full and complete interpretation in a linear category for duplication.
Quantum programming languages permit a hardware independent, high-level description of quantum algorithms. In particular, the quantum λ-calculus is a higher-order language with quantum primitives, mixing quantum data and classical control. Giving satisfactory denotational semantics to the quantum λ-calculus is a challenging problem that has attracted significant interest. In the past few years, both static (the quantum relational model) and dynamic (quantum game semantics) denotational models were given, with matching computational adequacy results. However, no model was known to be fully abstract. Our first contribution is a full abstraction result for the games model of the quantum λ-calculus. Full abstraction holds with respect to an observational quotient of strategies, obtained by summing valuations of all states matching a given observable. Our proof method for full abstraction extends a technique recently introduced to prove full abstraction for probabilistic coherence spaces with respect to probabilistic PCF. Our second contribution is an interpretation-preserving functor from quantum games to the quantum relational model, extending a long line of work on connecting static and dynamic denotational models. From this, it follows that the quantum relational model is fully abstract as well. Altogether, this gives a complete denotational landscape for the semantics of the quantum λ-calculus, with static and dynamic models related by a clean functorial correspondence, and both fully abstract.
Several domains [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004; B. Coecke and K. Martin. A partial order on classical and quantum states. Technical report, PRG-RR-02-07, 2002; Ph. Jorrand and S. Perdrix. Towards a quantum calculus. In To appear in Proceedings of the 4th International Workshop on Quantum Programming Languages, ENTCS, 2006; P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004] can be used to define the semantics of quantum programs. Among them Abramsky [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004] has introduced a semantics based on probabilistic power domains, whereas the one by Selinger [P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004] associates with every program a completely positive map. In this paper, we mainly introduce a semantical domain based on admissible transformations, i.e. multisets of linear operators. In order to establish a comparison with existing domains, we introduce a simple quantum imperative language (QIL), equipped with three different denotational semantics, called pure, observable, and admissible respectively. The pure semantics is a natural extension of probabilistic (classical) semantics and is similar to the semantics proposed by Abramsky [S. Abramsky. A Cook's tour of a simple quantum programming language. 3rd International Symposium on Domain Theory, Xi'an, China, May 2004]. The observable semantics, à la Selinger [P. Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004], associates with any program a superoperator over density matrices. Finally, we introduce an admissible semantics which associates with any program an admissible transformation. These semantics are not equivalent, but exact abstraction [P. Cousot. Types as abstract interpretations. In POPL, pages 316–331, 1997] or interpretation relations are established between them, leading to a hierarchy of quantum semantics.
Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements and expressiveness theorems. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.