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:2403.10985 · IEEE Transactions on Information Theory

Bounding the Graph Capacity With Quantum Mechanics and Finite Automata

Alex Meiburg

Published Feb 24, 2025• 1 citation
arXivHTMLPDF

Abstract

The zero-error capacity of a channel (or “Shannon capacity of a graph”) quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity of achannel, the zero-error capacity has not even been shown to be computable: we have no convergent upper bounds. In this work, we present a new quantity, the zero-errorunitarycapacity, and show that it can be succinctly represented as the tensor product value of a quantum game. By studying the structure of finite automata, we show that the unitary capacity is within a controllable factor of the zero-error capacity. This allows new upper bounds through the sum-of-squares hierarchy, which converges to the commuting operator value of the game. Under the conjecture that the commuting operator and tensor product value of this game are equal, this would yield an algorithm for computing the zero-error capacity.

DOI
10.1109/tit.2025.3544970

Related papers

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

New Bound for Classical Zero-Error Capacity using Partially Commutative Monoids as Counting Tools

Andresso da Silva, Francisco de Assis

In this paper we propose a new bound for the classical zero-error capacity of a communication channel using partially commutative monoids as enumeration tools.Specifically, we analyze the relationship between classical zero-error capacity and the growth factor of the monoid, β(G), of a graph G.Although the value of β(G) allows us to calculate an upper bound for the classical zero-error capacity, determining it requires counting the number of cliques in a graph, which is an NP-Complete problem.Our main result is that the classical zeroerror capacity is always lower than the integer part of β(G).

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais•Jan 1, 2023•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

Complexity and Capacity Bounds for Quantum Channels

Rupert H. Levene, Vern I. Paulsen, Ivan G. Todorov

We generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.

arXiv:1710.06456•IEEE Transactions on Information Theory•May 7, 2018•11 citations
The zero-error capacity of a channel (or “Shannon capacity of a graph”) quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity of achannel, the zero-error capacity has not even been shown to be computable: we have no convergent upper bounds. In this work, we present a new quantity, the zero-errorunitarycapacity, and show that it can be succinctly represented as the tensor product value of a quantum game. By studying the structure of finite automata, we show that the unitary capacity is within a controllable factor of the zero-error capacity. This allows new upper bounds through the sum-of-squares hierarchy, which converges to the commuting operator value of the game. Under the conjecture that the commuting operator and tensor product value of this game are equal, this would yield an algorithm for computing the zero-error capacity.
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.
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).
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.
In this paper we propose a new bound for the classical zero-error capacity of a communication channel using partially commutative monoids as enumeration tools.Specifically, we analyze the relationship between classical zero-error capacity and the growth factor of the monoid, β(G), of a graph G.Although the value of β(G) allows us to calculate an upper bound for the classical zero-error capacity, determining it requires counting the number of cliques in a graph, which is an NP-Complete problem.Our main result is that the classical zeroerror capacity is always lower than the integer part of β(G).
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 generalize some well-known graph parameters to operator systems by considering their underlying quantum channels. In particular, we introduce the quantum complexity as the dimension of the smallest co-domain Hilbert space a quantum channel requires to realize a given operator system as its non-commutative confusability graph. We describe quantum complexity as a generalized minimum semidefinite rank and, in the case of a graph operator system, as a quantum intersection number. The quantum complexity and a closely related quantum version of orthogonal rank turn out to be upper bounds for the Shannon zero-error capacity of a quantum channel, and we construct examples for which these bounds beat the best previously known general upper bound for the capacity of quantum channels, given by the quantum Lovász theta number.