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

AI summary

Overview

Research area: Quantum information theory — specifically zero-error quantum Shannon theory, combined with convex optimization (semidefinite programming) and noncommutative graph theory.

Technical level: Advanced. The paper assumes fluency in completely positive maps, Choi operators, Kraus representations, operator systems, and semidefinite programming duality.

Scope (one sentence): The paper introduces and analyzes a new semidefinite-programming parameter Γ(K) that is exactly multiplicative under tensor products and serves as the tightest known SDP upper bound on the quantum no-signalling-assisted zero-error capacity of a quantum channel, then derives sharp bounds for classical–quantum channels.

The paper is purely theoretical. It reports no numerical experiments, no benchmark comparisons on real data, and no dataset sizes.

What This Paper Is About

In zero-error communication, a sender wants to transmit classical messages through a noisy quantum channel with zero probability of error, possibly using shared quantum no-signalling (QNS) correlations. The maximum number of messages per channel use is captured by a semidefinite program (SDP), but the true asymptotic rate over many channel uses — the QNS-assisted zero-error capacity C₀,NS(K), written exponentially as Θ_NS(K) = 2^{C₀,NS(K)} — is a regularized quantity with no known single-letter formula. The paper's goal is to construct a computable, single-letter upper bound on Θ_NS that is exactly multiplicative under tensor products, mirroring the role the Lovász number ϑ plays in classical zero-error information theory.

Key Contributions

1. A new multiplicative SDP bound Γ(K). The authors define Γ(K) for any Kraus operator space K, derive its dual program, prove strong duality, and prove that Γ(K₁ ⊗ K₂) = Γ(K₁)Γ(K₂) exactly. They establish that Γ upper-bounds Θ_NS and, among known SDP upper bounds on Θ_NS, is the tightest. They also prove Γ(K) ≤ Σ(K), where Σ is the semidefinite covering number of Duan and Winter.

2. Exact multiplicativity of Σ⁻ and a two-sided chain of bounds. They prove that the simulation lower bound Σ⁻(K) of Wang and Duan is exactly multiplicative (strengthening its previously known supermultiplicativity), and that Θ_NS(K) ≤ Γ(K) ≤ Σ⁻(K) ≤ Γ(K)². Consequently Σ⁻ is also a multiplicative upper bound on Θ_NS.

3. A negative answer to an open question on asymptotic simulation cost. Using the multiplicativity results, they show that the asymptotic QNS-assisted exact simulation cost S₀,NS(K) is not in general equal to log₂ Σ⁻(K), nor to its regularized extension; they construct a family of Kraus operator spaces for which log₂ Σ⁻(K) < S₀,NS(K).

4. Sharp bounds for classical–quantum channels. In terms of the effective output dimension r and the minimum rank k of the output support projections, they prove A(K) ≤ Γ(K) ≤ (1+√r)A(K)/2, Γ(K) ≤ Σ(K) ≤ (1+√r)Γ(K)/2, the rank-sensitive bound Σ(K)/A(K) ≤ [(1+√r)/(1+√k)]², and the operational estimate 0 ≤ S₀,NS(K) − C₀,NS(K) ≤ 2 log₂[(1+√r)/(1+√k)].

Main Findings

• Γ is exactly multiplicative: For any two Kraus operator spaces K₁ and K₂, Γ(K₁ ⊗ K₂) = Γ(K₁)Γ(K₂), so regularizing Γ yields nothing new: the single-letter value already equals the asymptotic value of the bound.

• Complete chain of general bounds: The paper establishes Υ̂(K) ≤ Θ_NS(K) ≤ Γ(K) ≤ Σ⁻(K) ≤ Γ(K)² together with Γ(K) ≤ Σ(K), where Υ̂ is the activated one-shot quantity of Duan and Wang and Σ is the semidefinite covering number.

• Γ is the tightest known SDP upper bound: Among upper bounds on Θ_NS given by semidefinite programs, Γ is the tightest, and it dominates the previously known covering-number bound since Γ(K) ≤ Σ(K) for every Kraus operator space K.

