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:1506.03892 · Journal of Geometric Analysis

Quantum Graphs as Quantum Relations

Nik Weaver

Published Jan 13, 2021• 50 citations
arXivHTMLPDF

Abstract

Abstract The “noncommutative graphs” which arise in quantum error correction are a special case of the quantum relations introduced in Weaver (Quantum relations. Mem Am Math Soc 215(v–vi):81–140, 2012). We use this perspective to interpret the Knill–Laflamme error-correction conditions (Knill and Laflamme in Theory of quantum error-correcting codes. Phys Rev A 55:900-911, 1997) in terms of graph-theoretic independence, to give intrinsic characterizations of Stahlke’s noncommutative graph homomorphisms (Stahlke in Quantum zero-error source-channel coding and non-commutative graph theory. IEEE Trans Inf Theory 62:554–577, 2016) and Duan, Severini, and Winter’s noncommutative bipartite graphs (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013), and to realize the noncommutative confusability graph associated to a quantum channel (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013) as the pullback of a diagonal relation. Our framework includes as special cases not only purely classical and purely quantum information theory, but also the “mixed” setting which arises in quantum systems obeying superselection rules. Thus we are able to define noncommutative confusability graphs, give error correction conditions, and so on, for such systems. This could have practical value, as superselection constraints on information encoding can be physically realistic.

DOI
10.1007/s12220-020-00578-w

Related papers

Covariant Quantum Combinatorics with Applications to Zero-Error Communication

Dominic Verdon

Abstract We develop the theory of quantum (a.k.a. noncommutative) relations and quantum (a.k.a. noncommutative) graphs in the finite-dimensional covariant setting, where all systems (finite-dimensional $$C^*$$ C ∗ -algebras) carry an action of a compact quantum group G , and all channels (completely positive maps preserving a certain G -invariant functional) are covariant with respect to the G -actions. We motivate our definitions by applications to zero-error quantum communication theory with a symmetry constraint. Some key results are the following: (1) We give a necessary and sufficient condition for a covariant quantum relation to be the underlying relation of a covariant channel. (2) We show that every quantum confusability graph with a G -action (which we call a quantum G -graph) arises as the confusability graph of a covariant channel. (3) We show that a covariant channel is reversible precisely when its confusability G -graph is discrete. (4) When G is quasitriangular (this includes all compact groups), we show that covariant zero-error source-channel coding schemes are classified by covariant homomorphisms between confusability G -graphs.

arXiv:2302.07776•Communications in Mathematical Physics•Feb 1, 2024•4 citations

The Haemers Bound of Noncommutative Graphs

Sander Gribling, Yinan Li

We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, IEEE Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).

arXiv:2002.02743•IEEE Journal on Selected Areas in Information Theory•Jul 31, 2020•4 citations

Quantum Zero-Error Source-Channel Coding and Non-Commutative Graph Theory

Dan Stahlke

Alice and Bob receive a bipartite state (possibly entangled) from some finite collection or from some subspace. Alice sends a message to Bob through a noisy quantum channel such that Bob may determine the initial state, with zero chance of error. This framework encompasses, for example, teleportation, dense coding, entanglement assisted quantum channel capacity, and one-way communication complexity of function evaluation. With classical sources and channels, this problem can be analyzed using graph homomorphisms. We show this quantum version can be analyzed using homomorphisms on non-commutative graphs (an operator space generalization of graphs). Previously the Lovász ϑ number has been generalized to non-commutative graphs; we show this to be a homomorphism monotone, thus providing bounds on quantum source-channel coding. We generalize the Schrijver and Szegedy numbers, and show these to be monotones as well. As an application, we construct a quantum channel whose entanglement assisted zero-error one-shot capacity can only be unlocked using a non-maximally entangled state. These homomorphisms allow definition of a chromatic number for non-commutative graphs. Many open questions are presented regarding the possibility of a more fully developed theory.

arXiv:1405.5254•IEEE Transactions on Information Theory•Nov 2, 2015•54 citations

