© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

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

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

Andresso da Silva, Francisco de Assis

Published Jan 1, 2023• 0 citations

Abstract

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).

DOI: 10.14209/sbrt.2023.1570922082

Related papers

Partial Commutativity and Quantum Zero-Error Capacity

Andresso da Silva, Francisco de Assis

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.

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais•Jan 1, 2024•0 citations

Bounding the Graph Capacity With Quantum Mechanics and Finite Automata

Alex Meiburg

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.

arXiv:2403.10985•IEEE Transactions on Information Theory•Feb 24, 2025•1 citation

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

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

Zero-error communication via quantum channels and a quantum Lovász θ-function

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 linear space operators as the quantum generalisation of the adjacency matrix, in terms of which the plain, quantum and entanglement-assisted capacity can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous υ function, as the norm-completion (or stabilisation) of a “naive” generalisation 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 programme, whose dual we write down explicitly, and that it is multiplicative with respect to the natural (strong) graph product. 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 linear spaces of operators associated to channels as “non-commutative graphs”, using the language of operator systems and Hilbert modules.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•13 citations

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

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).

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.

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.

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.

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.

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 linear space operators as the quantum generalisation of the adjacency matrix, in terms of which the plain, quantum and entanglement-assisted capacity can be formulated, and for which we show some new basic properties. Most importantly, we define a quantum version of Lovász' famous υ function, as the norm-completion (or stabilisation) of a “naive” generalisation 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 programme, whose dual we write down explicitly, and that it is multiplicative with respect to the natural (strong) graph product. 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 linear spaces of operators associated to channels as “non-commutative graphs”, using the language of operator systems and Hilbert modules.

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.