• Σ⁻ is exactly multiplicative: The regularization of Σ⁻ does not improve the simulation lower bound log₂ Σ⁻(K), because Σ⁻(K^{⊗n}) = Σ⁻(K)ⁿ.

• Separation of simulation cost from the lower bound: A constructed family of Kraus operator spaces satisfies log₂ Σ⁻(K) < S₀,NS(K), so log₂ Σ⁻(K) is strictly weaker than the asymptotic simulation cost in general.

• Quadratic relation between Σ⁻ and Γ: Γ(K) ≤ Σ⁻(K) ≤ Γ(K)², meaning the multiplicative lower/upper bound pair never differs by more than a square.

• Classical–quantum sandwich bounds: With r the effective output dimension, Θ_NS ≤ Γ ≤ (1+√r)Θ_NS/2 and Γ ≤ Σ⁻ ≤ (1+√r)Γ/2; since Θ_NS = A(K), Σ⁻ = Σ(K), and Υ̂ = A(K) for classical–quantum channels (results from prior work), these give Γ ≤ Σ ≤ (1+√r)Γ/2 and A ≤ Γ ≤ (1+√r)A/2.

• Sharpness of the rank-sensitive bound: Σ⁻/Θ_NS ≤ [(1+√r)/(1+√k)]², and this bound is attained for every 1 ≤ k ≤ r. An explicit r-dimensional pure-state family attains equality in both upper bounds and hence achieves Σ/A = [(1+√r)/2]², while also separating Θ_NS, Γ, and Σ from one another.

• Operational consequence: The gap between asymptotic simulation cost and asymptotic capacity is bounded by S₀,NS − C₀,NS ≤ 2 log₂[(1+√r)/(1+√k)], a sharp single-letter estimate for classical–quantum channels.

• Relation to entanglement assistance: Prior work's inequality Θ_*(S(K)) ≤ Θ_NS(K) is recalled, placing the QNS-assisted capacity above the entanglement-assisted capacity of the associated noncommutative graph.

Methodology in Plain English

The authors work entirely at the level of the channel's Kraus operator space K and its Choi support projection P. The key technical obstacle is that the existing activated SDP formulation Υ̂ contains a constraint of the form QVQ ⪯ 0 (with Q = I − P), and such constraints are not preserved when two channels are tensored together. The authors replace this with two tensor-stable conditions: a support condition PX = X, which forces QVQ = 0, and a 2×2 block positive-semidefinite constraint involving auxiliary operators T₀ and T₁, which enforces the operator inequality V ⪯ I ⊗ T. To keep the objective from depending on an arbitrary split between T₀ and T₁, they show the optimum can be taken with Tr T₀ = Tr T₁ (a scaling argument), so the objective becomes ½Tr(T₀ + T₁).

They then derive the dual program and verify strong duality, and prove exact multiplicativity by explicitly tensoring primal-feasible solutions (using a reordering unitary Π to align the A and B subsystems) and, separately, dual-feasible solutions. The upper-bound property is proved by mapping any feasible point of Γ back to a feasible point of the dual of Υ̂. For the classical–quantum case, they reduce everything to the projections P_x = supp(ρ_x) and the packing number A(K), then analyze how the parameters r and k control the ratios between A, Γ, and Σ, and construct explicit pure-state families that saturate the bounds.

Why This Matters

Impact on research: The work resolves a stated open question about the asymptotic simulation cost S₀,NS(K) and supplies the first exactly multiplicative SDP upper bound on the QNS-assisted zero-error capacity that is tightest among known SDP bounds. Exact multiplicativity is precisely the property that makes a bound single-letter and computationally meaningful for asymptotic rates, so Γ gives a principled answer to the quantum analogue of Shannon's classical upper-bound problem. The sharp classical–quantum analysis also quantifies, for the first time in this framework, how far the simulation cost can exceed the communication capacity in terms of simple structural parameters (r and k).

