Does entanglement-assisted capacity equal the Lovász bound?
Let $G = (V, E)$ be a finite nonempty simple graph, the confusability graph of a classical channel. Its entanglement-assisted independence number $\alpha_*(G)$ is the largest integer $m$ for which there are a finite dimension $d$, a density matrix $\rho \in \mathbb{C}^{d \times d}$ and positive semidefinite matrices $\rho_{i,x}$ ($1 \le i \le m$, $x \in V$) with $$\sum_{x \in V} \rho_{i,x} = \rho \quad (1 \le i \le m), \qquad \rho_{i,x}\, \rho_{j,y} = 0 \quad \text{if } i \ne j \text{ and } (x = y \text{ or } \{x, y\} \in E).$$ The entanglement-assisted Shannon capacity is $$\Theta_*(G) = \sup_{n \ge 1} \alpha_*\bigl(G^{\boxtimes n}\bigr)^{1/n},$$ where $G^{\boxtimes n}$ is the $n$th strong power of $G$; the dimension and the state may depend on $n$. Let $\vartheta(G)$ be the Lovász number, normalised so that $\alpha(G) \le \vartheta(G)$ for the independence number $\alpha$: orthonormal representations assign orthogonal unit vectors to distinct non-adjacent vertices. Beigi, and Duan, Severini and Winter, proved $\Theta_*(G) \le \vartheta(G)$ for every graph. Cubitt, Mančinska, Roberson, Severini, Stahlke and Winter proved that $\alpha_*(G)$ is at most Schrijver's variant of the Lovász number, so that for some graphs $\alpha_*(G)$ is strictly smaller than $\lfloor \vartheta(G) \rfloor$. Li and Zuiddam proved that the equality asked below and the equality of $\Theta_*$ with the quantum Shannon capacity of Mančinska and Roberson cannot both hold for all graphs. For quantum channels, Wang and Duan found channels whose entanglement-assisted zero-error capacity is strictly smaller than the logarithm of the quantum Lovász number.
Problem. Is $\Theta_*(G) = \vartheta(G)$ for every finite nonempty simple graph $G$?
Source: Duan, Severini and Winter (2013), Section VI, who ask whether the entanglement-assisted zero-error capacity equals the logarithm of their quantum Lovász number for every non-commutative graph, which for a classical channel with confusability graph G is log ϑ(G); stated for graphs as Li and Zuiddam (2021), Conjecture 19.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT, MP
- Keywords
- AIM Open Applied Problems, entanglement-assisted communication, Lovász number, zero-error capacities
References
@article{duan2013,
author = {Duan, Runyao and Severini, Simone and Winter, Andreas},
title = {Zero-error communication via quantum channels, noncommutative graphs, and a quantum {L}ov{\'a}sz number},
journal = {IEEE Trans. Inform. Theory},
volume = {59},
number = {2},
year = {2013},
pages = {1164--1174},
doi = {10.1109/TIT.2012.2221677},
eprint = {1002.2514},
archivePrefix = {arXiv},
}
@article{li2021,
author = {Li, Yinan and Zuiddam, Jeroen},
title = {Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum {S}hannon capacities},
journal = {IEEE Trans. Inform. Theory},
volume = {67},
number = {1},
year = {2021},
pages = {416--432},
doi = {10.1109/TIT.2020.3032686},
eprint = {1810.00744},
archivePrefix = {arXiv},
}
@article{beigi2010,
author = {Beigi, Salman},
title = {Entanglement-assisted zero-error capacity is upper-bounded by the {L}ov{\'a}sz $\vartheta$ function},
journal = {Phys. Rev. A},
volume = {82},
number = {1},
year = {2010},
pages = {010303},
doi = {10.1103/PhysRevA.82.010303},
eprint = {1002.2488},
archivePrefix = {arXiv},
}
@article{cubitt2014,
author = {Cubitt, Toby and Man{\v{c}}inska, Laura and Roberson, David E. and Severini, Simone and Stahlke, Dan and Winter, Andreas},
title = {Bounds on entanglement-assisted source-channel coding via the {L}ov{\'a}sz $\vartheta$ number and its variants},
journal = {IEEE Trans. Inform. Theory},
volume = {60},
number = {11},
year = {2014},
pages = {7330--7344},
doi = {10.1109/TIT.2014.2349502},
eprint = {1310.7120},
archivePrefix = {arXiv},
}
@article{wang2018,
author = {Wang, Xin and Duan, Runyao},
title = {Separation between quantum {L}ov{\'a}sz number and entanglement-assisted zero-error classical capacity},
journal = {IEEE Trans. Inform. Theory},
volume = {64},
number = {3},
year = {2018},
pages = {1454--1460},
doi = {10.1109/TIT.2018.2794391},
eprint = {1608.04508},
archivePrefix = {arXiv},
}
@misc{aim-entanglement-assisted-lovasz,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Does entanglement-assisted capacity equal the Lovász bound?}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/302-entanglement-assisted-lovasz.md},
note = {Entry 302 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00429, "Does entanglement-assisted capacity equal the Lovász bound?", clopen.solutions.