Activated zero-error classical communication over quantum channels assisted with
quantum no-signalling correlations
Runyao Duan1,2 and Xin Wang1
1

Centre for Quantum Software and Information, Faculty of Engineering and Information Technologies,

arXiv:1510.05437v2 [quant-ph] 18 Dec 2017

University of Technology Sydney, Australia
2

UTS-AMSS Joint Research Laboratory for Quantum Computation and Quantum Information Processing,
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, China
December 19, 2017

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 find 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.

1 Introduction
A fundamental problem of information theory is to determine the capacity of a communication channel, which describes the capability of the channel for delivering information
from the sender to the receiver. Shannon first discussed this problem in the zero-error
setting and described the zero-error capacity of a channel as the maximum rate at which
it can be used to transmit information perfectly [1]. It is well-known that the Shannon
zero-error capacity is extremely difficult to compute even for very simple classical channels. Nevertheless, this capacity is upper bounded by the Lovász ϑ function [2] which is
efficiently computable by semidefinite programming [3].
Recently the zero-error information theory has been studied in the quantum setting
and many interesting phenomena were observed. For instance, it was shown that shared
entanglement could sometimes improve the zero-error capacity of a classical channel [4, 5],
Runyao Duan: runyao.duan@uts.edu.au, http://www.uts.edu.au/staff/runyao.duan
Xin Wang: xin.wang-8@student.uts.edu.au, http://xinwang.online

1

and the entanglement-assisted zero-error channel coding was studied in [6–8]. Furthermore,
both the zero-error classical and quantum capacities can be super-activated [9–12]. Another
notable fact is that the entanglement-assisted zero-error capacity of a classical channel is
also upper-bounded by the Lovász ϑ function [13, 14], and this result can be generalized
to quantum setting by using a quantum version of Lovász ϑ function [14]. Recently the
separation between the quantum Lovász ϑ function and entanglement-assisted zero-error
capacity of quantum channels was shown in [15], while the case of classical channels remains
unknown.
As more general resources, the no-signaling (NS) correlations have been considered to
assist the zero-error communication in [20, 21], respectively. The no-signalling correlations
arise in the research of the relativistic causality of quantum operations [16–19]. Cubitt
et al. [20] first introduced classical no-signalling correlations into the zero-error classical
communication. One of us and Winter [21] further introduced quantum no-signalling
correlations into the zero-error communication problem. They formulated the one-shot
capacity as a semidefinite program (SDP) which depends only on the non-commutative
bipartite graph of the given channel (an operator space that is given by the linear span
of the Choi-Kraus operators of the channel). Furthermore, Duan, Severini, and Winter
studied the zero-error communication via quantum channel assisted by unlimited noiseless
feedback and showed the induced capacity also depends only on the non-commutative
bipartite graph [32].
In this paper, we further develop the theory of quantum NS-assisted communication
by introducing the activated communication model. The model is introduced in Section 3
and it considers the additional forward noiseless channel as a catalyst for communication.
For a quantum channel N , we can “borrow” a noiseless classical channel I, then we can
use N ⊗ I to transmit information. After the communication finishes we “pay back” the
capacity of I. This kind of communication method was suggested in [31], and was highly
relevant to the notion of potential capacity recently studied by Winter and Yang [33]. We
further show that the one-shot activated zero-error capacity can also be formulated as an
SDP. In Section 4, we show a striking result that one bit can even fully activate any cq
channel to achieve its asymptotic NS-assisted zero-error capacity (or the fractional packing
number). In Section 5, we further show that there is no activation in the asymptotic regime
and the one-shot activated capacity is better than the super-dense coding bound in [21].

2 Zero-error communication over quantum channels
A quantum channel NA0 →B is a completely positive (CP) and trace-preserving (TP) linear
map from operators on a finite-dimensional Hilbert space A0 to operators on a finiteP
dimensional Hilbert space B. The Choi-Jamiołkowski matrix of N is JN = ij |iihj|A ⊗
N (|iihj|A0 ) = (idA ⊗ N )|ΦihΦ|, where A and A0 are isomorphic Hilbert spaces with reP
spective orthonormal basis {|iiA } and {|jiA0 }, |Φi = i |iiA |iiA0 , and idA is the identity
map.
In the communication task, Alice wants to send the classical messages to Bob using
the composite channel MA→B 0 = ΠAB→A0 B 0 ◦ NA0 →B , where Π is a quantum bipartite
operation that generalizes the usual encoding scheme E and decoding scheme D (see Figure. 1). We say such Π is an NS-assisted code if it can be implemented by local operations
with quantum no-signalling correlations. Here, the no-signalling constraint means that
Alice and Bob cannot use the bipartite operation Π to communicate classical information.
The NS-assisted codes have also been applied to study the ordinary classical and quantum
communication over quantum channels (e.g., [21–30]).
2