Potential real-world applications (the paper reports no applied or numerical studies):

• Benchmarking and certifying the zero-error capability of physically realizable quantum communication links, where numerical SDP solvers could evaluate Γ.
• Design and analysis of quantum network architectures in which shared non-signalling correlations are an idealized resource model.
• Bounding the classical side-information or classical control cost needed to simulate a given quantum channel exactly.
• Guiding code design for zero-error quantum communication by identifying channel structures (small r, large k) whose capacity and simulation cost are provably close.

Industry relevance: The results are relevant to quantum networking and quantum communication hardware, where channel simulation costs and zero-error guarantees matter for system-level design. Because QNS correlations are a superset of entanglement-assisted strategies, the bounds also constrain what entanglement-assisted protocols can achieve. The paper does not report any industry deployment, implementation, or experimental validation.

Future Directions

• Determine whether Γ equals Θ_NS in general. The chain Θ_NS ≤ Γ ≤ Σ⁻ ≤ Γ² leaves open how much slack Γ can have for general (non-classical–quantum) channels.
• Characterize when log₂ Σ⁻(K) = S₀,NS(K) holds. The paper gives a family where strict inequality holds; a full characterization of the equality case remains open.
• Extend the sharp r- and k-parametrized analysis beyond classical–quantum channels, and look for multi-letter refinements of the gap S₀,NS − C₀,NS.
• Compare Γ systematically with the quantum Lovász number ϑ̃ and other noncommutative graph parameters (the paper notes that a comparison with the quantum Lovász number is collected in the appendices), with the aim of finding still tighter multiplicative bounds.
• Assess the computational cost of evaluating Γ relative to Σ, Σ⁻, and Υ̂, since tighter bounds are only useful if they remain practically solvable.

Target Audience

This paper is aimed at researchers and graduate students in quantum information theory, quantum Shannon theory, and zero-error information theory, as well as researchers in convex optimization and operator theory who work on noncommutative generalizations of graph parameters. Readers should be comfortable with completely positive trace-preserving maps, Choi–Jamiołkowski representations, Kraus operator spaces, and semidefinite programming duality. It is most valuable to those specifically working on capacities of quantum channels under non-signalling or entanglement assistance, or on single-letter bounds for regularized information quantities.

Authors’ abstract

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 $Θ_{\rm NS}(K)$, where $\log_2Θ_{\rm NS}(K)=C_{0,\rm NS}(K)$ and $C_{0,\rm NS}(K)$ denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on $Θ_{\rm NS}$ given by semidefinite programs, $Γ$ is the tightest. We also prove that the previously introduced simulation lower bound $Σ^{-}(K)$ is exactly multiplicative and satisfies $Θ_{\rm NS}(K)\leqΓ(K)\leqΣ^{-}(K)\leqΓ(K)^2$. Using this multiplicativity, we show that neither $S_{0,\rm NS}(K)=\log_2Σ^{-}(K)$ nor its regularized extension $S_{0,\rm NS}(K)=\lim\nolimits_{n\to\infty}n^{-1}\log_2Σ^{-}(K^{\otimes n})$ holds in general. This answers an open question about the asymptotic simulation cost $S_{0,\rm NS}(K)$. For classical-quantum channels, we obtain sharp bounds. If $r$ is the effective output dimension, then $Θ_{\rm NS}\leqΓ\leq(1+r^{1/2})Θ_{\rm NS}/2$ and $Γ\leqΣ^{-}\leq(1+r^{1/2})Γ/2$. If $k$ is the minimum rank of the output support projections, then $Σ^{-}/Θ_{\rm NS}\leq[(1+r^{1/2})/(1+k^{1/2})]^2$, and this bound is sharp for every $1\leq k\leq r$. Thus, we obtain the sharp bound $S_{0,\rm NS}-C_{0,\rm NS}\leq2\log_2[(1+r^{1/2})/(1+k^{1/2})]$.