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

AI summary

Overview

Research area: Quantum information theory, specifically zero-error communication and the asymptotic spectrum of graphs (graph parameters, entanglement-assisted channel capacities, and Rényi information measures).

Technical level: Advanced. The paper is written for researchers comfortable with semidefinite programming, Rényi divergences, and quantum channel capacities.

Scope (one sentence): The paper constructs a continuous family of new points in the entanglement-assisted asymptotic spectrum of graphs, interpolating between the Lovász number, the minimal Holevo capacity, and the no-signalling simulation cost, and uses explicit graphs to show these points are genuinely distinct.

What This Paper Is About

Li and Zuiddam defined an entanglement-assisted asymptotic spectrum of graphs whose pointwise minimum is the entanglement-assisted Shannon capacity, but the only known member of that spectrum was the Lovász number. This paper shows the Lovász number is not alone: a one-parameter family of graph parameters, indexed by a Rényi order between 0 and 2, all belong to the spectrum. The authors then prove that different members of the family take different values on specific graphs, settling several open questions about the Duan–Winter inequality chain along the way.

Key Contributions

1. A continuum of spectral points. For every order α in [0, 2], the graph parameter ϑ_α defined via Petz–Rényi information radii belongs to the entanglement-assisted asymptotic spectrum, with ϑ_0 = ϑ (Lovász number), ϑ_1 = 2^{C_min}, and ϑ_2 = Σ. Only the α = 0 case was previously known.
2. Multiplicativity without factorization. The hard step is proving ϑ_α(G ⊠ H) = ϑ_α(G)ϑ_α(H) for representations of the strong product that are not tensor products. This is handled by an exact nesting identity for power compressions. It yields a single-letter formula for graph-level no-signalling simulation, S_{0,NS}(G) = log₂ Σ(G), resolving an open question of Duan and Winter.
3. The pentagon conjecture. A Hilbert–Schmidt inequality for the five-cycle gives C_min(C₅) = log₂(5/2), proving the conjecture of Duan and Winter, and shows the family attains every value in [√5, 5/2] on C₅.
4. Two separations. A 32-vertex graph built from the Mermin–Peres magic square has 2^{C_min} strictly below Σ (so order one differs from order two), and a 1440-vertex graph has Σ strictly below the projective rank of its complement (so order two is not the projective rank).

Main Findings

• Theorem A (every order up to two is a spectral point): For every α ∈ [0, 2], ϑ_α lies in the entanglement-assisted asymptotic spectrum X(G, ≤). Normalization and additivity are routine; monotonicity under ≤ follows from data processing, which is why the construction stops at order two, since Petz divergences lose data processing above order two (Remark 4.8).
• Three quantities, one family: The Duan–Winter chain log₂ ϑ(G) ≤ C_min(G) ≤ S_{0,NS}(G) ≤ log₂ Σ(G) ≤ log₂ α*(G) is recovered as samples at orders 0, 1, and 2 of a single nondecreasing family. The sandwiched Rényi radii of order β ∈ [1/2, ∞] give the same family at α = 2 − 1/β (Proposition 3.5).
• Theorem B (the pentagon): For 1/2 ≤ α ≤ 2, ϑ_α(C₅) = 5/2. For 0 ≤ α ≤ 1/2, with p = 1/(1 − α) ∈ [1, 2], √5·(√5/2)^{p−1} ≤ ϑ_α(C₅) ≤ min{5/2, √5·5^{(p−1)/2}}. The map is continuous and carries [0, 1/2] onto [√5, 5/2], so the spectrum contains continuum many distinct points.
• Duan–Winter pentagon corollary: log₂ √5 < C_min(C₅) = S_{0,NS}(C₅) = log₂ Σ(C₅) = log₂ α*(C₅) = log₂(5/2). The upper bounds come from the Duan–Winter chain; the new ingredient is the lower bound C_min(C₅) ≥ log₂(5/2).
• Theorem C (order one is not order two): For the 32-vertex magic-square graph G₃₂, 2^{C_min(G₃₂)} ≤ 6.186983… < 6.194232… ≤ Σ(G₃₂). In exact rational form the certified bounds are 32329248967670751/5225365592240894 < 93824992214030/15147154828811. For this graph ϑ(G₃₂) = 6 and α*(G₃₂) = 32/5, so ϑ_1 ≠ ϑ_2.
• Theorem D (order two is not the projective rank): For a 1440-vertex magic-square graph G₁₄₄₀, Σ(G₁₄₄₀) ≤ 215940/899 = 240.2002… < 240.2033… = 14172/59 ≤ ξ_f(complement of G₁₄₄₀). The lower bound is a rank inequality for the magic square valid in every dimension (Lemma 7.3), based on approximate anticommutation of cell observables.
• Flat witnesses and projective rank: Every d/r-representation of the complement is a flat witness, so Σ(G) ≤ ξ_f(complement of G) for all graphs, with equality on C₅ and on Duan and Winter's Hadamard example. Theorem D shows equality fails in general.
• Status of the chain's links: The first link is strict on C₅ (proved here); the second can be strict (Theorem C); the third is always an equality (Theorem 4.1 at order two); the fourth can be strict, as already shown by Duan and Winter.
• Range of the family: Every ϑ_α lies between ϑ and α*. The family collapses to a single value on graphs with ϑ = α*, including perfect graphs, and can only separate points on graphs with ϑ < α*.