Morita equivalence for quantum graphs

Alexandros Chatzinikolaou, Gage Hoefer, Nikolaos Koutsonikos-Kouloumpis +1 more

We introduce an operator-algebraic framework for Morita equivalence of quantum graphs based on $Δ$-equivalence of operator systems introduced by Eleftherakis, Kakariadis and Todorov. Adopting the perspective of Weaver, we view quantum graphs as quantum relations, that is, operator systems endowed with a bimodule structure over the commutant of a von Neumann algebra. Within this framework, we show that two irreducibly acting quantum graphs are Morita equivalent if and only if they are both full pullbacks of a common quantum graph. This extends a result of Eleftherakis, Kakariadis and Todorov for graph operator systems to the quantum graph setting. In passing we construct a true-twin reduction analogue for an irreducibly acting quantum graph. We further characterise the case where we have simultaneous TRO-equivalence of the quantum graphs and their associated algebras, thus giving a second, stronger notion of Morita equivalence. In the special case of noncommutative graphs, corresponding to the zero-error quantum communication setting, the two notions coincide and we obtain a characterisation in terms of strong co-homomorphisms of noncommutative graphs. Finally, we show that connectivity, the independence number, Shannon capacity, quantum complexity and subcomplexity, Haemers bound, and the Lovász number are invariant under Morita equivalence.

arXiv:2604.18065•Apr 20, 2026•1 citation

Quantum Graph Theory by Example

Gian Luca Spitzer, Ion Nechita

Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices $(A, B, C)$. The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: $A$ and $C$ are described by a classical weighted graph called the strange graph, while $B$ provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.

math.OACross-listedarXiv:2603.23651•Quantum•Mar 26, 2026•1 citation

Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number

Runyao Duan, Simone Severini B, Andreas Winter

We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain subspace of operators (so-called operator systems) as the quantum generalization of the adjacency matrix, in terms of which the zero-error capacity of a quantum channel, as well as the quantum and entanglement-assisted zero-error capacities can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous ϑ function on general operator systems, as the norm-completion (or stabilization) of a “naive” generalization of ϑ. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite program, whose dual we write down explicitly, and that it is multiplicative with respect to the tensor product of operator systems (corresponding to the tensor product of channels). We explore various other properties of the new quantity, which reduces to Lovász' original ϑ in the classical case, give several applications, and propose to study the operator systems associated with channels as “noncommutative graphs,” using the language of Hilbert modules.