B0

A

E

f
N

D

Π

N

A0

B

Figure 1: General code scheme

We denote M0,NS (N ) as the maximum number of bits can be transmitted perfectly
over a single use of quantum channel N with NS-assisted codes, i.e.,
M0,NS (N ) := sup{log ` : Π ◦ N = I` , Π is an NS-assisted code},

(1)

where I` (ρ) = `−1
i=0 Tr(ρ|iihi|)|iihi| is the classical noiseless channel. Also, throughout this
paper, log denotes the binary logarithm log2 .
P
As showed in [21], for a channel N (ρ) = k Ek ρEk† , the one-shot NS-assisted zero-error
M0,NS (N ) only depends on the non-commutative bipartite graph K of the channel, i.e.,
P

M0,NS (N ) = M0,NS (K),

(2)

where K = span{Ek } is the linear span of the Choi-Kraus operators of the channel. For
a quantum channel N with non-commutative bipartite graph K, the one-shot NS-assisted
zero-error capacity is gievn by [21]
M0,NS (N ) = M0,NS (K) = log Υ(K),

(3)

where Υ(K) is given by the following SDP:
Υ(K) = max Tr SA
s.t. 0 ≤ UAB ≤ SA ⊗ 1B ,
TrA UAB = 1B ,

(4)

Tr PAB (SA ⊗ 1B − UAB ) = 0.
Here, PAB denotes the projection onto the support of the Choi-Jamiołkowski matrix of N ,
which is uniquely determined by the non-commutative bipartite graph K. Due to this fact,
we will not distinguish between the notations Υ(N ) and Υ(K) in the rest of this paper.
Then by the regularization, the NS-assisted zero-error capacity is

1
log Υ K ⊗n .
n≥1 n

C0,NS (N ) = sup

(5)

The sup in Eq. (5) can be replaced by lim based on the lemma about existence of limits
in [34].

3 One-shot activated zero-error communication
3.1 Activated one-shot zero-error capacity
The model of activated communication is described as follows. For a quantum channel N
assisted by NS codes, we can first borrow a noiseless classical channel I` whose capacity is
3

log `, then we can use N ⊗ I` coherently to transmit classical messages. After the communication finishes, we just pay back the capacity of I` (see Figure 2.) The communication
model follows the idea of potential capacities of quantum channels introduced by Winter
and Yang [33].
I`
m ∈ {1, . . . , M }

E

D

m̂ ∈ {1, . . . , M }

N
Figure 2: Activated classical communication.

Definition 1 For a quantum channel N with non-commutative bipartite graph K, the
one-shot activated no-signalling assisted zero-error classical capacity is defined as the following:
Ma0,NS (N ) = Ma0,NS (K) := sup[M0,NS (K ⊗ ∆` ) − log `],
(6)
`≥1

where ∆` is the non-commutative graph of the noiseless channel I` (ρ) =

