Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.21071

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

Xin Li, Yinan Li

quant-phcs.ITSubmitted Oct 15, 2026• Announced Oct 16, 2026• 0 citations
arXivHTMLPDF

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})]$.

AI Summary

The paper studies computable upper bounds on asymptotic quantum no-signalling-assisted zero-error communication capacity and their relation to exact channel simulation. The underlying object is a channel’s Kraus operator space $K$, with $\Theta_{\rm NS}=2^{C_{0,\rm NS}}$. It introduces an SDP parameter $\Gamma$ and proves exact tensor-product multiplicativity, together with $\Theta_{\rm NS}\leq\Gamma\leq\Sigma^-\leq\Gamma^2$ and $\Sigma^-\leq\Sigma$, where $\Sigma$ is the semidefinite covering number. An equivalent minimization formulation also establishes exact multiplicativity of the previously known simulation lower bound $\Sigma^-$. An explicit qubit-channel family disproves the proposed identity $S_{0,\rm NS}=\log_2\Sigma^-$: its simulation cost is computed exactly on every tensor power, while the gap above $\log_2\Sigma^-$ approaches one bit. For classical–quantum channels, where $\Theta_{\rm NS}=A$ and $\Sigma^-=\Sigma$, the paper proves $A\leq\Gamma\leq(1+\sqrt r)A/2$ and $\Gamma\leq\Sigma\leq(1+\sqrt r)\Gamma/2$, with simultaneous equality attained by an explicit pure-state family. More generally, if output supports have minimum rank $k$ and effective dimension $r$, then $\Sigma/A\leq[(1+\sqrt r)/(1+\sqrt k)]^2$. This gives the sharp communication–simulation gap $S_{0,\rm NS}-C_{0,\rm NS}\leq2\log_2[(1+\sqrt r)/(1+\sqrt k)]$, attainable for every $1\leq k\leq r$. Proofs use primal–dual tensor constructions, block positivity, weighted partial-trace Cauchy–Schwarz inequalities, and projection inequalities. The results do not provide a general single-letter capacity or simulation-cost formula; $\Gamma$ can strictly exceed capacity and is incomparable with the quantum Lovász number.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
23 pages

Related papers

No-Signalling-Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number

Runyao Duan, Andreas Winter

We study the one-shot zero-error classical capacity of a quantum channel assisted by quantum no-signalling correlations, and the reverse problem of exact simulation of a prescribed channel by a noiseless classical one. Quantum no-signalling correlations are viewed as two-input and two-output completely positive and trace preserving maps with linear constraints enforcing that the device cannot signal. Both problems lead to simple semidefinite programmes (SDPs) that depend only on the Choi-Kraus (operator) space of the channel. In particular, we show that the zero-error classical simulation cost is precisely the conditional min-entropy of the Choi-Jamiołkowski matrix of the given channel. The zero-error classical capacity is given by a similar-looking but different SDP; the asymptotic zero-error classical capacity is the regularization of this SDP, and in general, we do not know of any simple form. Interestingly, however, for the class of classical-quantum channels, we show that the asymptotic capacity is given by a much simpler SDP, which coincides with a semidefinite generalization of the fractional packing number suggested earlier by Aram Harrow. This finally results in an operational interpretation of the celebrated Lovász ϑ function of a graph as the zero-error classical capacity of the graph assisted by quantum no-signalling correlations, the first information theoretic interpretation of the Lovász number.

arXiv:1409.3426•IEEE Transactions on Information Theory•Dec 11, 2015•70 citations

A semidefinite programming upper bound of quantum capacity

Xin Wang, Runyao Duan

Recently the power of positive partial transpose preserving (PPTp) and no-signalling (NS) codes in quantum communication has been studied. We continue with this line of research and show that the NS/PPTp/NS∩PPTp codes assisted zero-error quantum capacity depends only on the non-commutative bipartite graph of the channel and the one-shot case can be computed efficiently by semidefinite programming (SDP). As an example, the activated PPTp codes assisted zero-error quantum capacity is carefully studied. We then present a general SDP upper bound QΓof quantum capacity and show it is always smaller than or equal to the “Partial transposition bound” introduced by Holevo and Werner, and the inequality could be strict. This upper bound is found to be additive, and thus is an upper bound of the potential PPTp assisted quantum capacity as well. We further demonstrate that QΓis strictly better than several previously known upper bounds for an explicit class of quantum channels. Finally, we show that QΓcan be used to bound the super-activation of quantum capacity.

