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• 37 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

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•2 citations

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•3 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•0 citations

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•0 citations

Sufficient conditions for additivity of the zero-error classical capacity of quantum channels

Jeonghoon Park, Jeong San Kim

The one-shot zero-error classical capacity of a quantum channel is the maximum amount of classical information that can be transmitted with zero probability of error via a single channel use. This capacity is fundamentally characterized by the logarithm of the independence number of the noncommutative graph induced by the quantum channel. Consequently, the additivity of the one-shot zero-error classical capacity is equivalent to the multiplicativity of the independence number of the associated noncommutative graphs. As the independence number is not multiplicative in general, the specific conditions under which multiplicativity is preserved remain an open question in quantum information theory. Here, we establish some sufficient conditions for the multiplicativity of the independence number and provide explicit examples of quantum channels that satisfy these criteria. Furthermore, we investigate the block form of noncommutative graphs and derive the conditions under which the independence number remains multiplicative within this framework. These results offer new insights into the structural properties of noncommutative graphs and the fundamental limits of zero-error quantum communication.

quant-pharXiv:2601.18538•Physical Review A•Jan 27, 2026•0 citations

Quantum Asymptotic Spectra of Graphs and Non-Commutative Graphs, and Quantum Shannon Capacities

Yinan Li, Jeroen Zuiddam

We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.

IEEE Transactions on Information Theory•Oct 22, 2020•6 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.
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).
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 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.
The one-shot zero-error classical capacity of a quantum channel is the maximum amount of classical information that can be transmitted with zero probability of error via a single channel use. This capacity is fundamentally characterized by the logarithm of the independence number of the noncommutative graph induced by the quantum channel. Consequently, the additivity of the one-shot zero-error classical capacity is equivalent to the multiplicativity of the independence number of the associated noncommutative graphs. As the independence number is not multiplicative in general, the specific conditions under which multiplicativity is preserved remain an open question in quantum information theory. Here, we establish some sufficient conditions for the multiplicativity of the independence number and provide explicit examples of quantum channels that satisfy these criteria. Furthermore, we investigate the block form of noncommutative graphs and derive the conditions under which the independence number remains multiplicative within this framework. These results offer new insights into the structural properties of noncommutative graphs and the fundamental limits of zero-error quantum communication.
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.