Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.20775

The Lovász number is not alone: a continuum of Rényi points in the entanglement-assisted spectrum of graphs

Nidhal Mghirbi, Seth Douglas

quant-phmath.COSubmitted Oct 14, 2026• Announced Oct 16, 2026• 1 citation
arXivHTMLPDF

Abstract

Li and Zuiddam's entanglement-assisted asymptotic spectrum of graphs consists of the normalized graph parameters that are additive under disjoint unions, multiplicative under strong products and monotone under entanglement-assisted cohomomorphisms; the entanglement-assisted Shannon capacity is their pointwise minimum. To our knowledge, the Lovász number $\vartheta$ was its only known element. We find a continuum of others. Three quantities of Duan and Winter, $\log_2\vartheta$, the minimal Holevo capacity $C_{\min}$ and the logarithm of the no-signalling simulation cost $Σ$, are the smallest information radii of classical-quantum channels compatible with a graph, measured with Petz-Rényi divergences of orders $0$, $1$ and $2$. At order zero this is due to Schrijver (as credited by Dalai) and to Duan and Winter; at order one it is the min-max formula for the Holevo capacity. Interpolating in the order gives a family $\vartheta_α$, $0\leα\le2$, and we prove that every member lies in the spectrum. The main step, multiplicativity under strong products for channels that need not factor, follows from an exact nesting identity for compressions. Sandwiched Rényi radii of order $β\in[1/2,\infty]$ give the same family, at $α=2-1/β$. On the five-cycle the family takes every value in $[\sqrt5,5/2]$. A Hilbert-Schmidt inequality for the pentagon gives $C_{\min}(C_5)=\log_2(5/2)$, proving a conjecture of Duan and Winter. We also settle the two open links of their inequality chain: the graph-level no-signalling simulation rate always equals its single-letter value $\log_2Σ(G)$, and a 32-vertex graph from the Mermin-Peres magic square has $C_{\min}<\log_2Σ$, certified in exact rational arithmetic. Finally, $Σ$ never exceeds the projective rank of the complement; a rank inequality for the same square makes this strict on a 1440-vertex graph.

AI Summary

The paper asks whether the Lovász number $\vartheta$ is the only point in the entanglement-assisted asymptotic spectrum of graphs. It defines $\vartheta_\alpha$, for $0\le\alpha\le2$, by minimizing Petz–Rényi information radii over compatible classical–quantum channels and center states. The endpoints are $\vartheta_0=\vartheta$, $\vartheta_1=2^{C_{\min}}$, and $\vartheta_2=\Sigma$, linking the Lovász number, minimal Holevo capacity, and no-signalling simulation cost. Every $\vartheta_\alpha$ is proved additive under disjoint union, multiplicative under strong product, and monotone under entanglement-assisted cohomomorphisms. Multiplicativity handles arbitrary joint representations using an exact nesting identity for power compressions; monotonicity follows from data processing. Sandwiched Rényi radii yield the same family under $\alpha=2-1/\beta$. On $C_5$, the family continuously covers $[\sqrt5,5/2]$, establishing continuum many distinct spectral points, and equals $5/2$ for $\alpha\ge1/2$. A dimension-independent Hilbert–Schmidt inequality proves the pentagon conjecture $C_{\min}(C_5)=\log_2(5/2)$. Multiplicativity also establishes the single-letter graph-level simulation rate $S_{0,\mathrm{NS}}(G)=\log_2\Sigma(G)$. Exact rational certificates separate $2^{C_{\min}}\le6.186983\ldots<6.194232\ldots\le\Sigma$ on a 32-vertex magic-square graph. A contextual rank inequality separates $\Sigma$ from complementary projective rank on 1,440 vertices: $\Sigma\le240.2002\ldots<240.2033\ldots\le\xi_f(\overline G)$. All constructed points dominate $\vartheta$, leaving $\Theta_*=\vartheta$ unresolved. The exact pentagon curve below order $1/2$, left continuity at orders $1$–$2$, spectral membership above order two, and extensions to non-commutative graphs remain open.

Little sign of AI-generated textAI use disclosed
Generative AI tools were used throughout the research and preparation of this manuscript, including for mathematical exploration, proof development and critique, literature organization, computational assistance, and drafting.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
35 pages, 5 figures, 1 table. Version 1.2.1 of Zenodo record https://doi.org/10.5281/zenodo.22983498; code: https://github.com/Apsiape/the-lovasz-number-is-not-alone

Related papers

Quantum Asymptotic Spectra of Graphs and Non-Commutative Graphs, and Quantum Shannon Capacities