P`−1
i=0

Tr(ρ|iihi|)|iihi|.

Definition 2 For a quantum channel N with non-commutative bipartite graph K, the
asymptotic activated no-signalling zero-error classical capacity is given the following regularization:

1
a
a
C0,NS
(N ) = C0,NS
(K) := sup Ma0,NS K ⊗n .
(7)
n≥1 n
To provide a feasible formulation of the activated capacity Ma0,NS (N ), let us frsit
introduce a slightly revised SDP of Υ(K) as follows,
b
Υ(K)
= max Tr SA

s.t. 0 ≤ UAB ≤ SA ⊗ 1B ,
TrA UAB ≤ 1B ,

(8)

Tr PAB (SA ⊗ 1B − UAB ) = 0.
b
The only difference between Υ(K)
and Υ(K) is that now TrA UAB is only required to be
less than or equal to 1B , and an equality is not necessary. However, we will see that such
b
a small revision is of crucial importance. The dual SDP of Υ(K)
is given by
b
Υ(K)
= min Tr TB

s.t. VAB ≤ 1A ⊗ TB ,

TrB VAB ≥ 1A , T ≥ 0,

(9)

(1 − P )AB VAB (1 − P )AB ≤ 0.
Note that by strong duality, the values of both the primal and the dual SDPs coincide.
Now we are ready to present the main result.
Theorem 3 For any quantum channel N with non-commutative bipartite graph K,
b
Ma0,NS (N ) = log Υ(K).

4

(10)

Proof The intuition of this theorem is that the additional noiseless channel may play a
role as a catalyst during the communication task.
To prove the achievable part, it’s important to observe that the additional noiseless
channel indeed provides a larger solution space of Υ(K ⊗ ∆` ). Let us first consider the
b
case ` = 2 and assume that the optimal feasible solution of Υ(K)
is {SA , UAB }. Let us
choose
SAA0 = SA ⊗ (|0ih0| + |1ih1|)A0

(11)

and
UAA0 BB 0 =UAB ⊗ (|00ih00| + |11ih11|)A0 B 0 + ŪAB ⊗ (|01ih01| + |10ih10|)A0 B 0 ,

(12)

where ŪAB = TrSSAA ⊗ (1B − TrA UAB ).
This construction ensures that
TrAA0 UAA0 BB 0 = TrA ((UAB + ŪAB ) ⊗ 1B 0 ) = 1BB 0 .

(13)

Moreover, we have
SAA0 ⊗ 1BB 0 − UAA0 BB 0 =(SA ⊗ 1B − UAB ) ⊗ (|00ih00| + |11ih11|)A0 B 0
+ (SA ⊗ 1B − ŪAB ) ⊗ (|01ih01| + |10ih10|)A0 B 0 ,

(14)
(15)

which directly means that
SAA0 ⊗ 1BB 0 − UAA0 BB 0 ≥ 0.

(16)

Also, noting that Tr PAB (SA ⊗ 1B − UAB ) = 0 and Tr 1A0 B 0 (|01ih01| + |10ih10|)A0 B 0 = 0,
we have that
Tr(PAB ⊗ 1A0 B 0 )(SAA0 ⊗ 1BB 0 − UAA0 BB 0 ) = 0.
(17)
Therefore, {SAA0 , UAA0 BB 0 } is a feasible solution of Υ(K ⊗ ∆2 ), which means that
sup
`≥2

