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

Xin Wang, Runyao DuanIEEE Trans. Information Theory 2018 · OpenReview

TL;DR

This paper tackles a fundamental question in quantum information theory: whether entanglement can always help achieve the theoretical upper bound on zero-error communication. The authors construct a novel class of quantum channels that demonstrate a strict gap between this upper bound (the quantum Lovász number) and the actual achievable rate with entanglement, proving that entanglement alone isn't always sufficient to reach the theoretical limit.

What Problem Does This Paper Address?

The field of zero-error information theory explores how to transmit information with absolute certainty, a challenging problem even for classical channels. For quantum channels, this becomes even more complex. A key theoretical tool is the "quantum Lovász number," which provides an upper bound on the "entanglement-assisted zero-error classical capacity" – the maximum rate at which information can be sent with zero error, assuming the sender and receiver can share entangled quantum states. A long-standing open question was whether this entanglement-assisted capacity could always reach the quantum Lovász number. If it could, it would imply certain desirable properties like additivity. This paper directly addresses this by investigating if a gap can exist between these two quantities.

Methods

The core of the paper's method involves constructing a specific family of quantum channels, denoted as $N_\alpha$, which are "qutrit-to-qutrit" channels (meaning they operate on three-dimensional quantum states). The authors then employ tools from quantum information theory, specifically:

  • Non-commutative graph theory: This framework associates a mathematical object (a "non-commutative graph") with a quantum channel, which captures its zero-error communication properties.
  • Semidefinite programming (SDP): This is a powerful optimization technique used to calculate quantities like the quantum Lovász number and various zero-error capacities. The paper utilizes both primal and dual SDP formulations.
  • No-signalling (NS)-assisted capacities: The authors also consider capacities that can be enhanced by "no-signalling correlations," a resource that is stronger than entanglement. They show that for their constructed channels, the NS-assisted capacity is equal to the entanglement-assisted capacity.
  • Construction of specific quantum states and operators: To prove their results, the authors carefully construct specific quantum states and operators that serve as feasible solutions for the SDPs, allowing them to derive bounds and exact values for the capacities and the quantum Lovász number.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Entanglement is not always enough: The most significant insight is the demonstration that entanglement alone cannot always bridge the gap between the theoretical upper bound (quantum Lovász number) and the achievable zero-error capacity. This challenges the assumption that entanglement is a universal "fix" for zero-error communication limitations.
  • A specific channel construction reveals the gap: The paper's ingenuity lies in constructing a particular class of qutrit-to-qutrit channels ($N_\alpha$) that exhibit this gap. This is crucial because finding such channels was a major hurdle.
  • Reversibility with no-signalling correlations: Interestingly, for these constructed channels, the zero-error communication and simulation settings become "reversible" when assisted by no-signalling correlations. This means the capacity and simulation cost are equal, a strong form of reversibility.
  • Quantum fractional packing number vs. capacities: The paper highlights a divergence between classical and quantum channels regarding the fractional packing number. For classical channels, this number equals the NS-assisted capacity. For the constructed quantum channels, the quantum fractional packing number is larger than the NS-assisted (and thus entanglement-assisted) zero-error capacity.

Key Results

  • Strict gap demonstrated: The paper proves that for a specific class of qutrit-to-qutrit channels ($N_\alpha$ with $0 < \alpha < \pi/4$), the quantum Lovász number is strictly larger than the entanglement-assisted zero-error capacity. Specifically, $\log(\vartheta(N_\alpha)) > C_{0,NS}(N_\alpha) \ge C_{0E}(N_\alpha)$.
  • Exact values for capacities and Lovász number: For these channels, the authors show that the entanglement-assisted zero-error capacity ($C_{0E}(N_\alpha)$), the no-signalling assisted zero-error capacity ($C_{0,NS}(N_\alpha)$), and the simulation cost ($S_{0,NS}(N_\alpha)$) are all equal to 2 bits.
  • Quantum Lovász number calculation: They derive an exact formula for the quantum Lovász number of these channels: $\vartheta(N_\alpha) = 2 + \cos^2 \alpha + \cos^{-2} \alpha$.
  • Quantum fractional packing number calculation: The quantum fractional packing number for these channels is also found to be $A(N_\alpha) = 2 + \cos^2 \alpha + \cos^{-2} \alpha$, which is equal to the quantum Lovász number.

Limitations and Future Work

  • Specific channel class: The demonstrated gap is for a particular class of qutrit-to-qutrit channels. While this is a significant achievement, it leaves open the question of whether such gaps exist for other types of quantum channels, particularly qubit channels.
  • Computability of $C_{0E}$: The paper notes that the entanglement-assisted zero-error capacity ($C_{0E}$) is not known to be computable in general, which makes finding channels where it differs from the Lovász number a difficult task.
  • Generalization of fractional packing number: The paper raises a new question about exploring other quantum extensions of the fractional packing number, as the current quantum generalization does not directly correspond to the NS-assisted zero-error capacity for all quantum channels.
  • Lovász number and $C_{0E}$ for classical channels: The paper mentions that it's still unknown whether the Lovász number coincides with $C_{0E}$ for every classical channel, suggesting further research in this area.

Summary updated

BibTeX
@article{wang2018separation,
  author = {Xin Wang and Runyao Duan},
  title = {{Separation Between Quantum Lovász Number and Entanglement-Assisted Zero-Error Classical Capacity}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=_hE8Hscdbd},
}
Figure