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

Complete Positivity and Natural Representation of Quantum Computations

Mathys Rennela, Sam Staton

Published Dec 1, 2015• 9 citations
Publisher

Abstract

We propose a new 'quantum domain theory' in which Scott-continuous functions are replaced by Scott-continuous natural transformations. Completely positive maps are widely accepted as a model of first-order quantum computation. We begin by establishing a categorical characterization of completely positive maps as natural families of positive maps. We explore this categorical characterization by building various representations of quantum computation based on different structures: affine maps between cones of positive elements, morphisms of algebras of effects, and affine maps of convex sets of states. By focusing on convex dcpos, we develop a quantum domain theory and show that it supports some important constructions such as tensor products by quantum data, and lifting.

DOI
10.1016/j.entcs.2015.12.022

Related papers

Towards the simulation of higher-order quantum resources: a general type-theoretic approach

Samuel B. Steakley, Elia Zanoni, Carlo Maria Scandolo

Quantum resources exist in a hierarchy of multiple levels. At order zero, quantum states are transformed by linear maps (channels, or gates) in order to perform computations or simulate other states. At order one, gates and channels are transformed by linear maps (superchannels) in order to simulate other gates. To develop a full hierarchy of quantum resources, beyond those first two orders, and to account for the fact that quantum protocols can interconvert resources of different orders, we need a theoretical framework that addresses all orders in a uniform manner. We introduce a framework based on a system of types, which label the different kinds of objects that are present at different orders. We equip the framework with a parallel product operation that modifies and generalizes the tensor product so as to be operationally meaningful for maps of distinct and arbitrary orders. Finally, we introduce a family of convex cones that generalize the notion of complete positivity to all orders, with the aim of characterizing the objects that are physically admissible, facilitating an operational treatment of quantum objects at any order.

arXiv:2510.03622•Oct 4, 2025•0 citations

Categories of relations as models of quantum theory

Chris Heunen, Sean Tull

Categories of relations over a regular category form a family of models of quantum theory. Using regular logic, many properties of relations over sets lift to these models, including the correspondence between Frobenius structures and internal groupoids. Over compact Hausdorff spaces, this lifting gives continuous symmetric encryption. Over a regular Mal'cev category, this correspondence gives a characterization of categories of completely positive maps, enabling the formulation of quantum features. These models are closer to Hilbert spaces than relations over sets in several respects: Heisenberg uncertainty, impossibility of broadcasting, and behavedness of rank one morphisms.

arXiv:1506.05028•Electronic Proceedings in Theoretical Computer Science•Nov 4, 2015•24 citations

A type-based framework for higher-order quantum theory

Samuel B. Steakley

The study of quantum information protocols that process quantum gates has led to an interest in ‘higher-order’ quantum transformations, which are transformations that act on other quantum transformations as inputs and/or return them as outputs. Mathematically, such transformations form an inductive hierarchy of infinitely many levels, or ‘orders’: quantum states are at order zero; channels, which transform quantum states, are at order one; superchannels, which transform channels, are at order two; maps that transform superchannels are at order three, and so on. To proceed toward a general understanding of higher-order quantum theory, we need methods to study the full inductive hierarchy in a uniform manner. In the context of the Hilbert space formalism of quantum theory, this means studying operator spaces (used to represent states), linear operators between operator spaces (used to represent channels), etc.; in other words, the inductive hierarchy of higher-order linear maps. We introduce a methodological framework for higher-order quantum theory, partly modeled on that of [Bisio \& Perinotti, 2019]. The framework is based on a set of types, denoted TypesA. Types may be thought of as labels that we use to identify and differentiate all the different kinds of objects of higher-order quantum theory. The central objects of the framework are typed (higher-order) linear maps, as given by the construction of a set L(x) of linear maps of type x for each x ∈ TypesA. We equip the framework with a parallel product operation for typed linear maps, which modifies and generalizes the tensor product so as to be physically meaningful when applied to maps of distinct and arbitrary orders. With the aim of characterizing the higher-order linear maps that represent valid quantum objects, we give a construction, consisting of a convex cone K(x) for each x ∈ TypesA, which generalizes the notion of complete positivity to all orders. We construct a version of the Choi isomorphism for our framework, and we use it to show that K(x) is self-dual for all x ∈ TypesA.

•Dec 18, 2025•0 citations

Complete Positivity

Chris Heunen, Jamie Vicary

Abstract Completely positive maps give a notion of quantum process that allows the description of probabilistic effects in quantum theory. We show how to describe this categorically in terms of the CP construction and contrast the behaviour of classical and quantum information in this setting. We also study the behaviour of duality and linear structure under the CP construction.

•Nov 19, 2019•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

A Categorical Model for Classical and Quantum Block Designs