Υ(K ⊗ ∆2 )
Tr SAA0
Υ(K ⊗ ∆` )
b
≥
≥
= Υ(K).
`
2
2

(18)

b
On the other hand, to prove the converse part, we will use the fact that Υ(K
⊗ ∆` ) =
b
` Υ(K),
which is provided in the following Lemma 4. This fact directly implies that

sup
`≥2

b
Υ(K
⊗ ∆` )
Υ(K ⊗ ∆` )
b
≤ sup
= Υ(K).
`
`
`≥2

(19)

Finally, by Eq. (18) and Eq. (19), we can conclude that
b
Ma0,NS (N ) = Ma0,NS (K) = log Υ(K).

(20)
t
u

b is shown as follows.
A simple but useful property of Υ

Lemma 4 For any non-commutative bipartite graph K, we have
b
b
Υ(K
⊗ ∆` ) = ` Υ(K).

5

b
Proof On one hand, it is evident from the super-multiplicativity that Υ(K
⊗ ∆` ) ≥
b
` Υ(K). On the other hand, note that an optimal solution for SDP (9) for ∆` is given
P
by {1B 0 , `i=1 |iiihii|A0 B 0 }, and we assume that the optimal solution of SDP (9) for K is
{TB , VAB }. It is evident that

VAB ⊗

`
X

|iiihii|A0 B 0 ≤ 1AA0 ⊗ TB ⊗ 1B 0 .

(21)

i=1

Then, it can be checked that {VAB ⊗ `i=1 |iiihii|A0 B 0 , TB ⊗ 1B 0 } is a feasible solution of
b
b
b
SDP(9) for Υ(K
⊗ ∆` ). Therefore,Υ(K
⊗ ∆` ) ≤ Tr TB ⊗ 1B 0 = ` Υ(K).
t
u
Indeed, in the previous proof we have shown the following stronger result:
P

b
Υ(K)
=

Υ(K ⊗ ∆` )
Υ(K ⊗ ∆2 )
=
, ∀ ` ≥ 2.
`
2

3.2 Activation via noisy quantum channels
We further discussion the activation via noisy quantum channels
Proposition 5 Let us consider two quantum channels N1 with non-commutative bipartite
graphs K1 and K2 , respectively. If Υ(K2 ) − 1 ≥ b 1 , then
Υ(K1 )

M0,NS (K1 ⊗ K2 ) − M0,NS (K2 ) ≥ Ma0,NS (K1 ).

(22)

In other words, K2 can activate K1 if K1 is activatable. In particular, this inequality
always holds when Υ(K2 ) ≥ 2.
b
Proof Let us assume that the optimal solution to the SDP (8) of Υ(K
1 ) is {SA , UAB }
while the optimal solution to the SDP (4) of Υ(K2 ) is {SA0 , UA0 B 0 }.
Then we can choose

SAA0 = SA ⊗ SA0 ,

(23)

UAA0 BB 0 = UAB ⊗ UA0 B 0 + ŪAB ⊗ VA0 B 0 ,

(24)

where VA0 B 0 = (SA0 ⊗ 1B 0 − UA0 B 0 )/(Tr SA0 − 1) and ŪAB = SA /Tr SA ⊗ (1B − TrA UAB ).
Furthermore, we have
SAA0 ⊗ 1BB 0 − UAA0 BB 0 = (SA ⊗ 1B − UAB ) ⊗ UA0 B 0 + [(Tr SA0 − 1 −

1
)SA ⊗ 1B ] ⊗ VA0 B 0 .
Tr SA
(25)

Then, one can check that the constucted solutions satisfy
SAA0 ⊗ 1BB 0 − UAA0 BB 0 ≥ 0, TrAA0 UAA0 BB 0 = 1BB 0 ,
(PAB ⊗ PA0 B 0 )(SAA0 ⊗ 1BB 0 − UAA0 BB 0 ) = 0.

(26)
(27)

Therefore, {SAA0 , UAA0 BB 0 } is a feasible solution to the SDP (4) of Υ(K1 ⊗ K2 ), which
means that
b
Υ(K1 ⊗ K2 ) ≥ Υ(K
1 )Υ(K2 ).

(28)

t
u
If we only consider using the channel N to activate itself, we have the following result
from the above proposition.
6

For any quantum channel N with non-commutative bipartite graph K, if Υ(K) ≥
then
Υ(K ⊗ K)
b
≥ Υ(K).
Υ(K)
Note that Υ(K) ≥
from Proposition 5.

√
1+ 5
2

means Υ(K) − 1 −

1
Υ(K)

√
1+ 5
2 ,

(29)

≥ 0. Thus the result follows directly

4 Activated zero-error capacity of classical-quantum channel
A classical-quantum (cq) channel N : i → ρi (1 ≤ i ≤ n) is a CPTP map with classical
inputs {i}ni=1 and quantum outputs {ρi }ni=1 . The non-commutative bipartite graph of a cq
channel is called a cq graph. Given a cq channel N : i → ρi (1 ≤ i ≤ n) with cq graph K,
its one-shot NS-assisted zero-error capacity (quantified as messages) can be simplified to
X

Υ(K) = max

si

i

s.t. 0 ≤ si , 0 ≤ Ri ≤ si (1 − Pi ),

(30)

(si Pi + Ri ) = 1.

X
i

where Pi is the projection onto the support of ρi for 1 ≤ i ≤ n
Moreover, it was shown in [21] that the asymptotic no-signalling assisted zero-error
classical capacity of a cq channel is equal to the semidefinite (fractional) packing number
first suggested by Harrow [21].
Lemma 6 (Theorem 4 in [21]) For any classical-quantum channel N : i → ρi (1 ≤ i ≤ n)
with cq graph K,
C0,NS (N ) = log A(K),
(31)
with
A(K) = max

X

si

i

s.t. 0 ≤ si ,

X

si Pi ≤ 1.

(32)

i

where Pi the projection onto the support of ρi for 1 ≤ i ≤ n.
This result is a classical-quantum generalization of the fact that the fractional packing/covering number [1, 35] of the bipartite graph (induced by the classical channel) equals
to its NS-assisted zero-error capacity [20]. Moreover, Shannon proved that the feedbackassisted zero-error capacity of a classical channel is also given by the fractional packing
number [1].
For any channel N with cq graph K, the one-shot activated capacity Ma0,NS (N ) =
b
log Υ(K)
can be simplied to
b
Υ(K)
= max

X

si

i

s.t. 0 ≤ si , 0 ≤ Ri ≤ si (1 − Pi ),
(si Pi + Ri ) ≤ 1.

X
i

7

(33)

Theorem 7 For any classical-quantum channel N with cq graph K,
a
M0,NS
(N ) = log A(K).

(34)

In other words, for any cq channel, the asymptotic NS-assisted zero-error capacity (or
the semidefinite packing number) can be achieved via activated NS codes in the one-shot
regime, i.e.,
a
a
C0,NS
(N ) = M0,NS
(N ) = log A(K).
(35)
b
Proof First, we will show A(K) ≥ Υ(K).
Suppose that optimal solution of the SDP (33)
b
of Υ(K) is {si , Ri }. Then,
X

si Pi ≤ 1 −

i

X

Ri ≤ 1,

(36)

i

b
which means that {si } is a feasible solution for A(K). So we have A(K) ≥ Υ(K).
Second, let us assume the optimal solution of SDP (32) is {si }, let Ri = 0 for all
i. It is easy to check that {si , Ri } is a feasible solution of SDP (33), which means that
b
A(K) ≤ Υ(K).
Therefore, for any cq graph K, it holds that
b
Υ(K)
= A(K).

(37)
t
u

To see the existence of activation, let us consider an example here.
Example For the simplest possible cq channel N , which has only two inputs and two pure
output states Pi = |ψi ihψi |. Withour loss
√ of generarity, we assume that |ψ0 i = α|0i + β|1i
and |ψ1 i = α|0i − β|1i with α ≥ β = 1 − α2 . In [21], it has been solved that Υ(K) = 1
and A(K) = α12 . Hence, by Theorem 7, we know
b
Υ(K)
=

1
Υ(N ⊗ ∆2 )
= 2 > Υ(K) = 1.
2
α

(38)

Furthermore, we have
a
a
C0,NS
(N ) = M0,NS
(N ) = −2 log α > M0,NS (N ) = 0.

(39)

5 Activated zero-error communication in the asymptotic regime
5.1 Asymptotic zero-error capacity
As we find the activation phenomenon of zero-error communication in the one-shot regime,
it’s natural to wonder whether there exists an activation in the asymptotic regime. In the
following theorem, we prove that the answer is nagetive.
Theorem 8 For any channel N with non-commutative bipartite graph K with positive
zero-error capacity, let n0 be the smallest integer such that Υ(K ⊗n0 ) ≥ 2. Note that n0
always exists and depends only on K. Then for any n ≥ n0 , we have
⊗(n−n0 )
⊗n
b
b
2 ≤ Υ(K
) ≤ Υ(K ⊗n ) ≤ Υ(K
).

(40)

Moreover,
a
C0,NS
(K) = sup log

q
n

b
⊗n ) = lim log
Υ(K
n→∞

n≥1

8

q
n

b
⊗n ) = C
Υ(K
0,NS (K).

(41)

Proof

Eq. (40) is immediatelly from Theorem 5. Then,
lim log

q
n

n→∞

b
⊗n ) = lim log
Υ(K
n→∞

q
n

Υ(K ⊗n ).

(42)

To prove Eq. (41), the technique is based on a lemma about the existence of limits
⊗n ) ≤ 2n log d. On the other hand, since Υ(K)
b
b
in [34]. On one hand, log Υ(K
is super⊗(mn)
⊗m
⊗n
b
b
b
multiplicative, then log Υ(K
) ≥ log Υ(K ) + log Υ(K ). Therefore,
⊗n )
⊗n )
b
b
log Υ(K
log Υ(K
= lim
= C0,NS (K).
n→∞
n
n
n≥1

sup

(43)
t
u

5.2 Lower bound of the activated capacity
We further explore the lower bound for the activated zero-error communication assisted
with NS codes and study the equivalent conditions for a quantum channel to have a positive
capacity. We find that the one-shot activated capacity is always larger than or equal to
the super-dense coding bound in Theorem 25 in [21].
Proposition 9 Let K be a non-commutative bipartite graph with Choi-Jamiołkowski projection PAB , and let QAB = 1AB − PAB be the orthogonal complement of PAB . Let
PB = TrA PAB , then the following are equivalent:
i. C0,NS (K) > 0;
ii. A(K) > 1;
iii. PB < dA 1B ;
iv. TrA QAB is positive definite;
b
v. Ma0,NS (K) > 0 (or Υ(K)
> 1).

As a matter of fact, we have
C0,NS (N ) ≥ Ma0,NS (N ) ≥ log

dA
.
k TrA PAB k∞

(44)

Proof In [21], i) , ii), iii) and iv) are proved to be equivalent. We focus on v) here.
On one hand, it is easy from v) to i) by Theorem 8.
On the other hand, to prove i) to v), it is equivalent to prove iii) to v). We first
apply the standard super-dense coding protocol to obtain a cq channel Ns with d2A outputs
{(Um ⊗ 1B )JAB (Um ⊗ 1B )† }, and the projections are given by {(Um ⊗ 1B )PAB (Um ⊗ 1B )† },
where Um are generalized Pauli matrices acting on A. Therefore,
A(Ns ) = Pd2

