© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1006.1011 · Electronic Notes in Theoretical Computer Science

Relating Toy Models of Quantum Computation: Comprehension, Complementarity and Dagger Mix Autonomous Categories

Duško Pavlović

Published Feb 1, 2011• 9 citations

Abstract

Toy models have been used to separate important features of quantum computation from the rich background of the standard Hilbert space model. Category theory, on the other hand, is a general tool to separate components of mathematical structures, and analyze one layer at a time. It seems natural to combine the two approaches, and several authors have already pursued this idea. We explore categorical comprehension construction as a tool for adding features to toy models. We use it to comprehend quantum propositions and probabilities within the basic model of finite-dimensional Hilbert spaces. We also analyze complementary quantum observables over the category of sets and relations. This leads into the realm of test spaces, a well-studied model. We present one of many possible extensions of this model, enabled by the comprehension construction. Conspicuously, all models obtained in this way carry the same categorical structure, extending the familiar dagger compact framework with the complementation operations. We call the obtained structure dagger mix autonomous, because it extends star autonomous categories, popular in computer science, in a similar way like dagger compact structure extends compact categories. Dagger mix autonomous categories seem to arise quite naturally in quantum computation, as soon as complementarity is viewed as a part of the global structure.

DOI: 10.1016/j.entcs.2011.01.027

Related papers

Dagger linear logic for categorical quantum mechanics

Robin Cockett, Cole Comfort, Priyaa Varshinee Srinivasan

Categorical quantum mechanics exploits the dagger compact closed structure of finite dimensional Hilbert spaces, and uses the graphical calculus of string diagrams to facilitate reasoning about finite dimensional processes. A significant portion of quantum physics, however, involves reasoning about infinite dimensional processes, and it is well-known that the category of all Hilbert spaces is not compact closed. Thus, a limitation of using dagger compact closed categories is that one cannot directly accommodate reasoning about infinite dimensional processes. A natural categorical generalization of compact closed categories, in which infinite dimensional spaces can be modelled, is *-autonomous categories and, more generally, linearly distributive categories. This article starts the development of this direction of generalizing categorical quantum mechanics. An important first step is to establish the behaviour of the dagger in these more general settings. Thus, these notes simultaneously develop the categorical semantics of multiplicative dagger linear logic. The notes end with the definition of a mixed unitary category. It is this structure which is subsequently used to extend the key features of categorical quantum mechanics.

arXiv:1809.00275•Logical Methods in Computer Science•Nov 16, 2021•7 citations

Toy Quantum Categories (Extended Abstract)

Bob Coecke, Bill Edwards

We show that Rob Spekken's toy quantum theory arises as an instance of our categorical approach to quantum axiomatics, as a (proper) subcategory of the dagger compact category FRel of finite sets and relations with the cartesian product as tensor, where observables correspond to dagger Frobenius algebras. This in particular implies that the quantum-like properties of the toy model are in fact very general categorytheoretic properties. We also show the remarkable fact that we can already interpret complementary quantum observables on the two-element set in FRel. Keywords: Quantum category, dagger symmetric monoidal category, finite dimensional Hilbert spaces, FdHilb, FRel

Electronic Notes in Theoretical Computer Science•Feb 1, 2011•25 citations

Dagger linear logic and categorical quantum mechanics

Priyaa Varshinee Srinivasan

This thesis develops the categorical proof theory for the non-compact multiplicative dagger linear logic, and investigates its applications to Categorical Quantum Mechanics (CQM). The existing frameworks of CQM are categorical proof theories of compact dagger linear logic, and are motivated by the interpretation of quantum systems in the category of finite dimensional Hilbert spaces. This thesis describes a new non-compact framework called Mixed Unitary Categories which can accommodate infinite dimensional systems, and develops models for the framework. To this end, it builds on linearly distributive categories, and $*$-autonomous categories which are categorical proof theories of (non-compact) multiplicative linear logic. The proof theory of non-compact dagger-linear logic is obtained from the basic setting of an LDC by adding a dagger functor satisfying appropriate coherences to give a dagger-LDC. From every (isomix) dagger-LDC one can extract a canonical "unitary core" which up to equivalence is the traditional CQM framework of dagger-monoidal categories. This leads to the framework of Mixed Unitary Categories (MUCs): every MUC contains a (compact) unitary core which is extended by a (non-compact) isomix dagger-LDC. Various models of MUCs based on Finiteness Spaces, Chu spaces, Hopf modules, etc., are developed in this thesis. This thesis also generalizes the key algebraic structures of CQM, such as observables, measurement, and complementarity, to MUC framework. Furthermore, using the MUC framework, this thesis establishes a connection between the complementary observables of quantum mechanics and the exponential modalities of linear logic.

