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

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais

Partial Commutativity and Quantum Zero-Error Capacity

Andresso da Silva, Francisco de Assis

Published Jan 1, 2024• 0 citations
Publisher

Abstract

Recently, it was discovered that there is a connection between the growth factor of the partially commutative monoid, denoted as β(G), and the independence number of the graph.It was shown that β(G) ≥ α(G) and that log β(G) is as an upper bound for the classical zero-error capacity [1].In this paper, we demonstrate that β(G) is not only an upper bound for the Lovász number of G, but is also for the chromatic number of the complement G. Furthermore, we show that log β(G) is an upper bound for the quantum zero-error capacity.

DOI
10.14209/sbrt.2024.1571036516

Related papers

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

Entanglement-assisted zero-error capacity is upper-bounded by the Lovász ϑ function

Salman Beigi

The zero-error capacity of a classical channel is expressed in terms of the independence number of some graph and its tensor powers. This quantity is hard to compute even for small graphs such as the cycle of length seven, so upper bounds such as the Lov\'asz theta function play an important role in zero-error communication. In this paper, we show that the Lov\'asz theta function is an upper bound on the zero-error capacity even in the presence of entanglement between the sender and receiver.

arXiv:1002.2488•Physical Review A•Jul 26, 2010•30 citations

Separation Between Quantum Lovász Number and Entanglement-Assisted Zero-Error Classical Capacity

Xin Wang, Runyao Duan

Quantum Lovász number is a quantum generalization of the Lovász number in graph theory. It is the best known efficiently computable upper bound of the entanglement-assisted zero-error classical capacity of a quantum channel. However, it remains an intriguing open problem whether quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lovász number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lovász number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signaling correlations, which differs from the case of classical channels.

arXiv:1608.04508•IEEE Transactions on Information Theory•Jan 17, 2018•14 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

Invariants of the Quantum Graph of Partial Trace

Wojciech Paupa, Piotr Mikołaj Sołtan

We compute the independence number, zero-error capacity, the values of Lovász function and the quantum Lovász function for the quantum graph associated to the partial trace quantum channel [Formula: see text].

Open Systems & Information Dynamics•Dec 1, 2024•0 citations

Invariants of the quantum graph of the partial trace

Wojciech Paupa, Piotr Mikołaj Sołtan

We compute the independence number, zero-error capacity, and the values of the Lovász function and the quantum Lovász function for the quantum graph associated to the partial trace quantum channel $\operatorname{Tr}_n\otimes\mathrm{id}_k\colon\operatorname{B}(\mathbb{C}^n\otimes\mathbb{C}^k)\to\operatorname{B}(\mathbb{C}^k)$.

arXiv:2408.16858•Aug 29, 2024•0 citations
Recently, it was discovered that there is a connection between the growth factor of the partially commutative monoid, denoted as β(G), and the independence number of the graph.It was shown that β(G) ≥ α(G) and that log β(G) is as an upper bound for the classical zero-error capacity [1].In this paper, we demonstrate that β(G) is not only an upper bound for the Lovász number of G, but is also for the chromatic number of the complement G. Furthermore, we show that log β(G) is an upper bound for the quantum zero-error capacity.
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 zero-error capacity of a classical channel is expressed in terms of the independence number of some graph and its tensor powers. This quantity is hard to compute even for small graphs such as the cycle of length seven, so upper bounds such as the Lov\'asz theta function play an important role in zero-error communication. In this paper, we show that the Lov\'asz theta function is an upper bound on the zero-error capacity even in the presence of entanglement between the sender and receiver.
Quantum Lovász number is a quantum generalization of the Lovász number in graph theory. It is the best known efficiently computable upper bound of the entanglement-assisted zero-error classical capacity of a quantum channel. However, it remains an intriguing open problem whether quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lovász number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lovász number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signaling correlations, which differs from the case of classical channels.
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.
We compute the independence number, zero-error capacity, and the values of the Lovász function and the quantum Lovász function for the quantum graph associated to the partial trace quantum channel Tr⁡n⊗idk ⁣:B⁡(Cn⊗Ck)→B⁡(Ck)\operatorname{Tr}_n\otimes\mathrm{id}_k\colon\operatorname{B}(\mathbb{C}^n\otimes\mathbb{C}^k)\to\operatorname{B}(\mathbb{C}^k)Trn​⊗idk​:B(Cn⊗Ck)→B(Ck).