Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity

arXiv:2610.21071 · quant-ph, cs.IT, math.IT · Submitted 2026-10-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity".

Mira: The gist The authors introduce a multiplicative semidefinite programming parameter Γ(K) that upper-bounds the asymptotic quantum no-signalling-assisted zero-error capacity ΘNS(K), providing the tightest known bound among semidefinite programs,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So we just talked about how this paper introduces Gamma of K as the tightest multiplicative upper bound for Theta NS of K.

Mira: And they also show that their simulation lower bound, Sigma minus K, is multiplicative and it sits between Theta NS of K and Gamma of K squared.

Kai: This structure allows them to prove that neither S0 NS or its regularized extension holds in general for these quantities.

Lev: That’s a big deal because the paper says this answers an open question about the asymptotic simulation cost S0 NS of K.

Mira: For classical quantum channels, they get some very sharp bounds when you look at things like the effective output dimension r and the minimum rank of the output support projections k.

Kai: They give us these specific inequalities: Theta NS less than or equal to Gamma less than or equal to one plus square root r times Theta NS over two.

Lev: And they also get a bound involving k, where Sigma minus divided by Theta NS is less than or equal to the square of one plus square root r divided by one plus square root k.

Mira: That bound involving k is sharp for every value of k between one and r, so it gives them a specific operational estimate for S0 NS minus C0 NS.

Kai: So what they prove is that the simulation gap can be bounded by two times the logarithm base two of one plus square root r divided by one plus square root k.

Conclusion: Mira: So wrapping up this discussion on "Multiplicative Semidefinite Programming Upper Bounds on Quantum No-Signalling-Assisted Zero-Error Capacity," the core idea is that we found a tight upper bound, Gamma of K, for the capacity Theta NS of K.

Kai: And more importantly, they showed that neither the standard simulation cost nor its regularized version equals these quantities in general cases.

Lev: What this means for us is that we have a concrete way to measure how much classical information you need to simulate a quantum channel exactly without resorting to things that don't hold universally.

Mira: The sharpest result they get is that the simulation gap can be bounded by the term involving r and k, which relates to the dimension of your output space.

Kai: So for someone just listening, it suggests that you can quantify how much extra classical data you might need when trying to perfectly replicate a quantum process using no-signalling correlations.

Xin Li, Yinan Li

Wuhan University

quant-ph, cs.IT, math.IT

Submitted: 2026-10-15

Updated: 2026-10-15

Comments: 23 pages

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist The authors introduce a multiplicative semidefinite programming parameter Γ(K) that upper-bounds the asymptotic quantum no-signalling-assisted zero-error capacity ΘNS(K), providing the

Key concepts

Quantum No-Signalling Correlation (QNS): This refers to a non-local game represented by a bipartite CPTP map. It describes correlations between two parties that are constrained by quantum no-signalling, meaning they cannot communicate faster than classical limits allow, but can still be used to assist communication tasks.
Asymptotic QNS-Assisted Zero-Error Capacity ($\Theta_{\rm NS}(K)$): This is the fundamental limit on the maximum number of classical messages that can be sent without error using a quantum channel assisted by QNS correlations. It is defined as $\lim_{n\to\infty} 1/n \log_2 \Upsilon(K^{\otimes n})$, representing the long-term achievable rate.
Multiplicative Parameter ($\Gamma(K)$): This is a specific semidefinite programming parameter introduced by the authors that exactly multiplies under tensor products. It serves as the tightest known upper bound for $\Theta_{\rm NS}(K)$ among all existing SDP bounds, establishing a crucial relationship between capacity and simulation cost.

Summary

The gist The authors introduce a multiplicative semidefinite programming parameter Γ(K) that upper-bounds the asymptotic quantum no-signalling-assisted zero-error capacity ΘNS(K), providing the tightest known bound among semidefinite programs, and they prove that neither S0,NS(K) nor its regularized extension holds in general > ref:15.

Introduction to QNS Capacity and Bounds

The paper studies zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations > ref:1. A non-local game can be represented by a bipartite CPTP map R: L(Ai ⊗ Bi) → L(Ao ⊗ Bo), which is called a quantum no-signalling correlation > ref:2. The asymptotic QNS-assisted zero-error capacity is given by C0,NS(K) = limn→∞ 1/n log2 Υ(K⊗n), denoted as ΘNS(K) > ref:2. Duan and Winter proved that the maximum number of classical messages that can be transmitted without error in one channel use with QNS assistance depends only on K and equals ⌊Υ(K)⌋, where Υ(K) is given by a semidefinite program > ref:17.

The Multiplicative Upper Bound Γ(K)

The authors introduce the parameter Γ(K), which is exactly multiplicative under tensor products and upper-bounds ΘNS(K) = 2C0,NS(K) > ref:15. They prove that Γ ≤ Σ− ≤ Γ squared > ref:17. This multiplicativity leads to the conclusion that neither S0,NS(K) nor its regularized extension holds in general > ref:15. The tightest upper bound among known general upper bounds on ΘNS given by semidefinite programs is Γ > ref:15.

Relationship between Simulation Cost and Capacity