Yinan Li, Jeroen Zuiddam

We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.

arXiv:1810.00744•IEEE Transactions on Information Theory•Oct 22, 2020•11 citations

Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász \(\vartheta \) Number and Its Variants

Toby S. Cubitt, Laura Mancinska, David E. Roberson +3 more

We study zero-error entanglement-assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if ϑ(G̅) ≤ ϑ(H̅), where ϑ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ϑ-and Szegedy ϑ+numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement-assisted cost rate. We show that the entanglement-assisted independence number is bounded by the Schrijver number: α*(G) ≤ ϑ-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity β as an upper bound on α* and posed the question of whether β(G) = ⌊ϑ(G)⌋. We answer this in the affirmative and show that a related quantity is equal to ⌊ϑ(G)⌋. We show that a quantity χvect(G) recently introduced in the context of Tsirelson's problem is equal to ⌊ϑ+(G)⌋. In an appendix, we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.

arXiv:1310.7120•IEEE Transactions on Information Theory•Aug 19, 2014•38 citations

Exact certification of a positive-order Rényi additivity violation for an explicit channel pair

Artus Krohn-Grimberghe

Cubitt, Harrow, Leung, Montanaro, and Winter (CHLMW) exhibited an explicit pair of quantum channels whose minimum output Rényi entropy is nonadditive at order zero, and reported numerical violations at positive orders close to zero. Their paper states that a semidefinite-programming argument yields a rigorous positive-order interval for the same example, without printing the endpoint or a verifiable certificate; a recent paper by Leung, Lovitz, and Wu records that for this pair "no rigorous endpoint was obtained". We close that gap for the trace-preserving normalization of the printed pair fixed in Section 2. Small rational witness matrices prove that every output of either channel has all eigenvalues between $301/100000$ and $2/3$; a single explicit entangled input has an exact rational joint output spectrum of rank eight; and two independent elementary interval arguments turn these three facts into a proof of strict additivity violation, $S_p^{\min}(\mathrm{N}_R\otimes\mathrm{N}_{\bar S}) < S_p^{\min}(\mathrm{N}_R)+S_p^{\min}(\mathrm{N}_{\bar S}),$ for every real order $0<p\le 1/22$. Every step of the verification reduces to comparisons of integers, and the complete certificate is a few small rational matrices that a reader can check with a short program -- or, for any single order, by hand. To our knowledge, consistent with the assessment of Leung, Lovitz, and Wu, this is the first printed, computer-verifiable certified positive-order endpoint for this explicit pair. We claim no novelty for the phenomenon or for the eigenvalue-floor mechanism, both due to CHLMW, and no optimality of the endpoint.

quant-pharXiv:2608.17376•Aug 19, 2026•0 citations

Noncommutative extensions of parameters in the asymptotic spectrum of graphs

Péter Vrana

The zero-error capacity of a classical channel is a parameter of its confusability graph, and is equal to the minimum of the values of graph parameters that are additive under the disjoint union, multiplicative under the strong product, monotone under homomorphisms between the complements, and normalized. We show that any such function either has uncountably many extensions to noncommutative graphs with similar properties, or no such extensions at all. More precisely, we find that every extension has an exponent that characterizes its values on the confusability graphs of identity quantum channels, and the set of admissible exponents is either an unbounded subinterval of $[1,\infty)$ or empty. In particular, the set of admissible exponents for the Lovász number, the projective rank, and the fractional Haemers bound over the complex numbers are maximal, while the fractional clique cover number does not have any extensions.

arXiv:2207.10483•Jul 21, 2022•3 citations

The Haemers Bound of Noncommutative Graphs

Sander Gribling, Yinan Li

We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, IEEE Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).

arXiv:2002.02743•IEEE Journal on Selected Areas in Information Theory•Jul 31, 2020•4 citations

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

Xin Wang, Runyao Duan

Quantum Lovász number is a quantum generalization of the Lovász number in graph theory. It 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 quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lovász number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lovász number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signaling correlations, which differs from the case of classical channels.