Paulina L. A. Goedicke, Jamie Vicary

Classical block designs are important combinatorial structures with a wide range of applications in Computer Science and Statistics. Here we give a new abstract description of block designs based on the arrow category construction. We show that models of this structure in the category of matrices and natural numbers recover the traditional classical combinatorial objects, while models in the category of completely positive maps yield a new definition of quantum designs. We show that this generalizes both a previous notion of quantum designs given by Zauner and the traditional description of block designs. Furthermore, we demonstrate that there exists a functor which relates every categorical block design to a quantum one.

arXiv:2312.09264•Electronic Proceedings in Theoretical Computer Science•Dec 14, 2023•0 citations
We propose a new 'quantum domain theory' in which Scott-continuous functions are replaced by Scott-continuous natural transformations. Completely positive maps are widely accepted as a model of first-order quantum computation. We begin by establishing a categorical characterization of completely positive maps as natural families of positive maps. We explore this categorical characterization by building various representations of quantum computation based on different structures: affine maps between cones of positive elements, morphisms of algebras of effects, and affine maps of convex sets of states. By focusing on convex dcpos, we develop a quantum domain theory and show that it supports some important constructions such as tensor products by quantum data, and lifting.
Quantum resources exist in a hierarchy of multiple levels. At order zero, quantum states are transformed by linear maps (channels, or gates) in order to perform computations or simulate other states. At order one, gates and channels are transformed by linear maps (superchannels) in order to simulate other gates. To develop a full hierarchy of quantum resources, beyond those first two orders, and to account for the fact that quantum protocols can interconvert resources of different orders, we need a theoretical framework that addresses all orders in a uniform manner. We introduce a framework based on a system of types, which label the different kinds of objects that are present at different orders. We equip the framework with a parallel product operation that modifies and generalizes the tensor product so as to be operationally meaningful for maps of distinct and arbitrary orders. Finally, we introduce a family of convex cones that generalize the notion of complete positivity to all orders, with the aim of characterizing the objects that are physically admissible, facilitating an operational treatment of quantum objects at any order.
Categories of relations over a regular category form a family of models of quantum theory. Using regular logic, many properties of relations over sets lift to these models, including the correspondence between Frobenius structures and internal groupoids. Over compact Hausdorff spaces, this lifting gives continuous symmetric encryption. Over a regular Mal'cev category, this correspondence gives a characterization of categories of completely positive maps, enabling the formulation of quantum features. These models are closer to Hilbert spaces than relations over sets in several respects: Heisenberg uncertainty, impossibility of broadcasting, and behavedness of rank one morphisms.
The study of quantum information protocols that process quantum gates has led to an interest in ‘higher-order’ quantum transformations, which are transformations that act on other quantum transformations as inputs and/or return them as outputs. Mathematically, such transformations form an inductive hierarchy of infinitely many levels, or ‘orders’: quantum states are at order zero; channels, which transform quantum states, are at order one; superchannels, which transform channels, are at order two; maps that transform superchannels are at order three, and so on. To proceed toward a general understanding of higher-order quantum theory, we need methods to study the full inductive hierarchy in a uniform manner. In the context of the Hilbert space formalism of quantum theory, this means studying operator spaces (used to represent states), linear operators between operator spaces (used to represent channels), etc.; in other words, the inductive hierarchy of higher-order linear maps. We introduce a methodological framework for higher-order quantum theory, partly modeled on that of [Bisio \& Perinotti, 2019]. The framework is based on a set of types, denoted TypesA. Types may be thought of as labels that we use to identify and differentiate all the different kinds of objects of higher-order quantum theory. The central objects of the framework are typed (higher-order) linear maps, as given by the construction of a set L(x) of linear maps of type x for each x ∈ TypesA. We equip the framework with a parallel product operation for typed linear maps, which modifies and generalizes the tensor product so as to be physically meaningful when applied to maps of distinct and arbitrary orders. With the aim of characterizing the higher-order linear maps that represent valid quantum objects, we give a construction, consisting of a convex cone K(x) for each x ∈ TypesA, which generalizes the notion of complete positivity to all orders. We construct a version of the Choi isomorphism for our framework, and we use it to show that K(x) is self-dual for all x ∈ TypesA.
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.
Classical block designs are important combinatorial structures with a wide range of applications in Computer Science and Statistics. Here we give a new abstract description of block designs based on the arrow category construction. We show that models of this structure in the category of matrices and natural numbers recover the traditional classical combinatorial objects, while models in the category of completely positive maps yield a new definition of quantum designs. We show that this generalizes both a previous notion of quantum designs given by Zauner and the traditional description of block designs. Furthermore, we demonstrate that there exists a functor which relates every categorical block design to a quantum one.