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.
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
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 ϑ was its only known element. We find a continuum of others.
Three quantities of Duan and Winter, log2ϑ, the minimal Holevo capacity 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 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 ϑα, 0≤α≤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,∞] give the same family, at α=2−1/β.
On the five-cycle the family takes every value in [5,5/2]. A Hilbert-Schmidt inequality for the pentagon gives 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 log2Σ(G), and a 32-vertex graph from the Mermin-Peres magic square has 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.
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.
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,∞) 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.
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, Spmin(NR⊗NSˉ)<Spmin(NR)+Spmin(NSˉ), for every real order 0<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.
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).
We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space K, we introduce a semidefinite programming parameter Γ(K) that is exactly multiplicative under tensor products and upper-bounds ΘNS(K), where log2ΘNS(K)=C0,NS(K) and C0,NS(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on ΘNS given by semidefinite programs, Γ is the tightest. We also prove that the previously introduced simulation lower bound Σ−(K) is exactly multiplicative and satisfies ΘNS(K)≤Γ(K)≤Σ−(K)≤Γ(K)2. Using this multiplicativity, we show that neither S0,NS(K)=log2Σ−(K) nor its regularized extension S0,NS(K)=limn→∞n−1log2Σ−(K⊗n) holds in general. This answers an open question about the asymptotic simulation cost S0,NS(K). For classical-quantum channels, we obtain sharp bounds. If r is the effective output dimension, then ΘNS≤Γ≤(1+r1/2)ΘNS/2 and Γ≤Σ−≤(1+r1/2)Γ/2. If k is the minimum rank of the output support projections, then Σ−/ΘNS≤[(1+r1/2)/(1+k1/2)]2, and this bound is sharp for every 1≤k≤r. Thus, we obtain the sharp bound S0,NS−C0,NS≤2log2[(1+r1/2)/(1+k1/2)].
The noise threshold below which the qubit depolarizing channel retains positive quantum capacity has been studied since 1996. The classic constructions come with exact finite formulae, but in every reported threshold to date -- most recently the record of Agarwal et al. -- the final step, the sign of the coherent information at the reported point, is a floating-point evaluation. We give the first exact-arithmetic, independently machine-checkable positivity proofs in this regime: an explicit 45-copy rank-two input state A, published as a 1,472-byte witness, with certified Ic>0 at the exact rational p=16239/250000=0.064956 (per-Pauli convention; total error rate 3p=0.194868) -- beyond both the best value printed in the Agarwal et al. paper (0.064657) and the strongest state in the same authors' public repository (≈0.064911), both numerical. Because the depolarizing family is a semigroup under composition, fixed-input coherent information is nonincreasing in p on [0,1/4], so a single certified point extends to the entire interval below it. The same machinery confines the positivity boundaries of A and of the strongest public state of Agarwal et al. to disjoint rational intervals separated by more than 1/25000 -- to our knowledge the first proven ordering of the positivity boundaries of two explicit competing code states. Every computational claim in the paper reduces to a finite list of big-integer comparisons, checkable by a dependency-free few-hundred-line verifier whose soundness rests on three self-contained half-page lemmas. Payloads, certificates, and verifier accompany the paper as a supplementary artifact.