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 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 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.
The zero-error capacity of quantum channels was defined as the least upper bound of rates at which classical information can be transmitted through a quantum channel with probability of error equal to zero. This paper investigates some properties of input states and measurements used to attain the quantum zero-error capacity. We start by reformulating the problem of finding the zero-error capacity in the language of graph theory. This alternative definition is used to prove that the zero-error capacity of any quantum channel can be reached by using tensor products of pure states as channel inputs, and projective measurements in the channel output. We conclude by presenting an example that illustrates our results.
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.
Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classicalquantum channels with a confusability graph G, is exactly log ϑ(G), where ϑ(G) is the celebrated Lov´asz theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph G defined by equal-sized cyclotomic cosets, is logbϑ(G)c, which further implies that its asymptotic capacity is log ϑ(G). This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This gives Lov´asz ϑ function another operational meaning in zero-error classical-quantum communication.
We study the activated quantum no-signalling-assisted zero-error classical capacity by first allowing the assistance from some noiseless forward communication channel and later paying back the cost of the helper. This activated communication model considers the additional forward noiseless channel as a catalyst for communication. First, we show that the one-shot activated capacity can be formulated as a semidefinite program and we derive a number of striking properties of this capacity. We further present a sufficient condition under which a noisy channel can be activated. Second, we show that one-bit noiseless classical communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity, or the semidefinite (or fractional) packing number. Third, we prove that the asymptotic activated capacity cannot exceed the original asymptotic capacity of any quantum channel. We also show that the asymptotic no-signalling-assisted zero-error capacity does not equal to the semidefinite packing number for quantum channels, which differs from the case of classical-quantum channels.
We study the one-shot zero-error classical capacity of a quantum channel assisted by quantum no-signalling correlations, and the reverse problem of exact simulation of a prescribed channel by a noiseless classical one. Quantum no-signalling correlations are viewed as two-input and two-output completely positive and trace preserving maps with linear constraints enforcing that the device cannot signal. Both problems lead to simple semidefinite programmes (SDPs) that depend only on the Choi-Kraus (operator) space of the channel. In particular, we show that the zero-error classical simulation cost is precisely the conditional min-entropy of the Choi-Jamiołkowski matrix of the given channel. The zero-error classical capacity is given by a similar-looking but different SDP; the asymptotic zero-error classical capacity is the regularization of this SDP, and in general, we do not know of any simple form. Interestingly, however, for the class of classical-quantum channels, we show that the asymptotic capacity is given by a much simpler SDP, which coincides with a semidefinite generalization of the fractional packing number suggested earlier by Aram Harrow. This finally results in an operational interpretation of the celebrated Lovász ϑ function of a graph as the zero-error classical capacity of the graph assisted by quantum no-signalling correlations, the first information theoretic interpretation of the Lovász number.