The paper shows that neither S0,NS(K) = log2 Σ−(K) nor its regularized extension S0,NS(K) = limn→∞ n−1 log2 Σ−(K⊗n) holds in general > ref:15. They establish sharp bounds for classical–quantum channels where the effective output dimension is r and the minimum rank of the output support projections is k > ref:15. Specifically, if r is the effective output dimension, then ΘNS ≤ Γ ≤ (1 + √r)ΘNS/2 and Γ ≤ Σ− ≤ (1 + √r)Γ/2 > ref:15. If k is the minimum rank of the output support projections, then Σ−/ΘNS ≤ [(1+√r)/(1+√k)] squared, and this bound is sharp for every 1 ≤ k ≤ r > ref:15. Thus, they obtain the sharp bound S0,NS−C0,NS ≤ 2 log2 [(1 + √r)/(1 + √k)] > ref:15.

Sharp Bounds for Classical–Quantum Channels

For classical–quantum channels with effective output dimension r and minimum rank k of support projections, they prove the sharp bounds A ≤ Γ ≤ (1 + √r)A/2, Γ ≤ Σ ≤ (1 + √r)Γ/2, and Σ/A ≤ [(1 + √r)/(1 + √k)] squared > ref:15. They also obtain the sharp operational estimate 0 ≤ S0,NS(K) − C0,NS(K) ≤ 2 log2 [(1 + √r)/(1 + √k)] > ref:15.

Dimension-Dependent Bounds and Extremal Families

The paper derives dimension-dependent bounds between A and Γ, proving A(K) ≤ Γ(K) ≤ crA(K), where cr:= (1 + √r)/2 > ref:15. Furthermore, for every pair 1 ≤ k ≤ r, there exists a classical–quantum Kraus operator space attaining equality in both dimension-dependent bounds in (35) > ref:15. The extremal family for this bound is an r-Dimensional Pure-State Extremal Family where Γ = √r and Σ = √r(1 + √r)/2 > ref:16.

Comparison with the Quantum Lovasz Number

The authors establish that Γ(K) and Σ−(K) are incomparable with the quantum Lovasz number ϑe(S(K)) [10] > ref:22. They exhibit examples yielding strict inequalities in both directions relative to ϑe, showing that Γ = Σ− ref:43.

Conclusion on Simulation Gap

For classical–quantum Kraus operator spaces, since Σ = Σ− in this setting, Theorem 10 gives that S0,NS(K) = log2 Σ(K) > ref:18. This leads to the corollary that for every 1 ≤ k ≤ r, 0 ≤ S0,NS(K) − C0,NS(K) ≤ 2 log2 [1 + √r/(1 + √k)] > ref:23. The construction in Proposition 21 attains the upper bound on the operational gap > ref:23.

Summary of Key Findings

The paper establishes a hierarchy of bounds: Υ(b K) ≤ ΘNS(K) ≤ Γ(K) ≤ Σ−(K) ≤ Γ squared > ref:13. It proves that Γ and Σ− are exactly multiplicative under tensor products > ref:7, ref:10. The sharp bound for the simulation cost is S0,NS−C0,NS ≤ 2 log2 [(1 + √r)/(1 + √k)] > ref:15. Finally, they show that the gap between the asymptotic capacity and the exact simulation cost can be non-zero for certain channel families > ref:18.

--- Page 26 ---

The authors used ChatGPT (OpenAI) in developing the mathematical arguments and proofs in IV-E and V-B–V-G > ref:23. The relevant material was reviewed and verified by the authors through multiple rounds of manual checking > ref:23. The authors take full responsibility for the content of this paper > ref:23.

--- Page 18 ---

--- Page 17 ---

The Authors used ChatGPT (OpenAI) in developing the mathematical arguments and proofs in IV-E and V-B–V-G > ref:23. The relevant material was reviewed and verified by the authors through multiple rounds of manual checking > ref:23. The authors take full responsibility for the content of this paper > ref:23.

--- Page 16 ---

--- Page 15 ---

--- Page 14 ---

--- Page 13 ---

--- Page 12 ---

--- Page 11 ---

--- Page 10 ---

Improvements for AI systems

A quantum channel simulation system can achieve zero-error communication with an asymptotic cost bounded by a tight SDP parameter: ΘNS(K) ≤ Γ(K) ≤ Σ−(K) ≤ Γ(K)2. This allows for the design of communication protocols that guarantee exact channel simulation while maintaining zero decoding error, providing a rigorous upper bound on the required classical message alphabet size.
The system can exploit rank-sensitive refinements to achieve sharper bounds: Σ(K) / A(K) ≤ [(1 + √r)/(1 + √k)]2 for every 1 ≤ k ≤ r." This enables the AI to determine the minimum necessary classical resources based on the minimum rank of the output support projections, optimizing communication efficiency for specific channel structures.
The system can distinguish between asymptotic capacity and simulation cost: S0,NS(K) − C0,NS(K) ≤ 2 log2 [1 + √r / 1 + √k]. This allows the AI to quantify the gap between theoretical maximum achievable rate and the actual practical cost of exact channel implementation.
The system can utilize a specific qubit family for capacity estimation: S0,NS(Kη) = 2 log2 (q + h) for a specific Kraus operator space Kη." This provides an explicit formula for the asymptotic simulation cost in certain quantum settings, allowing the AI to compute this cost directly rather than relying on general regularized extensions.
The system can perform exact simulation with guaranteed multiplicative costs: Γ(K1 ⊗ K2) = Γ(K1)Γ(K2). This ensures that if a channel is composed of tensor products of simpler channels, the required classical resources scale multiplicatively, which is crucial for scaling simulations across complex quantum circuits.

Sources

Activated zero-error classical communication over quantum channels assisted with quantum no-signalling correlations