arXiv:2303.14231•Mar 24, 2023•0 citations

Toy quantum categories

Bob Coecke, Bill Edwards

We show that Rob Spekken's toy quantum theory arises as an instance of our categorical approach to quantum axiomatics, as a (proper) subcategory of the dagger compact category FRel of finite sets and relations with the cartesian product as tensor, where observables correspond to dagger Frobenius algebras. This in particular implies that the quantum-like properties of the toy model are in fact very general category-theoretic properties. We also show the remarkable fact that we can already interpret complementary quantum observables on the two-element set FRel.

arXiv:0808.1037•Aug 7, 2008•35 citations

Spekkens's toy theory as a category of processes

Bob Coecke, Bill Edwards

We provide two mathematical descriptions of Spekkens's toy qubit theory, an inductively one in terms of a small set of generators, as well as an explicit closed form description. It is a subcategory MSpek of the category of finite sets, relations and the cartesian product. States of maximal knowledge form a subcategory Spek. This establishes the consistency of the toy theory, which has previously only been constructed for at most four systems. Our model also shows that the theory is closed under both parallel and sequential composition of operations (= symmetric monoidal structure), that it obeys map-state duality (= compact closure), and that states and effects are in bijective correspondence (= dagger structure). From the perspective of categorical quantum mechanics, this provides an interesting alternative model which enables us to describe many quantum phenomena in a discrete manner, and to which mathematical concepts such as basis structures, and complementarity thereof, still apply. Hence, the framework of categorical quantum mechanics has delivered on its promise to encompass theories other than quantum theory.

arXiv:1108.1978•Aug 9, 2011•0 citations

Idempotents in Dagger Categories

Peter Selinger

Dagger compact closed categories were studied by Abramsky and Coecke (under the name “strongly compact closed categories”) as an abstract presentation of the category of Hilbert spaces and linear maps, and as a framework in which to carry out the interpretation of quantum protocols. I subsequently showed that dagger compact closed categories can also describe mixed quantum computation, where the morphisms are completely positive maps. I introduced the CPM construction as a way to pass from the pure to the mixed setting. One technical detail of the CPM(C) construction is that it does not preserve biproducts. Therefore, to obtain an interpretation of classical types such as bit=I⊕I, one must work in the free biproduct completion CPM(C)⊕. In this paper, we show that there is another view of classical types, namely as splittings of self-adjoint idempotents on quantum types. We show that all the objects of CPM(C)⊕ arise as such splittings.

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

Toy models have been used to separate important features of quantum computation from the rich background of the standard Hilbert space model. Category theory, on the other hand, is a general tool to separate components of mathematical structures, and analyze one layer at a time. It seems natural to combine the two approaches, and several authors have already pursued this idea. We explore categorical comprehension construction as a tool for adding features to toy models. We use it to comprehend quantum propositions and probabilities within the basic model of finite-dimensional Hilbert spaces. We also analyze complementary quantum observables over the category of sets and relations. This leads into the realm of test spaces, a well-studied model. We present one of many possible extensions of this model, enabled by the comprehension construction. Conspicuously, all models obtained in this way carry the same categorical structure, extending the familiar dagger compact framework with the complementation operations. We call the obtained structure dagger mix autonomous, because it extends star autonomous categories, popular in computer science, in a similar way like dagger compact structure extends compact categories. Dagger mix autonomous categories seem to arise quite naturally in quantum computation, as soon as complementarity is viewed as a part of the global structure.

Categorical quantum mechanics exploits the dagger compact closed structure of finite dimensional Hilbert spaces, and uses the graphical calculus of string diagrams to facilitate reasoning about finite dimensional processes. A significant portion of quantum physics, however, involves reasoning about infinite dimensional processes, and it is well-known that the category of all Hilbert spaces is not compact closed. Thus, a limitation of using dagger compact closed categories is that one cannot directly accommodate reasoning about infinite dimensional processes. A natural categorical generalization of compact closed categories, in which infinite dimensional spaces can be modelled, is *-autonomous categories and, more generally, linearly distributive categories. This article starts the development of this direction of generalizing categorical quantum mechanics. An important first step is to establish the behaviour of the dagger in these more general settings. Thus, these notes simultaneously develop the categorical semantics of multiplicative dagger linear logic. The notes end with the definition of a mixed unitary category. It is this structure which is subsequently used to extend the key features of categorical quantum mechanics.

