⚛️ quantum physics

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

This paper establishes a continuum of new elements, denoted as $\vartheta_\alpha$ for $0 \le \alpha \le 2$ , within the entanglement-assisted asymptotic spectrum of graphs by interpolating between the Lovász number, minimal Holevo capacity, and no-signalling simulation cost using Petz-Rényi divergences, thereby resolving several open conjectures regarding their relationships and specific values.

Original authors: Nidhal Mghirbi, Seth Douglas

Published 2026-10-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nidhal Mghirbi, Seth Douglas

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of information theory, there is a fundamental question about how much data can be sent perfectly, without a single error, through a noisy channel. Imagine a telephone line where certain words sound so similar that a listener might confuse one for another. If you try to send a message using only those confusing words, you will inevitably make mistakes. To avoid this, you must choose your words carefully, picking only those that are distinct enough to be told apart. The mathematical structure that describes which words can be confused with which is called a graph, where dots represent the words and lines connect the ones that sound alike. For decades, scientists have struggled to calculate the maximum rate at which information can be sent through such a graph with absolute certainty. This limit is known as the zero-error capacity.

For a long time, the best tool mathematicians had to estimate this limit was a single, famous number called the Lovász number. It acts like a ceiling, telling us that the true capacity can never be higher than this value. In recent years, researchers discovered that if the sender and receiver share a special quantum resource called entanglement, they can sometimes communicate better than classical physics allows. This led to a new, more powerful version of the problem, where the ceiling might be higher. For a while, it seemed that the Lovász number might be the only tool available to measure this new, entanglement-assisted capacity. Scientists wondered if this single number was the only possible answer, or if there were other, hidden limits waiting to be found.

A team of researchers has now shown that the Lovász number is not alone. They have discovered a continuous family of new mathematical tools, a whole spectrum of values that sit alongside the original number. These new tools are not just theoretical curiosities; they are proven to be valid limits on how much information can be sent. The researchers found that these tools are connected to different ways of measuring the "distance" between quantum states, a concept that changes depending on which specific mathematical lens you use to look at the data. By adjusting this lens, they generated an infinite number of distinct values, each one a valid upper bound on the communication capacity. This means the landscape of what we know about quantum communication is much richer and more complex than previously thought.

To understand how they found this, one must look at the specific problem of the "pentagon." In graph theory, a simple shape with five points connected in a circle is a classic test case. For this shape, the original Lovász number gives a value of the square root of five, while the absolute maximum possible rate is two and a half. The researchers wanted to know what happens in between these two extremes. They constructed a family of measurements that smoothly transitions from the Lovász number to the higher limit. They proved that for the pentagon, this family of measurements actually takes on every single value between the square root of five and two and a half. This is a massive discovery because it confirms that the entanglement-assisted spectrum is not a single point, but a continuous line of possibilities.

The team did not stop at the pentagon. They also investigated whether the different members of this new family were truly distinct from one another. They built a complex graph based on a famous quantum puzzle known as the Mermin–Peres magic square. This graph has thirty-two points. By running precise calculations on this graph, they showed that one specific member of their new family, which corresponds to a measure of communication efficiency, gives a strictly smaller number than another member of the family, which corresponds to the cost of simulating the communication. This proves that the different tools in their new family are not just different ways of saying the same thing; they are genuinely different limits that separate from each other on certain graphs.

Furthermore, the researchers settled a long-standing question about the cost of simulating these quantum channels. They proved that the cost to simulate a channel over a long period of time is exactly the same as the cost to simulate it in a single step. This was an open question that had puzzled experts for years. They showed that the complexity of the simulation does not grow or change when you look at the system over time; the single-step calculation is sufficient to describe the long-term behavior. This result simplifies the way scientists can think about these quantum communication problems, turning a difficult, long-term calculation into a manageable, one-time problem.

The paper also addressed the relationship between these new numbers and another known limit called the projective rank. For some graphs, the new simulation cost number and the projective rank are identical. However, the researchers constructed a massive graph with 1,440 points to show that this is not always true. On this large graph, the simulation cost is strictly lower than the projective rank. This finding closes a potential path that some had hoped would link these two concepts together, showing instead that they are distinct measures of complexity.

In the end, this work transforms our understanding of the limits of quantum communication. It replaces the idea of a single, solitary ceiling with a vast, continuous range of ceilings, each offering a different perspective on how much information can be sent. The researchers have provided a rigorous proof that these new limits exist, are distinct, and are essential for understanding the full potential of entanglement-assisted communication. They have moved the field from a place of uncertainty, where only one tool was known, to a landscape filled with a continuum of precise, measurable boundaries.

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

Problem Statement
The paper addresses the structure of the entanglement-assisted asymptotic spectrum of graphs, denoted $X(G, \leq^*)$ . This spectrum consists of graph parameters that are additive under disjoint unions, multiplicative under strong products, and monotone under the entanglement-assisted cohomomorphism preorder. According to Strassen's duality theorem adapted by Li and Zuiddam, the entanglement-assisted Shannon capacity $\Theta^*(G)$ is the pointwise minimum of all elements in this spectrum. Prior to this work, the Lovász number $\vartheta(G)$ was the only known element of $X(G, \leq^*)$ other than trivial bounds. A significant open question was whether $\vartheta$ was the only element or the least element of the spectrum, which would imply $\Theta^*(G) = \vartheta(G)$ . The paper investigates whether a continuum of other spectral points exists.

