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:1511.01569 · Electronic Proceedings in Theoretical Computer Science

Total and Partial Computation in Categorical Quantum Foundations

Kenta Cho

Published Nov 3, 2015• 7 citations
arXivHTMLPDF

Abstract

This paper uncovers the fundamental relationship between total and partial computation in the form of an equivalence of certain categories. This equivalence involves on the one hand effectuses, which are categories for total computation, introduced by Jacobs for the study of quantum/effect logic. On the other hand, it involves what we call FinPACs with effects; they are finitely partially additive categories equipped with effect algebra structures, serving as categories for partial computation. It turns out that the Kleisli category of the lift monad (-)+1 on an effectus is always a FinPAC with effects, and this construction gives rise to the equivalence. Additionally, state-and-effect triangles over FinPACs with effects are presented.

DOI
10.4204/eptcs.195.9

Related papers

Total and Partial Computation in Categorical Quantum Foundations

Kenta Cho

This paper uncovers the fundamental relationship between total and partial computation in the form of an equivalence of certain categories. This equivalence involves on the one hand effectuses, which are categories for total computation, introduced by Jacobs for the study of quantum/effect logic. On the other hand, it involves what we call FinPACs with effects; they are finitely partially additive categories equipped with effect algebra structures, serving as categories for partial computation. It turns out that the Kleisli category of the lift monad (−)+1 on an effectus is always a FinPAC with effects, and this construction gives rise to the equivalence. Additionally, state-and-effect triangles over FinPACs with effects are presented. 1

•Jan 1, 2015•15 citations

Effectuses from Monads

Bart Jacobs

Effectuses have recently been introduced as categorical models for quantum computation, with probabilistic and Boolean (classical) computation as special cases. These 'probabilistic' models are called commutative effectuses. All known examples of such commutative effectuses are Kleisli categories of a monad. This paper answers the open question what properties a monad should satisfy so that its Kleisli category is a (commutative) effectus. The relevant properties are: strong affineness and partial additivity, together with some non-triviality conditions.

Electronic Notes in Theoretical Computer Science•Oct 1, 2016•5 citations

Effectus of Quantum Probability on Relational Structures

Octavio Zapata

The notion of effectus from categorical logic is relevant in the emerging field of categorical probability theory. In some cases, stochastic maps are represented by maps in the Kleisli category of some probability monad. Quantum homomorphisms from combinatorics and quantum information theory are the Kleisli maps of certain sort of quantum monad. We show that the Kleisli category of this quantum monad is an effectus. This gives rise to notions of quantum probabilistic reasoning as predicates, validity, conditioning, and channels.

arXiv:2005.00209•Electronic Proceedings in Theoretical Computer Science•Apr 30, 2020•0 citations

An effect-theoretic reconstruction of quantum theory

John van de Wetering

An often used model for quantum theory is to associate to every physical system a C ∗ -algebra. From a physical point of view it is unclear why operator algebras would form a good description of nature. In this paper, we find a set of physically meaningful assumptions such that any physical theory satisfying these assumptions must embed into the category of finite-dimensional C ∗ -algebras. These assumptions were originally introduced in the setting of effectus theory, a categorical logical framework generalizing classical and quantum logic. As these assumptions have a physical interpretation, this motivates the usage of operator algebras as a model for quantum theory.In contrast to other reconstructions of quantum theory, we do not start with the framework of generalized probabilistic theories and instead use effect theories where no convex structure and no tensor product needs to be present. The lack of this structure in effectus theory has led to a different notion of pure maps. A map in an effectus is pure when it is a composition of a compression and a filter. These maps satisfy particular universal properties and respectively correspond to `forgetting' and `measuring' the validity of an effect.We define a pure effect theory (PET) to be an effect theory where the pure maps form a dagger-category and filters and compressions are adjoint. We show that any convex finite-dimensional PET must embed into the category of Euclidean Jordan algebras. Moreover, if the PET also has monoidal structure, then we show that it must embed into either the category of real or complex C ∗ -algebras, which completes our reconstruction.

arXiv:1801.05798•Compositionality•Dec 18, 2019•24 citations

Quantum Programs as Kleisli Maps

Abraham Westerbaan

Furber and Jacobs have shown in their study of quantum computation that the category of commutative C*-algebras and PU-maps (positive linear maps which preserve the unit) is isomorphic to the Kleisli category of a comonad on the category of commutative C*-algebras with MIU-maps (linear maps which preserve multiplication, involution and unit). [Furber and Jacobs, 2013] In this paper, we prove a non-commutative variant of this result: the category of C*-algebras and PU-maps is isomorphic to the Kleisli category of a comonad on the subcategory of MIU-maps. A variation on this result has been used to construct a model of Selinger and Valiron's quantum lambda calculus using von Neumann algebras. [Cho and Westerbaan, 2016]

arXiv:1501.01020•Electronic Proceedings in Theoretical Computer Science•Jan 1, 2017•13 citations

Categorical models of computation: Partially traced categories and presheaf models of quantum computation

Octavio Malherbe