We show that Rob Spekken's toy quantum theory arises as an instance of our categorical approach to quantum axiomatics, as a (proper) subcategory of the dagger compact category FRel of finite sets and relations with the cartesian product as tensor, where observables correspond to dagger Frobenius algebras. This in particular implies that the quantum-like properties of the toy model are in fact very general categorytheoretic properties. We also show the remarkable fact that we can already interpret complementary quantum observables on the two-element set in FRel. Keywords: Quantum category, dagger symmetric monoidal category, finite dimensional Hilbert spaces, FdHilb, FRel

This thesis develops the categorical proof theory for the non-compact multiplicative dagger linear logic, and investigates its applications to Categorical Quantum Mechanics (CQM). The existing frameworks of CQM are categorical proof theories of compact dagger linear logic, and are motivated by the interpretation of quantum systems in the category of finite dimensional Hilbert spaces. This thesis describes a new non-compact framework called Mixed Unitary Categories which can accommodate infinite dimensional systems, and develops models for the framework. To this end, it builds on linearly distributive categories, and

*

-autonomous categories which are categorical proof theories of (non-compact) multiplicative linear logic. The proof theory of non-compact dagger-linear logic is obtained from the basic setting of an LDC by adding a dagger functor satisfying appropriate coherences to give a dagger-LDC. From every (isomix) dagger-LDC one can extract a canonical "unitary core" which up to equivalence is the traditional CQM framework of dagger-monoidal categories. This leads to the framework of Mixed Unitary Categories (MUCs): every MUC contains a (compact) unitary core which is extended by a (non-compact) isomix dagger-LDC. Various models of MUCs based on Finiteness Spaces, Chu spaces, Hopf modules, etc., are developed in this thesis. This thesis also generalizes the key algebraic structures of CQM, such as observables, measurement, and complementarity, to MUC framework. Furthermore, using the MUC framework, this thesis establishes a connection between the complementary observables of quantum mechanics and the exponential modalities of linear logic.

We show that Rob Spekken's toy quantum theory arises as an instance of our categorical approach to quantum axiomatics, as a (proper) subcategory of the dagger compact category FRel of finite sets and relations with the cartesian product as tensor, where observables correspond to dagger Frobenius algebras. This in particular implies that the quantum-like properties of the toy model are in fact very general category-theoretic properties. We also show the remarkable fact that we can already interpret complementary quantum observables on the two-element set FRel.

We provide two mathematical descriptions of Spekkens's toy qubit theory, an inductively one in terms of a small set of generators, as well as an explicit closed form description. It is a subcategory MSpek of the category of finite sets, relations and the cartesian product. States of maximal knowledge form a subcategory Spek. This establishes the consistency of the toy theory, which has previously only been constructed for at most four systems. Our model also shows that the theory is closed under both parallel and sequential composition of operations (= symmetric monoidal structure), that it obeys map-state duality (= compact closure), and that states and effects are in bijective correspondence (= dagger structure). From the perspective of categorical quantum mechanics, this provides an interesting alternative model which enables us to describe many quantum phenomena in a discrete manner, and to which mathematical concepts such as basis structures, and complementarity thereof, still apply. Hence, the framework of categorical quantum mechanics has delivered on its promise to encompass theories other than quantum theory.

Dagger compact closed categories were studied by Abramsky and Coecke (under the name “strongly compact closed categories”) as an abstract presentation of the category of Hilbert spaces and linear maps, and as a framework in which to carry out the interpretation of quantum protocols. I subsequently showed that dagger compact closed categories can also describe mixed quantum computation, where the morphisms are completely positive maps. I introduced the CPM construction as a way to pass from the pure to the mixed setting. One technical detail of the CPM(C) construction is that it does not preserve biproducts. Therefore, to obtain an interpretation of classical types such as bit=I⊕I, one must work in the free biproduct completion CPM(C)⊕. In this paper, we show that there is another view of classical types, namely as splittings of self-adjoint idempotents on quantum types. We show that all the objects of CPM(C)⊕ arise as such splittings.