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

Completely positive classical structures and sequentializable quantum protocols

Chris Heunen, Sergio Boixo

Published Oct 1, 2012• 18 citations
arXivHTMLPDF

Abstract

We study classical structures in various categories of completely positive morphisms: on sets and relations, on cobordisms, on a free dagger compact category, and on Hilbert spaces. As an application, we prove that quantum maps with commuting Kraus operators can be sequentialized. Hence such protocols are precisely as robust under general dephasing noise when entangled as when sequential.

DOI
10.4204/eptcs.95.9

Related papers

Entangled and Sequential Quantum Protocols with Dephasing

Sergio Boixo, Chris Heunen

Sequences of commuting quantum operators can be parallelized using entanglement. This transformation is behind some optimal quantum metrology protocols and recent results on quantum circuit complexity. We show that dephasing quantum maps in arbitrary dimension can also be parallelized. This implies that for general dephasing noise the protocol with entanglement is not more fragile than the corresponding sequential protocol and, conversely, the sequential protocol is not less effective than the entangled one. We derive this result using tensor networks. Furthermore, we only use transformations strictly valid within string diagrams in dagger compact closed categories. Therefore, they apply verbatim to other theories, such as geometric quantization and topological quantum field theory. This clarifies and characterizes to some extent the role of entanglement in general quantum theories.

arXiv:1108.3569•Physical Review Letters•Mar 21, 2012•25 citations

Categories of Quantum and Classical Channels (extended abstract)

Bob Coecke, Chris Heunen, Aleks Kissinger

We introduce the CP*-construction on a dagger compact closed category as a generalisation of Selinger's CPM-construction. While the latter takes a dagger compact closed category and forms its category of "abstract matrix algebras" and completely positive maps, the CP*-construction forms its category of "abstract C*-algebras" and completely positive maps. This analogy is justified by the case of finite-dimensional Hilbert spaces, where the CP*-construction yields the category of finite-dimensional C*-algebras and completely positive maps. The CP*-construction fully embeds Selinger's CPM-construction in such a way that the objects in the image of the embedding can be thought of as "purely quantum" state spaces. It also embeds the category of classical stochastic maps, whose image consists of "purely classical" state spaces. By allowing classical and quantum data to coexist, this provides elegant abstract notions of preparation, measurement, and more general quantum channels.

arXiv:1408.0049•Electronic Proceedings in Theoretical Computer Science•Jul 29, 2014•6 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

Dagger Compact Closed Categories and Completely Positive Maps

Peter Selinger

Dagger compact closed categories were recently introduced by Abramsky and Coecke, under the name “strongly compact closed categories”, as an axiomatic framework for quantum mechanics. We present a graphical language for dagger compact closed categories, and sketch a proof of its completeness for equational reasoning. We give a general construction, the CPM construction, which associates to each dagger compact closed category its “category of completely positive maps”, and we show that the resulting category is again dagger compact closed. We apply these ideas to Abramsky and Coecke's interpretation of quantum protocols, and to D'Hondt and Panangaden's predicate transformer semantics.

Electronic Notes in Theoretical Computer Science•Mar 1, 2007•391 citations

Pictures of complete positivity in arbitrary dimension

Bob Coecke, Chris Heunen

Two fundamental contributions to categorical quantum mechanics are presented. First, we generalize the CP-construction, that turns any dagger compact category into one with completely positive maps, to arbitrary dimension. Second, we axiomatize when a given category is the result of this construction.

Electronic Proceedings in Theoretical Computer Science•Oct 1, 2012•32 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
We study classical structures in various categories of completely positive morphisms: on sets and relations, on cobordisms, on a free dagger compact category, and on Hilbert spaces. As an application, we prove that quantum maps with commuting Kraus operators can be sequentialized. Hence such protocols are precisely as robust under general dephasing noise when entangled as when sequential.
Sequences of commuting quantum operators can be parallelized using entanglement. This transformation is behind some optimal quantum metrology protocols and recent results on quantum circuit complexity. We show that dephasing quantum maps in arbitrary dimension can also be parallelized. This implies that for general dephasing noise the protocol with entanglement is not more fragile than the corresponding sequential protocol and, conversely, the sequential protocol is not less effective than the entangled one. We derive this result using tensor networks. Furthermore, we only use transformations strictly valid within string diagrams in dagger compact closed categories. Therefore, they apply verbatim to other theories, such as geometric quantization and topological quantum field theory. This clarifies and characterizes to some extent the role of entanglement in general quantum theories.
We introduce the CP*-construction on a dagger compact closed category as a generalisation of Selinger's CPM-construction. While the latter takes a dagger compact closed category and forms its category of "abstract matrix algebras" and completely positive maps, the CP*-construction forms its category of "abstract C*-algebras" and completely positive maps. This analogy is justified by the case of finite-dimensional Hilbert spaces, where the CP*-construction yields the category of finite-dimensional C*-algebras and completely positive maps. The CP*-construction fully embeds Selinger's CPM-construction in such a way that the objects in the image of the embedding can be thought of as "purely quantum" state spaces. It also embeds the category of classical stochastic maps, whose image consists of "purely classical" state spaces. By allowing classical and quantum data to coexist, this provides elegant abstract notions of preparation, measurement, and more general quantum channels.
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.
Dagger compact closed categories were recently introduced by Abramsky and Coecke, under the name “strongly compact closed categories”, as an axiomatic framework for quantum mechanics. We present a graphical language for dagger compact closed categories, and sketch a proof of its completeness for equational reasoning. We give a general construction, the CPM construction, which associates to each dagger compact closed category its “category of completely positive maps”, and we show that the resulting category is again dagger compact closed. We apply these ideas to Abramsky and Coecke's interpretation of quantum protocols, and to D'Hondt and Panangaden's predicate transformer semantics.
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.