This dissertation has two main parts. The first part deals with questions relating to Haghverdi and Scott's notion of partially traced categories. The main result is a representation theorem for such categories: we prove that every partially traced category can be faithfully embedded in a totally traced category. Also conversely, every monoidal subcategory of a totally traced category is partially traced, so this characterizes the partially traced categories completely. The main technique we use is based on Freyd's paracategories, along with a partial version of Joyal, Street, and Verity's Int construction. Along the way, we discuss some new examples of partially traced categories, mostly arising in the context of quantum computation. The second part deals with the construction of categorical models of higher-order quantum computation. We construct a concrete semantic model of Selinger and Valiron's quantum lambda calculus, which has been an open problem until now. We do this by considering presheaf categories over appropriate base categories arising from first-order quantum computation. The main technical ingredients are Day's convolution theory and Kelly and Freyd's notion of continuity of functors. We first give an abstract description of the properties required of the base categories for the model construction to work; then exhibit a specific example of base categories satisfying these properties.

arXiv:1301.5087•Jan 1, 2010•11 citations
This paper uncovers the fundamental relationship between total and partial computation in the form of an equivalence of certain categories. This equivalence involves on the one hand effectuses, which are categories for total computation, introduced by Jacobs for the study of quantum/effect logic. On the other hand, it involves what we call FinPACs with effects; they are finitely partially additive categories equipped with effect algebra structures, serving as categories for partial computation. It turns out that the Kleisli category of the lift monad (-)+1 on an effectus is always a FinPAC with effects, and this construction gives rise to the equivalence. Additionally, state-and-effect triangles over FinPACs with effects are presented.
This paper uncovers the fundamental relationship between total and partial computation in the form of an equivalence of certain categories. This equivalence involves on the one hand effectuses, which are categories for total computation, introduced by Jacobs for the study of quantum/effect logic. On the other hand, it involves what we call FinPACs with effects; they are finitely partially additive categories equipped with effect algebra structures, serving as categories for partial computation. It turns out that the Kleisli category of the lift monad (−)+1 on an effectus is always a FinPAC with effects, and this construction gives rise to the equivalence. Additionally, state-and-effect triangles over FinPACs with effects are presented. 1
Effectuses have recently been introduced as categorical models for quantum computation, with probabilistic and Boolean (classical) computation as special cases. These 'probabilistic' models are called commutative effectuses. All known examples of such commutative effectuses are Kleisli categories of a monad. This paper answers the open question what properties a monad should satisfy so that its Kleisli category is a (commutative) effectus. The relevant properties are: strong affineness and partial additivity, together with some non-triviality conditions.
The notion of effectus from categorical logic is relevant in the emerging field of categorical probability theory. In some cases, stochastic maps are represented by maps in the Kleisli category of some probability monad. Quantum homomorphisms from combinatorics and quantum information theory are the Kleisli maps of certain sort of quantum monad. We show that the Kleisli category of this quantum monad is an effectus. This gives rise to notions of quantum probabilistic reasoning as predicates, validity, conditioning, and channels.
An often used model for quantum theory is to associate to every physical system a C ∗ -algebra. From a physical point of view it is unclear why operator algebras would form a good description of nature. In this paper, we find a set of physically meaningful assumptions such that any physical theory satisfying these assumptions must embed into the category of finite-dimensional C ∗ -algebras. These assumptions were originally introduced in the setting of effectus theory, a categorical logical framework generalizing classical and quantum logic. As these assumptions have a physical interpretation, this motivates the usage of operator algebras as a model for quantum theory.In contrast to other reconstructions of quantum theory, we do not start with the framework of generalized probabilistic theories and instead use effect theories where no convex structure and no tensor product needs to be present. The lack of this structure in effectus theory has led to a different notion of pure maps. A map in an effectus is pure when it is a composition of a compression and a filter. These maps satisfy particular universal properties and respectively correspond to `forgetting' and `measuring' the validity of an effect.We define a pure effect theory (PET) to be an effect theory where the pure maps form a dagger-category and filters and compressions are adjoint. We show that any convex finite-dimensional PET must embed into the category of Euclidean Jordan algebras. Moreover, if the PET also has monoidal structure, then we show that it must embed into either the category of real or complex C ∗ -algebras, which completes our reconstruction.
Furber and Jacobs have shown in their study of quantum computation that the category of commutative C*-algebras and PU-maps (positive linear maps which preserve the unit) is isomorphic to the Kleisli category of a comonad on the category of commutative C*-algebras with MIU-maps (linear maps which preserve multiplication, involution and unit). [Furber and Jacobs, 2013] In this paper, we prove a non-commutative variant of this result: the category of C*-algebras and PU-maps is isomorphic to the Kleisli category of a comonad on the subcategory of MIU-maps. A variation on this result has been used to construct a model of Selinger and Valiron's quantum lambda calculus using von Neumann algebras. [Cho and Westerbaan, 2016]
This dissertation has two main parts. The first part deals with questions relating to Haghverdi and Scott's notion of partially traced categories. The main result is a representation theorem for such categories: we prove that every partially traced category can be faithfully embedded in a totally traced category. Also conversely, every monoidal subcategory of a totally traced category is partially traced, so this characterizes the partially traced categories completely. The main technique we use is based on Freyd's paracategories, along with a partial version of Joyal, Street, and Verity's Int construction. Along the way, we discuss some new examples of partially traced categories, mostly arising in the context of quantum computation. The second part deals with the construction of categorical models of higher-order quantum computation. We construct a concrete semantic model of Selinger and Valiron's quantum lambda calculus, which has been an open problem until now. We do this by considering presheaf categories over appropriate base categories arising from first-order quantum computation. The main technical ingredients are Day's convolution theory and Kelly and Freyd's notion of continuity of functors. We first give an abstract description of the properties required of the base categories for the model construction to work; then exhibit a specific example of base categories satisfying these properties.