A

m=1 (Um

d2A
⊗ 1B )PAB (Um ⊗ 1B )†

(45)

dA
=
.
k TrA PAB k∞
b
b s ) = A(Ns ). And when TrA PAB < dA 1B strictly holds, the rightHence, Υ(K)
≥ Υ(N
hand side of the above equation is strictly larger than 1. This also means that 1 bit is
enough to activate any one-shot useless non-trival channel.
t
u

9

Example Let us consider the amplitude damping channel Nr (ρ) = 1i=0 Ei ρEi† with
√
√
(46)
E0 = |0ih0| + 1 − r|1ih1|, E1 = r|0ih1|(0 ≤ r ≤ 1).
P

The classical communication capability of this class of channels has been studied in [36–
38], but its classical capacity, zero-error capacity, NS-assisted zero-error capacity are all
unknown. In particular, when r = 3/4, let SA = 38 |0ih0| + 34 |1ih1| and UAB = 14 (|00ih00| +
|00ih11| + |11ih00| + |11ih11|) + 34 |10ih10|, it is not difficult to check that {SA , UAB } is an
feasible solution to the SDP (8) of Υ(Nr ). Hence,
Ma0,NS (Nr ) ≥ log

9
Tr SA
= log > M0,NS (Nr ) = 0.
2
8

(47)

By applying the super-dense coding bound [21], we know C0,NS (Nr ) ≥ log k TrA dPAAB k∞ =
log 10
9 . And it’s clear that the one-shot activated capacity is better than the super-dense
coding bound in [21], i.e.,
Ma0,NS (Nr ) ≥ log

9
10
dA
.
> log
=
8
9
k TrA PAB k∞

(48)

5.3 C0,NS and semidefinite packing nubmber
As the asypmtotic capacity of classical-quantum channel is given by the semidifinite (or
fractional) packing number A(K) in Eq.32, will it hold even for general quantum channels?
In [21], the semidifinite packing number for a general quantum channel was also introduced,
i.e.,
A(N ) = A(K) = max Tr SA
s.t. 0 ≤ SA , TrA PAB (SA ⊗ 1B ) ≤ 1B .

(49)

The difficulty is that we currently do not know efficient methods to calculate the asymptotic no-signalling zero-error capacity.
We will exhibit an example to disprove it.
Proposition 10 There exists a quantum channel N with non-commutative bipartite graph
b
K such that Υ(K)
> A(K). Consequently,
C0,NS (N ) 6= A(N ).

(50)

2
Let K correspond
channel
N (ρ) =
Ei ρEi† with E0 =
i=0q
q
q
q to the quantum
50
1
49
98
√1 |0ih0| + √1 |2ih0|, E1 =
99 |0ih2| +
99 |1ih1| +
99 |2ih2| and E2 =
99 |0ih1|.
2
2
By solving SDPs on Matlab [39, 40], we find that

P

Proof

b
Υ(N
) ≈ 1.1767 > 1.1751 ≥ A(N ).

(51)

C0,NS (N ) ≥ M0,NS (N ) > log A(N ).

(52)

Then, it leads to
t
u

10

6 Discussions
There are many related interesting open problems, of which we highlight a few here. For
example, an interesting problem to characterize the activated entanglement-assisted classical communication over quantum channels. Also, it would be interesting to study the
asymptotic NS-assisted zero-error capacity, which is still difficult to calculate since it can
be larger than the semidefinite (fractional) packing number. Perhaps one could consider
other quantum generalizations of the fractional packing number.
This work was partly supported by the Australian Research Council (Grants No.
DP120103776 and No. FT120100449) and the National Natural Science Foundation of
China (Grant No. 61179030).

References
[1] C E Shannon. The zero error capacity of a noisy channel. IRE Trans. Inf. Theory, 2(3):8–19,
1956. DOI: 10.1109/TIT.1956.1056798.
[2] L Lovasz. On the Shannon capacity of a graph. IEEE Transactions on Information Theory,
25(1):1–7, 1979. DOI: 10.1109/TIT.1979.1055985.
[3] Lieven Vandenberghe and Stephen Boyd. Semidefinite Programming. SIAM Review, 38(1):
49–95, 1996. DOI: 10.1137/1038003.
[4] Toby S Cubitt, Debbie Leung, William Matthews, and Andreas Winter. Improving Zero-Error
Classical Communication with Entanglement. Physical Review Letters, 104(23):230503, 2010.
DOI: 10.1103/PhysRevLett.104.230503.
[5] Debbie Leung, Laura Mancinska, William Matthews, Maris Ozols, and Aidan Roy. Entanglement can increase asymptotic rates of zero-error classical communication over classical channels. Communications in Mathematical Physics, 311(1):97–111, 2012. DOI: 10.1007/s00220012-1451-x.
[6] Teresa Piovesan, Giannicola Scarpa, and Christian Schaffner. Multiparty Zero-Error Classical
Channel Coding With Entanglement IEEE Transactions on Information Theory, 61(2):1113–
1123, 2015. DOI: 10.1109/TIT.2014.2379273.
[7] Jop Briet, Harry Buhrman, Monique Laurent, Teresa Piovesan, and Giannicola Scarpa.
Entanglement-Assisted Zero-Error Source-Channel Coding IEEE Transactions on Information Theory, 61(2):1124–1138, 2015. DOI: 10.1109/TIT.2014.2385080.
[8] Dan Stahlke. Quantum zero-error source-channel coding and non-commutative graph
theory
IEEE Transactions on Information Theory, 62(1):554-577, 2016.
DOI:
10.1109/TIT.2015.2496377.
[9] Toby S Cubitt and Graeme Smith. An Extreme Form of Superactivation for Quantum ZeroError Capacities. IEEE Transactions on Information Theory, 58(3):1953–1961, 2012. DOI:
10.1109/TIT.2011.2178157.
[10] Toby S Cubitt, Jianxin Chen, and Aram W Harrow. Superactivation of the Asymptotic ZeroError Classical Capacity of a Quantum Channel. IEEE Transactions on Information Theory,
57(12):8114–8126, 2011. DOI: 10.1109/TIT.2011.2169109.
[11] Runyao Duan. Super-activation of zero-error capacity of noisy quantum channels. arXiv
preprint arXiv:0906.2527, 2009.
[12] Runyao Duan and Yaoyun Shi. Entanglement between Two Uses of a Noisy Multipartite
Quantum Channel Enables Perfect Transmission of Classical Information, Physical Review
Letters, 101(2):020501, 2008. DOI: 10.1103/PhysRevLett.101.020501.
[13] Salman Beigi. Entanglement-assisted zero-error capacity is upper-bounded by the Lovász
function. Physical Review A, 82(1):010303, 2010. DOI: 10.1103/PhysRevA.82.010303.
[14] Runyao Duan, Simone Severini, and Andreas Winter. Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number. IEEE Transactions
on Information Theory, 59(2):1164–1174, 2013. DOI: 10.1109/TIT.2012.2221677.
[15] Xin Wang and Runyao Duan. Separation between quantum Lovász number and entanglementassisted zero-error classical capacity. arXiv:1608.04508.

11

[16] David Beckman, Daniel Gottesman, M A Nielsen, and John Preskill. Causal and localizable quantum operations. Physical Review A, 64(5):052309, 2001. DOI: 10.1103/PhysRevA.64.052309.
[17] Tilo Eggeling, Dirk Schlingemann, and Reinhard F Werner. Semicausal operations are semilocalizable. Europhysics Letters (EPL), 57(6):782–788, 2002. DOI: 10.1209/epl/i2002-00579-4.
[18] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. Quantum correlations with no causal
order. Nature Communications, 3:1092, 2012. DOI: 10.1038/ncomms2076.
[19] Marco Piani, M. Horodecki, P. Horodecki, and Ryszard Horodecki. Properties of quantum nonsignaling boxes. Physical Review A, 74(1):012305, 2006. DOI: 10.1103/PhysRevA.74.012305.
[20] Toby S Cubitt, Debbie Leung, William Matthews, and Andreas Winter. Zero-Error Channel
Capacity and Simulation Assisted by Non-Local Correlations. IEEE Transactions on Information Theory, 57(8):5509–5523, 2011. DOI: 10.1109/TIT.2011.2159047.
[21] Runyao Duan and Andreas Winter. No-Signalling-Assisted Zero-Error Capacity of Quantum Channels and an Information Theoretic Interpretation of the Lovász Number. IEEE
Transactions on Information Theory, 62(2):891–914, 2016. DOI: 10.1109/TIT.2015.2507979.
[22] Debbie Leung and William Matthews. On the Power of PPT-Preserving and NonSignalling Codes. IEEE Transactions on Information Theory, 61(8):4486–4499, 2015. DOI:
10.1109/TIT.2015.2439953.
[23] William Matthews. A linear program for the finite block length converse of polyanskiy-poorverdú via nonsignaling codes. IEEE Transactions on Information Theory, 58(12):7036–7044,
2012. DOI: 10.1109/TIT.2012.2210695.
[24] Xin Wang, Kun Fang, and Runyao Duan. Semidefinite programming converse bounds for
quantum communication. arXiv:1709.00200.
[25] Ching-Yi Lai and Runyao Duan. On the One-Shot Zero-Error Classical Capacity of ClassicalQuantum Channels Assisted by Quantum Non-signalling Correlations. Quantum Information
& Computation, 17(5):0380–0398, 2017.
[26] Xin Wang and Runyao Duan. On the quantum no-signalling assisted zero-error classical
simulation cost of non-commutative bipartite graphs. Proceedings of 2016 IEEE International
Symposium on Information Theory (ISIT). DOI: 10.1109/ISIT.2016.7541698.
[27] Jeonghoon Park and Soojoon Lee. Quantum nonsignaling-assisted zero-error classical capacity
of qubit channels. Physical Review A, 93(3):032334, 2016. DOI: 10.1103/PhysRevA.93.032334.
[28] Xin Wang,and Runyao Duan. A semidefinite programming upper bound of quantum capacity.
Proceedings of 2016 IEEE International Symposium on Information Theory (ISIT). DOI:
10.1109/ISIT.2016.7541587.
[29] William Matthews. Converses from non-signalling codes and their relationship to converses
from hypothesis testing. International Zurich Seminar on Communications, 2016.
[30] Wei Xie, Xin Wang, and Runyao Duan. Converse bounds for classical communication over
quantum networks. arXiv:1712.05637.
[31] Antonio Acín, Runyao Duan, David E. Roberson, Ana Belén Sainz, and Andreas Winter. A
new property of the Lovász number and duality relations between graph parameters. Discrete
Applied Mathematics, 216:489–501, 2017. DOI: 10.1016/j.dam.2016.04.028.
[32] Runyao Duan, Simone Severini, and Andreas Winter. On zero-error communication via quantum channels in the presence of noiseless feedback. IEEE Transactions on Information Theory,
62(9):5260–5277, 2016. DOI: 10.1109/TIT.2016.2562580.
[33] Andreas Winter and Dong Yang. Potential capacities of quantum channels. IEEE Transactions
on Information Theory, 62(3):1415–1424, 2015. DOI: 10.1109/TIT.2016.2519920.
[34] Howard Barnum, Michael Nielsen, and Benjamin Schumacher. Information transmission
through a noisy quantum channel. Physical Review A, 57(6):4153–4175, 1998. DOI:
10.1103/PhysRevA.57.4153.
[35] E. R. Scheinerman and D. H. Ullman, Fractional graph theory: a rational approach to the
theory of graphs. Vol. 46 of Wiley Series in Discrete Mathematics and Optimization, John
Wiley & Sons, 1997.
[36] Xin Wang and Wei Xie, and Runyao Duan. Semidefinite programming strong converse bounds
for classical capacit. IEEE Transactions on Information Theory (to appear), 2017. DOI:
10.1109/TIT.2017.2741101.

12

[37] Vittorio Giovannetti, and Rosario Fazio. Information-capacity description of spin-chain correlations Physical Review A, 71(3):032314, 2005. DOI: 10.1103/PhysRevA.71.032314.
[38] Fernando G S L Brandao, Jens Eisert, Michal Horodecki, and Dong Yang. Entangled inputs
cannot make imperfect quantum channels perfect. Physical Review Letters, 106(23):230502,
2011. DOI: 10.1103/PhysRevLett.106.230502.
[39] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version
2.1, 2014. http://cvxr.com/cvx.
[40] Nathaniel Johnston, Alessandro Cosentino, and Vincent Russo, QETLAB: A MATLAB toolbox for quantum entanglement, 2015. http://qetlab.com.

13