arXiv:1601.06888•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•37 citations

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

Runyao Duan, Xin Wang

We study the activated quantum no-signalling-assisted zero-error classical capacity by first allowing the assistance from some noiseless forward communication channel and later paying back the cost of the helper. This activated communication model considers the additional forward noiseless channel as a catalyst for communication. First, we show that the one-shot activated capacity can be formulated as a semidefinite program and we derive a number of striking properties of this capacity. We further present a sufficient condition under which a noisy channel can be activated. Second, we show that one-bit noiseless classical communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity, or the semidefinite (or fractional) packing number. Third, we prove that the asymptotic activated capacity cannot exceed the original asymptotic capacity of any quantum channel. We also show that the asymptotic no-signalling-assisted zero-error capacity does not equal to the semidefinite packing number for quantum channels, which differs from the case of classical-quantum channels.

arXiv:1510.05437•Oct 19, 2015•11 citations

Semidefinite Programming Strong Converse Bounds for Classical Capacity

Xin Wang, Wei Dong Xie, Runyao Duan

We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot E-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel.

arXiv:1610.06381•IEEE Transactions on Information Theory•Aug 17, 2017•69 citations

On the one-shot zero-error classical capacity of classical-quantum channels assisted by quantum non-signalling correlations

Ching–Yi Lai, Runyao Duan

Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classicalquantum channels with a confusability graph G, is exactly log ϑ(G), where ϑ(G) is the celebrated Lov´asz theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph G defined by equal-sized cyclotomic cosets, is logbϑ(G)c, which further implies that its asymptotic capacity is log ϑ(G). This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This gives Lov´asz ϑ function another operational meaning in zero-error classical-quantum communication.

arXiv:1504.06046•Quantum Information and Computation•Apr 1, 2017•1 citation

On the quantum no-signalling assisted zero-error classical simulation cost of non-commutative bipartite graphs

Xin Wang, Runyao Duan

Using one channel to simulate another exactly with the aid of quantum no-signalling correlations has been studied recently. The one-shot no-signalling assisted classical zero-error simulation cost of non-commutative bipartite graphs has been formulated as semidefinite programms [Duan and Winter, IEEE Trans. Inf. Theory 62, 891 (2016)]. Before our work, it was unknown whether the one-shot (or asymptotic) no-signalling assisted zero-error classical simulation cost for general non-commutative graphs is multiplicative (resp. additive) or not. In this paper we address these issues and give a general sufficient condition for the multiplicativity of the one-shot simulation cost and the additivity of the asymptotic simulation cost of non-commutative bipartite graphs, which include all known cases such as extremal graphs and classical-quantum graphs. Applying this condition, we exhibit a large class of so-called cheapest-full-rank graphs whose asymptotic zero-error simulation cost is given by the one-shot simulation cost. Finally, we disprove the multiplicativity of one-shot simulation cost by explicitly constructing a special class of qubit-qutrit non-commutative bipartite graphs.

