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


Quantum Lovász number, as a natural generalization of the celebrated Lovśz number in graph theory, 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 this number always coincides with the entanglement-assisted zero-error capacity. Here we show that there is a strict gap between these two quantities for a class of explicitly constructed qutrit-to-qutrit channels. Our key approach is to show that for this class of channels both the one-shot zero-error communication capacity and the one-shot zero-error simulation cost in the presence of quantum no-signalling correlations (QNSC), a more broader class of resources than entanglement, are exactly four, while the quantum Lov’ź number is strictly larger than that. Interestingly, for this class of channels, the quantum fractional packing number is strictly larger than the QNSC-assisted or quantum feedback-assisted zero-error classical capacity. Note that these quantities are all equal for classical channels.

IEEE Transactions on Information Theory