Methodology in Plain English

The authors recast a known construction from Duan and Winter. Instead of studying channels one at a time, they attach to each graph the smallest "information radius" achievable by any classical–quantum channel compatible with that graph: pick a center state, measure how far each output is from the center using a Rényi divergence of order α, take the worst input, and then minimize over channels and centers. At α = 0 this is the Lovász number, at α = 1 it is the Holevo-capacity formula, and at α = 2 it matches the no-signalling simulation cost.

To show each of these parameters belongs to the asymptotic spectrum, they must verify four axioms: additivity under disjoint union, multiplicativity under strong product, normalization on a single vertex, and monotonicity under entanglement-assisted cohomomorphisms. Multiplicativity is the difficult one, because an optimal representation of a product graph need not be a tensor product of representations of the factors. The authors handle this with an exact identity that controls how "power compressions" of a state nest inside one another, reducing the product problem to a single-graph statement.

For the pentagon, they use a local geometric fact: the two neighbours of a vertex in C₅ are non-adjacent, so their projections sum to a projection, which limits how much of the identity the five projections can cover. This gives a Hilbert–Schmidt inequality and hence the lower bound. The matching upper bound comes from the simple classical channel that outputs a uniformly random element of {i, i+1}.

The separations use graphs derived from the Mermin–Peres magic square. Upper bounds are exhibited by explicit order-two witnesses (a magic-square representation with a slightly tilted center), while lower bounds are certified in exact rational arithmetic, so no floating-point error is involved.

Why This Matters

Impact on research: The paper overturns the working assumption that the Lovász number might be the only point of the entanglement-assisted spectrum. It also settles several explicitly stated open problems: the Duan–Winter pentagon conjecture, the single-letter nature of graph-level no-signalling simulation, and the strictness of the middle links of their chain. The identification of three apparently different quantities as one monotone family simplifies the landscape and explains why they are ordered as they are.

Potential applications (long-term and indirect, since the work is theoretical):

• Zero-error communication over noisy classical and quantum channels, where confusability graphs and their spectral parameters give upper bounds on achievable rates.
• Entanglement-assisted channel simulation and no-signalling-assisted protocols, where Σ and S_{0,NS} quantify the cost of simulating a channel exactly.
• Benchmarking semidefinite-programming relaxations: the new family provides a continuum of computable bounds between ϑ and α*, potentially tighter than either in intermediate regimes.
• Network coding and index-coding-style problems, where graph spectra and fractional packing numbers are standard tools.

Industry relevance: The results are foundational rather than deployable. They are most relevant to research groups in quantum communication, information-theoretic security, and optimization who design or analyze entanglement-assisted protocols and semidefinite relaxations.

Future Directions

• Is ϑ the least point? The authors show ϑ is not the only point, ruling out one of Li and Zuiddam's two suggested routes to Θ* = ϑ. The other route, that ϑ is the least element, and hence Θ* = ϑ, is untouched, since every ϑ_α dominates ϑ.
• Projective rank in the entanglement-assisted spectrum. Whether ξ_f(complement of G) lies in X(G, ≤*) remains open. Theorem D shows the natural route through equality with Σ fails, but does not decide the question.
• Interpolation beyond known points. Vrana's log-convex interpolation yields continua in the ordinary spectrum; whether an analogue holds for the entanglement-assisted preorder ≤* is not known. The authors give a heuristic (Section 8) for why ϑ_1 should not be an interpolation between ϑ and Σ.
• Beyond order two and beyond cq-graphs. Data processing for Petz divergences fails above order two, so the construction cannot simply be extended. Duan and Winter's general problem for non-commutative bipartite graphs that are not cq-graphs is also not addressed.

Target Audience

Researchers and graduate students in quantum information theory, quantum Shannon theory, and algebraic graph theory, particularly those working on zero-error capacities, entanglement-assisted communication, asymptotic spectra of graphs, and Rényi-divergence methods. Readers interested in semidefinite programming and exact-certificate verification will also find the constructive separations (Theorems C and D) valuable. A background in quantum channel capacities and linear algebra is assumed.

Authors’ 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}&lt;\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.