arXiv:1601.06855•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•7 citations
We study zero-error communication and exact simulation of quantum channels assisted by quantum no-signalling correlations. For a channel with Kraus operator space KKK, we introduce a semidefinite programming parameter Γ(K)Γ(K)Γ(K) that is exactly multiplicative under tensor products and upper-bounds ΘNS(K)Θ_{\rm NS}(K)ΘNS​(K), where log⁡2ΘNS(K)=C0,NS(K)\log_2Θ_{\rm NS}(K)=C_{0,\rm NS}(K)log2​ΘNS​(K)=C0,NS​(K) and C0,NS(K)C_{0,\rm NS}(K)C0,NS​(K) denotes the asymptotic quantum no-signalling-assisted zero-error capacity. Among known upper bounds on ΘNSΘ_{\rm NS}ΘNS​ given by semidefinite programs, ΓΓΓ is the tightest. We also prove that the previously introduced simulation lower bound Σ−(K)Σ^{-}(K)Σ−(K) is exactly multiplicative and satisfies ΘNS(K)≤Γ(K)≤Σ−(K)≤Γ(K)2Θ_{\rm NS}(K)\leqΓ(K)\leqΣ^{-}(K)\leqΓ(K)^2ΘNS​(K)≤Γ(K)≤Σ−(K)≤Γ(K)2. Using this multiplicativity, we show that neither S0,NS(K)=log⁡2Σ−(K)S_{0,\rm NS}(K)=\log_2Σ^{-}(K)S0,NS​(K)=log2​Σ−(K) nor its regularized extension S0,NS(K)=lim⁡n→∞n−1log⁡2Σ−(K⊗n)S_{0,\rm NS}(K)=\lim\nolimits_{n\to\infty}n^{-1}\log_2Σ^{-}(K^{\otimes n})S0,NS​(K)=limn→∞​n−1log2​Σ−(K⊗n) holds in general. This answers an open question about the asymptotic simulation cost S0,NS(K)S_{0,\rm NS}(K)S0,NS​(K). For classical-quantum channels, we obtain sharp bounds. If rrr is the effective output dimension, then ΘNS≤Γ≤(1+r1/2)ΘNS/2Θ_{\rm NS}\leqΓ\leq(1+r^{1/2})Θ_{\rm NS}/2ΘNS​≤Γ≤(1+r1/2)ΘNS​/2 and Γ≤Σ−≤(1+r1/2)Γ/2Γ\leqΣ^{-}\leq(1+r^{1/2})Γ/2Γ≤Σ−≤(1+r1/2)Γ/2. If kkk is the minimum rank of the output support projections, then Σ−/ΘNS≤[(1+r1/2)/(1+k1/2)]2Σ^{-}/Θ_{\rm NS}\leq[(1+r^{1/2})/(1+k^{1/2})]^2Σ−/ΘNS​≤[(1+r1/2)/(1+k1/2)]2, and this bound is sharp for every 1≤k≤r1\leq k\leq r1≤k≤r. Thus, we obtain the sharp bound S0,NS−C0,NS≤2log⁡2[(1+r1/2)/(1+k1/2)]S_{0,\rm NS}-C_{0,\rm NS}\leq2\log_2[(1+r^{1/2})/(1+k^{1/2})]S0,NS​−C0,NS​≤2log2​[(1+r1/2)/(1+k1/2)].
The paper studies computable upper bounds on asymptotic quantum no-signalling-assisted zero-error communication capacity and their relation to exact channel simulation. The underlying object is a channel’s Kraus operator space KKK, with ΘNS=2C0,NS\Theta_{\rm NS}=2^{C_{0,\rm NS}}ΘNS​=2C0,NS​.
It introduces an SDP parameter Γ\GammaΓ and proves exact tensor-product multiplicativity, together with ΘNS≤Γ≤Σ−≤Γ2\Theta_{\rm NS}\leq\Gamma\leq\Sigma^-\leq\Gamma^2ΘNS​≤Γ≤Σ−≤Γ2 and Σ−≤Σ\Sigma^-\leq\SigmaΣ−≤Σ, where Σ\SigmaΣ is the semidefinite covering number. An equivalent minimization formulation also establishes exact multiplicativity of the previously known simulation lower bound Σ−\Sigma^-Σ−. An explicit qubit-channel family disproves the proposed identity S0,NS=log⁡2Σ−S_{0,\rm NS}=\log_2\Sigma^-S0,NS​=log2​Σ−: its simulation cost is computed exactly on every tensor power, while the gap above log⁡2Σ−\log_2\Sigma^-log2​Σ− approaches one bit.
For classical–quantum channels, where ΘNS=A\Theta_{\rm NS}=AΘNS​=A and Σ−=Σ\Sigma^-=\SigmaΣ−=Σ, the paper proves A≤Γ≤(1+r)A/2A\leq\Gamma\leq(1+\sqrt r)A/2A≤Γ≤(1+r​)A/2 and Γ≤Σ≤(1+r)Γ/2\Gamma\leq\Sigma\leq(1+\sqrt r)\Gamma/2Γ≤Σ≤(1+r​)Γ/2, with simultaneous equality attained by an explicit pure-state family. More generally, if output supports have minimum rank kkk and effective dimension rrr, then Σ/A≤[(1+r)/(1+k)]2\Sigma/A\leq[(1+\sqrt r)/(1+\sqrt k)]^2Σ/A≤[(1+r​)/(1+k​)]2. This gives the sharp communication–simulation gap S0,NS−C0,NS≤2log⁡2[(1+r)/(1+k)]S_{0,\rm NS}-C_{0,\rm NS}\leq2\log_2[(1+\sqrt r)/(1+\sqrt k)]S0,NS​−C0,NS​≤2log2​[(1+r​)/(1+k​)], attainable for every 1≤k≤r1\leq k\leq r1≤k≤r.
Proofs use primal–dual tensor constructions, block positivity, weighted partial-trace Cauchy–Schwarz inequalities, and projection inequalities. The results do not provide a general single-letter capacity or simulation-cost formula; Γ\GammaΓ can strictly exceed capacity and is incomparable with the quantum Lovász number.
We study the one-shot zero-error classical capacity of a quantum channel assisted by quantum no-signalling correlations, and the reverse problem of exact simulation of a prescribed channel by a noiseless classical one. Quantum no-signalling correlations are viewed as two-input and two-output completely positive and trace preserving maps with linear constraints enforcing that the device cannot signal. Both problems lead to simple semidefinite programmes (SDPs) that depend only on the Choi-Kraus (operator) space of the channel. In particular, we show that the zero-error classical simulation cost is precisely the conditional min-entropy of the Choi-Jamiołkowski matrix of the given channel. The zero-error classical capacity is given by a similar-looking but different SDP; the asymptotic zero-error classical capacity is the regularization of this SDP, and in general, we do not know of any simple form. Interestingly, however, for the class of classical-quantum channels, we show that the asymptotic capacity is given by a much simpler SDP, which coincides with a semidefinite generalization of the fractional packing number suggested earlier by Aram Harrow. This finally results in an operational interpretation of the celebrated Lovász ϑ function of a graph as the zero-error classical capacity of the graph assisted by quantum no-signalling correlations, the first information theoretic interpretation of the Lovász number.
Recently the power of positive partial transpose preserving (PPTp) and no-signalling (NS) codes in quantum communication has been studied. We continue with this line of research and show that the NS/PPTp/NS∩PPTp codes assisted zero-error quantum capacity depends only on the non-commutative bipartite graph of the channel and the one-shot case can be computed efficiently by semidefinite programming (SDP). As an example, the activated PPTp codes assisted zero-error quantum capacity is carefully studied. We then present a general SDP upper bound QΓof quantum capacity and show it is always smaller than or equal to the “Partial transposition bound” introduced by Holevo and Werner, and the inequality could be strict. This upper bound is found to be additive, and thus is an upper bound of the potential PPTp assisted quantum capacity as well. We further demonstrate that QΓis strictly better than several previously known upper bounds for an explicit class of quantum channels. Finally, we show that QΓcan be used to bound the super-activation of quantum capacity.
We study the activated quantum no-signalling-assisted zero-error classical capacity by first allowing the assistance from some noiseless forward communication channel and later paying back the cost of the helper. This activated communication model considers the additional forward noiseless channel as a catalyst for communication. First, we show that the one-shot activated capacity can be formulated as a semidefinite program and we derive a number of striking properties of this capacity. We further present a sufficient condition under which a noisy channel can be activated. Second, we show that one-bit noiseless classical communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity, or the semidefinite (or fractional) packing number. Third, we prove that the asymptotic activated capacity cannot exceed the original asymptotic capacity of any quantum channel. We also show that the asymptotic no-signalling-assisted zero-error capacity does not equal to the semidefinite packing number for quantum channels, which differs from the case of classical-quantum channels.
We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot E-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel.
Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classicalquantum channels with a confusability graph G, is exactly log ϑ(G), where ϑ(G) is the celebrated Lov´asz theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph G defined by equal-sized cyclotomic cosets, is logbϑ(G)c, which further implies that its asymptotic capacity is log ϑ(G). This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This gives Lov´asz ϑ function another operational meaning in zero-error classical-quantum communication.
Using one channel to simulate another exactly with the aid of quantum no-signalling correlations has been studied recently. The one-shot no-signalling assisted classical zero-error simulation cost of non-commutative bipartite graphs has been formulated as semidefinite programms [Duan and Winter, IEEE Trans. Inf. Theory 62, 891 (2016)]. Before our work, it was unknown whether the one-shot (or asymptotic) no-signalling assisted zero-error classical simulation cost for general non-commutative graphs is multiplicative (resp. additive) or not. In this paper we address these issues and give a general sufficient condition for the multiplicativity of the one-shot simulation cost and the additivity of the asymptotic simulation cost of non-commutative bipartite graphs, which include all known cases such as extremal graphs and classical-quantum graphs. Applying this condition, we exhibit a large class of so-called cheapest-full-rank graphs whose asymptotic zero-error simulation cost is given by the one-shot simulation cost. Finally, we disprove the multiplicativity of one-shot simulation cost by explicitly constructing a special class of qubit-qutrit non-commutative bipartite graphs.