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.
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 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)].
Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot
ε-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.
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.
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.
Abstract The “noncommutative graphs” which arise in quantum error correction are a special case of the quantum relations introduced in Weaver (Quantum relations. Mem Am Math Soc 215(v–vi):81–140, 2012). We use this perspective to interpret the Knill–Laflamme error-correction conditions (Knill and Laflamme in Theory of quantum error-correcting codes. Phys Rev A 55:900-911, 1997) in terms of graph-theoretic independence, to give intrinsic characterizations of Stahlke’s noncommutative graph homomorphisms (Stahlke in Quantum zero-error source-channel coding and non-commutative graph theory. IEEE Trans Inf Theory 62:554–577, 2016) and Duan, Severini, and Winter’s noncommutative bipartite graphs (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013), and to realize the noncommutative confusability graph associated to a quantum channel (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013) as the pullback of a diagonal relation. Our framework includes as special cases not only purely classical and purely quantum information theory, but also the “mixed” setting which arises in quantum systems obeying superselection rules. Thus we are able to define noncommutative confusability graphs, give error correction conditions, and so on, for such systems. This could have practical value, as superselection constraints on information encoding can be physically realistic.