Methodology
The authors construct a family of graph parameters $\vartheta_\alpha(G)$ indexed by a real parameter $\alpha \in [0, 2]$ . These parameters are defined as the minimum order- $\alpha$ information radius of classical-quantum channels compatible with a graph $G$ , measured using Petz–Rényi divergences $D_\alpha$ . Specifically:
$\log \vartheta_\alpha(G) = \inf_{(\rho_x), \sigma} \max_{x \in V(G)} D_\alpha(\rho_x \| \sigma)$
where $(\rho_x)$ is a family of states compatible with $G$ and $\sigma$ is a faithful state.

The methodology relies on three main technical pillars:

Projection Formula: The authors rewrite the optimization over states into an optimization over orthogonal projections (representations of the graph) using a "power compression" technique. This establishes a projection formula involving weights $Z_s(\sigma, P)$ where $s = 1-\alpha$ .
Multiplicativity via Tower Identity: To prove that $\vartheta_\alpha$ belongs to the spectrum, the authors must demonstrate multiplicativity under the strong product ( $G \boxtimes H$ ). For representations that are not simple tensor products, they employ an "exact nesting identity" (the tower identity) for compressions. This allows the weight of a joint representation to be factored into row and column components, proving $\vartheta_\alpha(G \boxtimes H) = \vartheta_\alpha(G)\vartheta_\alpha(H)$ .
Data Processing and Monotonicity: The authors utilize the data-processing inequality for Petz–Rényi divergences, which holds for $\alpha \in [0, 2]$ , to establish monotonicity under the entanglement-assisted preorder. They note that this argument fails for $\alpha > 2$ because data processing no longer holds for Petz divergences in that regime.

Key Contributions and Results

A Continuum of Spectral Points (Theorem A): The paper proves that for every $\alpha \in [0, 2]$ , the parameter $\vartheta_\alpha$ lies in the entanglement-assisted asymptotic spectrum $X(G, \leq^*)$ . This establishes the existence of a continuum of distinct spectral points, refuting the possibility that $\vartheta$ is the sole element.
Unification of Duan–Winter Quantities: The work identifies three previously distinct quantities from Duan and Winter as specific instances of the family $\vartheta_\alpha$ $ϑ_{α}$ :
- $\vartheta_0 = \vartheta$ (Lovász number)
- $\vartheta_1 = 2C_{\min}$ (Twice the minimal Holevo capacity)
- $\vartheta_2 = \Sigma$ (No-signalling simulation cost)
  The paper further shows that sandwiched Rényi radii $\tilde{\vartheta}_\beta$ for $\beta \in [1/2, \infty]$ map exactly to this same family via the relation $\tilde{\vartheta}_\beta = \vartheta_{2-1/\beta}$ .
The Pentagon (Theorem B): On the 5-cycle graph ( $C_5$ $C_{5}$ ), the family $\vartheta_\alpha$ $ϑ_{α}$ takes every value in the interval $[\sqrt{5}, 5/2]$ $[5, 5/2]$ .
- For $\alpha \in [1/2, 2]$ , $\vartheta_\alpha(C_5) = 5/2$ .
- For $\alpha \in [0, 1/2]$ , the value interpolates continuously between $\sqrt{5}$ and $5/2$ .
  This result proves that the spectrum contains continuum many distinct points, as parameters with different values on $C_5$ are distinct functions.
Resolution of the Duan–Winter Chain: The paper settles open questions regarding the chain of inequalities $\log_2 \vartheta \leq C_{\min} \leq S_{0,NS} \leq \log_2 \Sigma \leq \log_2 \alpha^*$ $lo g_{2} ϑ \leq C_{m i n} \leq S_{0, N S} \leq lo g_{2} Σ \leq lo g_{2} α^{*}$ :
- Strictness on $C_5$ : It proves $C_{\min}(C_5) = \log_2(5/2)$ , confirming the conjecture that the first inequality is strict on the pentagon.
- Graph-Level Simulation Cost: It proves that the asymptotic no-signalling simulation cost $S_{0,NS}(G)$ equals the single-letter value $\log_2 \Sigma(G)$ for all graphs, settling an open problem regarding the additivity of $\log \Sigma$ under strong products.
- Separation of Orders: Using a 32-vertex graph derived from the Mermin–Peres magic square ( $G_{32}$ ), the authors prove that $C_{\min}(G_{32}) < \log_2 \Sigma(G_{32})$ , demonstrating that order 1 and order 2 are distinct.
- Separation from Projective Rank: Using a 1440-vertex graph ( $G_{1440}$ ), the authors prove that $\Sigma(G) < \xi_f(G)$ (the projective rank of the complement), showing that order 2 is not equivalent to the projective rank.

Significance and Claims
The paper claims to fundamentally alter the understanding of the entanglement-assisted spectrum by demonstrating it is not a singleton set containing only the Lovász number. By constructing a continuum of spectral points $\vartheta_\alpha$ , the authors show that the spectrum is rich and complex.

However, the authors are modest regarding the implications for the Shannon capacity conjecture. They explicitly state that since every $\vartheta_\alpha$ dominates $\vartheta$ (i.e., $\vartheta_\alpha \geq \vartheta$ ), the bound $\Theta^* \leq \vartheta$ is not improved, and the conjecture $\Theta^* = \vartheta$ remains open. The new points do not provide a lower bound on $\Theta^*$ that is tighter than $\vartheta$ .

The work also clarifies the operational meaning of the quantities in the Duan–Winter chain, particularly establishing the single-letter formula for graph-level no-signalling simulation costs. Finally, the paper distinguishes between different quantum information radii and graph parameters (like the projective rank) that were previously suspected to be equivalent or closely related, providing exact rational arithmetic certificates for these separations.

The paper does not claim to extend these results to non-commutative graphs (though it poses this as an open problem) nor does it claim that the spectrum is log-convex in the entanglement-assisted setting, noting that such a property would require a new theory of probabilistic refinements.

More like this