arXiv:1608.04508•IEEE Transactions on Information Theory•Jan 17, 2018•15 citations
Li and Zuiddam's entanglement-assisted asymptotic spectrum of graphs consists of the normalized graph parameters that are additive under disjoint unions, multiplicative under strong products and monotone under entanglement-assisted cohomomorphisms; the entanglement-assisted Shannon capacity is their pointwise minimum. To our knowledge, the Lovász number ϑ\varthetaϑ was its only known element. We find a continuum of others.
Three quantities of Duan and Winter, log⁡2ϑ\log_2\varthetalog2​ϑ, the minimal Holevo capacity Cmin⁡C_{\min}Cmin​ and the logarithm of the no-signalling simulation cost ΣΣΣ, are the smallest information radii of classical-quantum channels compatible with a graph, measured with Petz-Rényi divergences of orders 000, 111 and 222. At order zero this is due to Schrijver (as credited by Dalai) and to Duan and Winter; at order one it is the min-max formula for the Holevo capacity. Interpolating in the order gives a family ϑα\vartheta_αϑα​, 0≤α≤20\leα\le20≤α≤2, and we prove that every member lies in the spectrum. The main step, multiplicativity under strong products for channels that need not factor, follows from an exact nesting identity for compressions. Sandwiched Rényi radii of order β∈[1/2,∞]β\in[1/2,\infty]β∈[1/2,∞] give the same family, at α=2−1/βα=2-1/βα=2−1/β.
On the five-cycle the family takes every value in [5,5/2][\sqrt5,5/2][5​,5/2]. A Hilbert-Schmidt inequality for the pentagon gives Cmin⁡(C5)=log⁡2(5/2)C_{\min}(C_5)=\log_2(5/2)Cmin​(C5​)=log2​(5/2), proving a conjecture of Duan and Winter. We also settle the two open links of their inequality chain: the graph-level no-signalling simulation rate always equals its single-letter value log⁡2Σ(G)\log_2Σ(G)log2​Σ(G), and a 32-vertex graph from the Mermin-Peres magic square has Cmin⁡<log⁡2ΣC_{\min}<\log_2ΣCmin​<log2​Σ, certified in exact rational arithmetic. Finally, ΣΣΣ never exceeds the projective rank of the complement; a rank inequality for the same square makes this strict on a 1440-vertex graph.
The paper asks whether the Lovász number ϑ\varthetaϑ is the only point in the entanglement-assisted asymptotic spectrum of graphs. It defines ϑα\vartheta_\alphaϑα​, for 0≤α≤20\le\alpha\le20≤α≤2, by minimizing Petz–Rényi information radii over compatible classical–quantum channels and center states. The endpoints are ϑ0=ϑ\vartheta_0=\varthetaϑ0​=ϑ, ϑ1=2Cmin⁡\vartheta_1=2^{C_{\min}}ϑ1​=2Cmin​, and ϑ2=Σ\vartheta_2=\Sigmaϑ2​=Σ, linking the Lovász number, minimal Holevo capacity, and no-signalling simulation cost.
Every ϑα\vartheta_\alphaϑα​ is proved additive under disjoint union, multiplicative under strong product, and monotone under entanglement-assisted cohomomorphisms. Multiplicativity handles arbitrary joint representations using an exact nesting identity for power compressions; monotonicity follows from data processing. Sandwiched Rényi radii yield the same family under α=2−1/β\alpha=2-1/\betaα=2−1/β. On C5C_5C5​, the family continuously covers [5,5/2][\sqrt5,5/2][5​,5/2], establishing continuum many distinct spectral points, and equals 5/25/25/2 for α≥1/2\alpha\ge1/2α≥1/2. A dimension-independent Hilbert–Schmidt inequality proves the pentagon conjecture Cmin⁡(C5)=log⁡2(5/2)C_{\min}(C_5)=\log_2(5/2)Cmin​(C5​)=log2​(5/2).
Multiplicativity also establishes the single-letter graph-level simulation rate S0,NS(G)=log⁡2Σ(G)S_{0,\mathrm{NS}}(G)=\log_2\Sigma(G)S0,NS​(G)=log2​Σ(G). Exact rational certificates separate 2Cmin⁡≤6.186983…<6.194232…≤Σ2^{C_{\min}}\le6.186983\ldots<6.194232\ldots\le\Sigma2Cmin​≤6.186983…<6.194232…≤Σ on a 32-vertex magic-square graph. A contextual rank inequality separates Σ\SigmaΣ from complementary projective rank on 1,440 vertices: Σ≤240.2002…<240.2033…≤ξf(G‾)\Sigma\le240.2002\ldots<240.2033\ldots\le\xi_f(\overline G)Σ≤240.2002…<240.2033…≤ξf​(G).
All constructed points dominate ϑ\varthetaϑ, leaving Θ∗=ϑ\Theta_*=\varthetaΘ∗​=ϑ unresolved. The exact pentagon curve below order 1/21/21/2, left continuity at orders 111–222, spectral membership above order two, and extensions to non-commutative graphs remain open.
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true.
Bounds on Entanglement-Assisted Source-Channel Coding via the Lovász ϑ\vartheta ϑ Number and Its Variants
We study zero-error entanglement-assisted source-channel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if ϑ(G̅) ≤ ϑ(H̅), where ϑ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ϑ-and Szegedy ϑ+numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement-assisted cost rate. We show that the entanglement-assisted independence number is bounded by the Schrijver number: α*(G) ≤ ϑ-(G). Therefore, we are able to disprove the conjecture that the one-shot entanglement-assisted zero-error capacity is equal to the integer part of the Lovász number. Beigi introduced a quantity β as an upper bound on α* and posed the question of whether β(G) = ⌊ϑ(G)⌋. We answer this in the affirmative and show that a related quantity is equal to ⌊ϑ(G)⌋. We show that a quantity χvect(G) recently introduced in the context of Tsirelson's problem is equal to ⌊ϑ+(G)⌋. In an appendix, we investigate multiplicativity properties of Schrijver's and Szegedy's numbers, as well as projective rank.
Cubitt, Harrow, Leung, Montanaro, and Winter (CHLMW) exhibited an explicit pair of quantum channels whose minimum output Rényi entropy is nonadditive at order zero, and reported numerical violations at positive orders close to zero. Their paper states that a semidefinite-programming argument yields a rigorous positive-order interval for the same example, without printing the endpoint or a verifiable certificate; a recent paper by Leung, Lovitz, and Wu records that for this pair "no rigorous endpoint was obtained". We close that gap for the trace-preserving normalization of the printed pair fixed in Section 2. Small rational witness matrices prove that every output of either channel has all eigenvalues between 301/100000301/100000301/100000 and 2/32/32/3; a single explicit entangled input has an exact rational joint output spectrum of rank eight; and two independent elementary interval arguments turn these three facts into a proof of strict additivity violation, Spmin⁡(NR⊗NSˉ)<Spmin⁡(NR)+Spmin⁡(NSˉ),S_p^{\min}(\mathrm{N}_R\otimes\mathrm{N}_{\bar S}) < S_p^{\min}(\mathrm{N}_R)+S_p^{\min}(\mathrm{N}_{\bar S}),Spmin​(NR​⊗NSˉ​)<Spmin​(NR​)+Spmin​(NSˉ​), for every real order 0<p≤1/220<p\le 1/220<p≤1/22. Every step of the verification reduces to comparisons of integers, and the complete certificate is a few small rational matrices that a reader can check with a short program -- or, for any single order, by hand. To our knowledge, consistent with the assessment of Leung, Lovitz, and Wu, this is the first printed, computer-verifiable certified positive-order endpoint for this explicit pair. We claim no novelty for the phenomenon or for the eigenvalue-floor mechanism, both due to CHLMW, and no optimality of the endpoint.
The zero-error capacity of a classical channel is a parameter of its confusability graph, and is equal to the minimum of the values of graph parameters that are additive under the disjoint union, multiplicative under the strong product, monotone under homomorphisms between the complements, and normalized. We show that any such function either has uncountably many extensions to noncommutative graphs with similar properties, or no such extensions at all. More precisely, we find that every extension has an exponent that characterizes its values on the confusability graphs of identity quantum channels, and the set of admissible exponents is either an unbounded subinterval of [1,∞)[1,\infty)[1,∞) or empty. In particular, the set of admissible exponents for the Lovász number, the projective rank, and the fractional Haemers bound over the complex numbers are maximal, while the fractional clique cover number does not have any extensions.
We continue the study of the quantum channel version of Shannon's zero-error capacity problem. We generalize the celebrated Haemers bound to noncommutative graphs (obtained from quantum channels). We prove basic properties of this bound, such as additivity under the direct sum and submultiplicativity under the tensor product. The Haemers bound upper bounds the Shannon capacity of noncommutative graphs, and we show that it can outperform other known upper bounds, including noncommutative analogues of the Lovász theta function (Duan-Severini-Winter, IEEE Trans. Inform. Theory, 2013 and Boreland-Todorov-Winter, arXiv preprint, 2019).
Quantum Lovász number is a quantum generalization of the Lovász number in graph theory. It 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 quantum entanglement can always enhance the zero-error capacity to achieve the quantum Lovász number. In this paper, by constructing a particular class of qutrit-to-qutrit channels, we show that there exists a strict gap between the entanglement-assisted zero-error capacity and the quantum Lovász number. Interestingly, for this class of quantum channels, the quantum generalization of fractional packing number is strictly larger than the zero-error capacity assisted with feedback or no-signaling correlations, which differs from the case of classical channels.