Foundations of quantum mechanics · Theory (AI-assisted)

Communication inequalities: robust quantum advantage, measurement testing and dimension witnessing with minimal setups

Albert Rico; Javier Fernández; Mani Zartab; John Calsamiglia; Some Sankar Bhattacharya

arXiv:2611.15995v1 ↗PDF ↗Submitted 11 November 2026

Question
In the simplest communication scenario Alice encodes one of \(n\) messages, Bob makes a single \(n\)-outcome measurement, and there is no shared randomness and no input for Bob. The classical system size needed to reproduce the matrix \(P_{ij}=p(i|j)\) is its nonnegative rank, and quantum systems can sometimes do the same with fewer levels. Because the sets of matrices achievable at fixed dimension are not convex, linear witnesses do not apply, and quantum advantage had been shown only at isolated examples. Can it be certified from a few numbers, with a margin for noise?
Result
Theorem 1 bounds the classical dimension from below using only the smallest and largest diagonal entries and the smallest off-diagonal entry of \(P\). The bound reaches its maximum \(n\) only on the family \(P_\alpha\) with diagonal \(\alpha\) and uniform off-diagonal entries. A quantum system of dimension \(\sqrt n\) realises \(P_\alpha\) for every \(0\le\alpha\le1/\sqrt n\) when a SIC-POVM exists, so both optimal exclusion (\(\alpha=0\)) and optimal discrimination (\(\alpha=1/\sqrt n\)) show a quadratic gap between classical and quantum dimension, and the discrimination end tolerates the most noise. A four-parameter condition guarantees a quantum realisation in dimension \(\lceil\sqrt n\rceil\), so quantum advantage holds on open regions. Saturation at diagonal \(1/d\) certifies that the measurement is a SIC-POVM, robustly; the same bound gives a dimension witness \(d_Q\ge\sqrt{1+\Gamma}\).

The paper in detail

The setting removes everything that usually produces quantum correlations: no entanglement, no shared randomness, no choice of measurement on Bob's side. What remains is the ability to send overlapping states. A classical message of \(d_C\) symbols reproduces \(P\) only if \(P\) splits into \(d_C\) nonnegative rank-one pieces; a quantum message of dimension \(d_Q\) reproduces it if \(P_{ij}=\mathrm{Tr}(\rho_jM_i)\). Since effects on \(\mathbb C^{d_Q}\) span at most \(d_Q^2\) dimensions, \(\mathrm{rank}\,P\le d_Q^2\) while \(\mathrm{rank}\,P\le d_C\), so the largest possible gap is quadratic.

Theorem 1 lower-bounds the rank. With \(c_{\min}\), \(c_{\max}\) the extreme diagonal entries and \(a_{\min}\) the smallest off-diagonal entry, \[d_C\ge1+\frac{\max\{nc_{\min}-1,\,1-nc_{\max},\,0\}}{1-(n-2)a_{\min}-2\min\{a_{\min},c_{\min}\}}.\] A large diagonal (correlated statistics) or a small diagonal with spread-out errors (anticorrelated statistics) forces many nonzero eigenvalues. The existing literature found advantage mainly with anticorrelations; the inequality shows that correlations work as well.

The bound equals \(n\) exactly on \(P_\alpha=\alpha\mathbb 1+\tfrac{1-\alpha}{n-1}(J-\mathbb 1)\), \(\alpha\neq1/n\), whose nonunit eigenvalues are all \((n\alpha-1)/(n-1)\). A quantum system of dimension \(\sqrt n\) reaches \(\alpha\le1/\sqrt n\), since \(\mathrm{Tr}\,P\le d_Q\). The edges are optimal exclusion, with states orthogonal to the SIC projector of the same label, and optimal discrimination, with the SIC states themselves. Lemma 3 shows that the second is the most noise-tolerant quadratic advantage possible: no \(d\)-dimensional realisation of size \(d^2\) has a smaller-modulus eigenvalue larger than \(1/(d+1)\).

A quantum dimension certificate is needed as well, and Proposition 4 supplies one from four numbers: if the entries stay within an explicit distance of \(1/n\), traceless operators built from a regular simplex give states and a measurement in dimension \(\lceil\sqrt n\rceil\). Theorem 5 goes the other way. Saturating the correlated bound with diagonal \(1/d\) forces pure states, effects proportional to them, and pairwise overlaps \(1/(d+1)\): a SIC-POVM. Because pairwise overlaps do not fix the triple products, only the SIC class is certified; in \(d=3\) inequivalent SICs give the same matrix.

Open questions remain on the side of practice and on the side of geometry. Shared randomness through slow drifts would undermine every bound, and the robust certification is quantitative but loose. The SIC existence problem becomes a numerical question, whether \(P_{1/d}\) with \(n=d^2\) has a \(d\)-dimensional realisation, though nothing here makes that search easier.

