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.
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 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.
Recently the one-shot quantum no-signalling assisted zero-error classical capacity of a quantum channel has been formulated as a semidefinite programming (SDP) depending only on the Choi-Kraus operator space of the channel. In this paper, we study the \textit{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. We show that the one-shot activated capacity can also be formulated as a SDP and derive a number of striking properties of this number. In particular, this number is additive under direct sum, and is always greater than or equal to the super-dense coding bound. An a remarkable consequence, we find that one bit noiseless classical communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity, or the semidefinite fractional packing number. We also discuss the condition under which a noisy channel can activate an activatable channel. Interestingly, a channel is able to activate itself if its one-shot capacity is greater than or equal to the Golden Ratio - (1+5)/2. We also show that the asymptotic activated capacity is still equal to the usual no-signalling assisted capacity. Finally, we show that general the asymptotic no-signalling assisted zero-error capacity does not equal to the semidefinite (fractional) packing number by an explicit construction.
We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space K, we introduce a semidefinite programming parameter Γ(K) that is exactly multiplicative under tensor products and upper-bounds ΘNS(K), where log2ΘNS(K)=C0,NS(K) and C0,NS(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on ΘNS given by semidefinite programs, Γ is the tightest. We also prove that the previously introduced simulation lower bound Σ−(K) is exactly multiplicative and satisfies ΘNS(K)≤Γ(K)≤Σ−(K)≤Γ(K)2. Using this multiplicativity, we show that neither S0,NS(K)=log2Σ−(K) nor its regularized extension S0,NS(K)=limn→∞n−1log2Σ−(K⊗n) holds in general. This answers an open question about the asymptotic simulation cost S0,NS(K). For classical-quantum channels, we obtain sharp bounds. If r is the effective output dimension, then ΘNS≤Γ≤(1+r1/2)ΘNS/2 and Γ≤Σ−≤(1+r1/2)Γ/2. If k is the minimum rank of the output support projections, then Σ−/ΘNS≤[(1+r1/2)/(1+k1/2)]2, and this bound is sharp for every 1≤k≤r. Thus, we obtain the sharp bound S0,NS−C0,NS≤2log2[(1+r1/2)/(1+k1/2)].
Using one channel to simulate another exactly with the aid of quantum no-signalling correlations has been studied recently. The one-shot no-signalling assisted classical zero-error simulation cost of non-commutative bipartite graphs has been formulated as semidefinite programms [Duan and Winter, IEEE Trans. Inf. Theory 62, 891 (2016)]. Before our work, it was unknown whether the one-shot (or asymptotic) no-signalling assisted zero-error classical simulation cost for general non-commutative graphs is multiplicative (resp. additive) or not. In this paper we address these issues and give a general sufficient condition for the multiplicativity of the one-shot simulation cost and the additivity of the asymptotic simulation cost of non-commutative bipartite graphs, which include all known cases such as extremal graphs and classical-quantum graphs. Applying this condition, we exhibit a large class of so-called cheapest-full-rank graphs whose asymptotic zero-error simulation cost is given by the one-shot simulation cost. Finally, we disprove the multiplicativity of one-shot simulation cost by explicitly constructing a special class of qubit-qutrit non-commutative bipartite graphs.
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.
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.