arXiv:1002.2514•IEEE Transactions on Information Theory•Oct 2, 2012•197 citations
Abstract The “noncommutative graphs” which arise in quantum error correction are a special case of the quantum relations introduced in Weaver (Quantum relations. Mem Am Math Soc 215(v–vi):81–140, 2012). We use this perspective to interpret the Knill–Laflamme error-correction conditions (Knill and Laflamme in Theory of quantum error-correcting codes. Phys Rev A 55:900-911, 1997) in terms of graph-theoretic independence, to give intrinsic characterizations of Stahlke’s noncommutative graph homomorphisms (Stahlke in Quantum zero-error source-channel coding and non-commutative graph theory. IEEE Trans Inf Theory 62:554–577, 2016) and Duan, Severini, and Winter’s noncommutative bipartite graphs (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013), and to realize the noncommutative confusability graph associated to a quantum channel (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013) as the pullback of a diagonal relation. Our framework includes as special cases not only purely classical and purely quantum information theory, but also the “mixed” setting which arises in quantum systems obeying superselection rules. Thus we are able to define noncommutative confusability graphs, give error correction conditions, and so on, for such systems. This could have practical value, as superselection constraints on information encoding can be physically realistic.
Abstract We develop the theory of quantum (a.k.a. noncommutative) relations and quantum (a.k.a. noncommutative) graphs in the finite-dimensional covariant setting, where all systems (finite-dimensional C∗C^*C∗ C ∗ -algebras) carry an action of a compact quantum group G , and all channels (completely positive maps preserving a certain G -invariant functional) are covariant with respect to the G -actions. We motivate our definitions by applications to zero-error quantum communication theory with a symmetry constraint. Some key results are the following: (1) We give a necessary and sufficient condition for a covariant quantum relation to be the underlying relation of a covariant channel. (2) We show that every quantum confusability graph with a G -action (which we call a quantum G -graph) arises as the confusability graph of a covariant channel. (3) We show that a covariant channel is reversible precisely when its confusability G -graph is discrete. (4) When G is quasitriangular (this includes all compact groups), we show that covariant zero-error source-channel coding schemes are classified by covariant homomorphisms between confusability G -graphs.
We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, IEEE Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).
Alice and Bob receive a bipartite state (possibly entangled) from some finite collection or from some subspace. Alice sends a message to Bob through a noisy quantum channel such that Bob may determine the initial state, with zero chance of error. This framework encompasses, for example, teleportation, dense coding, entanglement assisted quantum channel capacity, and one-way communication complexity of function evaluation. With classical sources and channels, this problem can be analyzed using graph homomorphisms. We show this quantum version can be analyzed using homomorphisms on non-commutative graphs (an operator space generalization of graphs). Previously the Lovász ϑ number has been generalized to non-commutative graphs; we show this to be a homomorphism monotone, thus providing bounds on quantum source-channel coding. We generalize the Schrijver and Szegedy numbers, and show these to be monotones as well. As an application, we construct a quantum channel whose entanglement assisted zero-error one-shot capacity can only be unlocked using a non-maximally entangled state. These homomorphisms allow definition of a chromatic number for non-commutative graphs. Many open questions are presented regarding the possibility of a more fully developed theory.
We introduce an operator-algebraic framework for Morita equivalence of quantum graphs based on ΔΔΔ-equivalence of operator systems introduced by Eleftherakis, Kakariadis and Todorov. Adopting the perspective of Weaver, we view quantum graphs as quantum relations, that is, operator systems endowed with a bimodule structure over the commutant of a von Neumann algebra. Within this framework, we show that two irreducibly acting quantum graphs are Morita equivalent if and only if they are both full pullbacks of a common quantum graph. This extends a result of Eleftherakis, Kakariadis and Todorov for graph operator systems to the quantum graph setting. In passing we construct a true-twin reduction analogue for an irreducibly acting quantum graph. We further characterise the case where we have simultaneous TRO-equivalence of the quantum graphs and their associated algebras, thus giving a second, stronger notion of Morita equivalence. In the special case of noncommutative graphs, corresponding to the zero-error quantum communication setting, the two notions coincide and we obtain a characterisation in terms of strong co-homomorphisms of noncommutative graphs. Finally, we show that connectivity, the independence number, Shannon capacity, quantum complexity and subcomplexity, Haemers bound, and the Lovász number are invariant under Morita equivalence.
Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices (A,B,C)(A, B, C)(A,B,C). The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: AAA and CCC are described by a classical weighted graph called the strange graph, while BBB provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.
We study the quantum channel version of Shannon's zero-error capacity problem. Motivated by recent progress on this question, we propose to consider a certain subspace of operators (so-called operator systems) as the quantum generalization of the adjacency matrix, in terms of which the zero-error capacity of a quantum channel, as well as the quantum and entanglement-assisted zero-error capacities can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous ϑ function on general operator systems, as the norm-completion (or stabilization) of a “naive” generalization of ϑ. We go on to show that this function upper bounds the number of entanglement-assisted zero-error messages, that it is given by a semidefinite program, whose dual we write down explicitly, and that it is multiplicative with respect to the tensor product of operator systems (corresponding to the tensor product of channels). We explore various other properties of the new quantity, which reduces to Lovász' original ϑ in the classical case, give several applications, and propose to study the operator systems associated with channels as “noncommutative graphs,” using the language of Hilbert modules.