Transferable methods

  1. Bounding the rank through the ergodicity coefficient

    Because the classical sets are not convex, there is no separating hyperplane to use. The authors bound the ordinary rank instead, which lower-bounds the nonnegative rank, and they bound it through the eigenvalues of a column-stochastic matrix, which are controlled by how much its columns overlap.

    For a column-stochastic \(P\), the eigenvalue 1 is fixed and all others satisfy \(\lvert\lambda\rvert\le\tau_1(P)\), where \[\tau_1(P)=1-\min_{j\neq k}\sum_i\min\{P_{ij},P_{ik}\}\] is Seneta's ergodicity coefficient. Two columns share at least \(a_{\min}\) in each of the \(n-2\) rows other than \(j,k\), and \(\min\{a_{\min},c_{\min}\}\) in rows \(j\) and \(k\), so \(\tau_1\le1-(n-2)a_{\min}-2\min\{a_{\min},c_{\min}\}\).

    At most \(r-1\) eigenvalues besides 1 are nonzero, where \(r=\mathrm{rank}\,P\). Hence \[\lvert\mathrm{Tr}\,P-1\rvert=\Bigl\lvert\sum_{\lambda\neq1}\lambda\Bigr\rvert\le(r-1)\,\tau_1(P),\] and \(nc_{\min}\le\mathrm{Tr}\,P\le nc_{\max}\) turns this into Theorem 1. For \(P_\alpha\) with \(\alpha>1/n\), \(\tau_1=1-na_{\min}=(n\alpha-1)/(n-1)\) and \(\mathrm{Tr}\,P-1=n\alpha-1\), so the bound gives exactly \(r\ge n\).

    Editorial checks: no violation of Theorem 1 among 20,000 random matrices of size 3–6 and rank 1–6; \(1+\Gamma=n\) and \(\lvert\lambda_{\min}\rvert=\lvert n\alpha-1\rvert/(n-1)\) for \(P_\alpha\) at \(n=4,9\) and several \(\alpha\). For the qubit tetrahedron with states \(\Pi_j\), the matrix has diagonal \(1/2\), off-diagonal \(1/6\), and with states \(\mathbb 1-\Pi_j\) the exclusion matrix again has \(1+\Gamma=4\).

    How to reuse it

    Whenever a resource is bounded by the rank of a stochastic matrix, the ergodicity coefficient turns entrywise information into an eigenvalue bound. Combined with a trace constraint it gives rank bounds that stay valid under small perturbations of the entries.

  2. Gram determinants for optimal noise tolerance and SIC certification

    To show that the SIC strategy is the most robust quadratic advantage, the authors bound the determinant of every quantum-realisable \(d^2\times d^2\) matrix. The factorisation \(P=AB\) in Hilbert–Schmidt coordinates reduces this to two Gram determinants.

    Writing effects and states in an orthonormal basis of Hermitian operators gives \(P=AB\) and \((\det P)^2=\det G^M\det G^\rho\). For \(n=d^2\) states, the Gram matrix \(G_{jk}=\mathrm{Tr}(\sigma_j\sigma_k)\) has largest eigenvalue at least \(n\,\mathrm{Tr}\bar\sigma^2\ge n/d\) and trace at most \(n\), and the AM–GM inequality on the other eigenvalues gives \[\det G\le d\Bigl(\frac{d}{d+1}\Bigr)^{n-1}.\] With \(M_i=t_i\sigma_i\) and \(\sum_it_i=d\), the same steps give \(\lvert\det P\rvert\le(d+1)^{-(n-1)}\), with equality only for SIC states.

    Theorem 5 uses a Cauchy–Schwarz chain: \(\tfrac1d=\mathrm{Tr}(\rho_iM_i)\le\sqrt{\mathrm{Tr}\rho_i^2\,\mathrm{Tr}M_i^2}\le\mathrm{Tr}M_i=\tfrac1d\). Equality throughout forces \(\rho_i\) pure and \(M_i=\rho_i/d\), and the off-diagonal entries then fix \(\mathrm{Tr}(\rho_i\rho_j)=1/(d+1)\).

    Editorial checks: the qubit SIC matrix has \(\det P=1/27=3^{-3}\), attaining the bound; 20,000 random qubit realisations gave at most \(\lvert\det P\rvert=0.0097\). The construction of Proposition 4 (simplex vectors in Gell-Mann coordinates, \(n=5\), \(d=3\)) reproduced 2,000 random matrices satisfying Eq. (8) with valid states and a valid measurement.

    How to reuse it

    Determinant bounds via Gram matrices apply to any bilinear model \(p(i|j)=\langle a_i,b_j\rangle\) with norm constraints. They single out the realisations whose statistics are farthest from losing rank, usually the most symmetric ones, and turn certification into a characterisation of the equality cases.

Source: Theorem 1 and Appendix A (Eqs. (12)–(18)); Lemma 3 and Appendix C (Eqs. (33)–(43)); Theorem 5 and Appendix F; Proposition 4 and Appendix E. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. It turns quantum advantage in the barest prepare-and-measure setting into an inequality with a continuous noise margin. It also certifies SIC-POVMs with \(d^2\) preparations and one fixed measurement, without inputs for Bob, and recasts the open SIC existence problem as whether one explicit matrix has a \(d\)-dimensional quantum realisation.

Limitations. All results assume that preparation and measurement devices share no randomness, including correlated drifts, which is hard to guarantee in practice. SIC certification assumes the Hilbert-space dimension exactly; leakage is handled only perturbatively. The bounds use extremal entries and can be spoiled by a single outlier (relabelling or submatrices help), and the robustness constants in Theorem 6 grow as \(d^3\). The authors report AI use: Gemini found the ergodicity-coefficient bound that closed a gap in Eq. (5); Claude Opus 5.5 proved Proposition 4 almost entirely, Theorem 6 was derived interactively with Claude, and Claude assisted with two figures.

Description based on the full arXiv HTML of v1, read 2026-11-15: the main text, Appendices A–F and the start of Appendix G (Proposition 8 and the proof of Theorem 6 up to Eq. (80)), and the AI statement. Theorem 1 was tested on 20,000 random communication matrices, saturation by \(P_\alpha\) and its eigenvalues for \(n=4,9\), the qubit SIC case against Lemma 3, Lemma 3 on random qubit realisations, and the construction of Proposition 4 on 2,000 random matrices.