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

Total and Partial Computation in Categorical Quantum Foundations

Kenta Cho

Published Jan 1, 2015• 15 citations
OpenAlex

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. 1

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.

arXiv:1511.01569•Electronic Proceedings in Theoretical Computer Science•Nov 3, 2015•7 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

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

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

The Structure of Partial Isometries

Peter Hines, Samuel L. Braunstein

It is well known that the “quantum logic” approach to the foundations of quantum mechanics is based on the subspace ordering of projectors on a Hilbert space. In this paper, we show that this is a special case of an ordering on partial isometries, introduced by Halmos and McLaughlin. Partial isometries have a natural physical interpretation, however, they are notoriously not closed under composition. In order to take a categorical approach, we demonstrate that the Halmos-McLaughlin partial ordering, together with tools from both categorical logic and inverse categories, allows us to form a category of partial isometries. This category can reasonably be considered a “categorification” of quantum logic – we therefore compare this category with Abramsky and Coecke's “compact closed categories” approach to foundations and with the “monoidal closed categories” view of categorical logic. This comparison illustrates a fundamental incompatibility between these two distinct approaches to the foundations of quantum mechanics. 9.1 Introduction As early as 1936, von Neumann and Birkhoff proposed treating projectors on Hilbert space as propositions about quantum systems (Birkhoff and von Neumann 1936), by direct analogy with classical order-theoretic approaches to logic. Boolean lattices arise as the Lindenbaum-Tarski algebras of propositional logics, and as the set of all projectors on a Hilbert space also forms an orthocomplemented lattice, the operations meet, join , and complement were analogously interpreted as the logical connectives conjunction, disjunction , and negation .

Cambridge University Press eBooks•Nov 30, 2009•10 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. 1
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.
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.
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.
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]
It is well known that the “quantum logic” approach to the foundations of quantum mechanics is based on the subspace ordering of projectors on a Hilbert space. In this paper, we show that this is a special case of an ordering on partial isometries, introduced by Halmos and McLaughlin. Partial isometries have a natural physical interpretation, however, they are notoriously not closed under composition. In order to take a categorical approach, we demonstrate that the Halmos-McLaughlin partial ordering, together with tools from both categorical logic and inverse categories, allows us to form a category of partial isometries. This category can reasonably be considered a “categorification” of quantum logic – we therefore compare this category with Abramsky and Coecke's “compact closed categories” approach to foundations and with the “monoidal closed categories” view of categorical logic. This comparison illustrates a fundamental incompatibility between these two distinct approaches to the foundations of quantum mechanics. 9.1 Introduction As early as 1936, von Neumann and Birkhoff proposed treating projectors on Hilbert space as propositions about quantum systems (Birkhoff and von Neumann 1936), by direct analogy with classical order-theoretic approaches to logic. Boolean lattices arise as the Lindenbaum-Tarski algebras of propositional logics, and as the set of all projectors on a Hilbert space also forms an orthocomplemented lattice, the operations meet, join , and complement were analogously interpreted as the logical connectives conjunction, disjunction , and negation .