arXiv:1801.04572v1 [quant-ph] 14 Jan 2018

Fully Quantum Arbitrarily Varying Channels:
Random Coding Capacity and Capacity Dichotomy
Holger Boche and Christian Deppe

Janis Nötzel

Andreas Winter

Theoretische Informationstechnik
and Nachrichtentechnik
TU München, Germany
{boche, christian.deppe}@tum.de

Theoretische Nachrichtentechnik
TU Dresden, Germany
janis.noetzel@tu-dresden.de

ICREA & Departament de Fı́sica
Grup d’Informació Quàntica
Universitat Autònoma de Barcelona, Spain
andreas.winter@uab.cat

Abstract—We consider a model of communication via a fully
quantum jammer channel with quantum jammer, quantum
sender and quantum receiver, which we dub quantum arbitrarily
varying channel (QAVC). Restricting to finite dimensional user
and jammer systems, we show, using permutation symmetry and
a de Finetti reduction, how the random coding capacity (classical
and quantum) of the QAVC is reduced to the capacity of a
naturally associated compound channel, which is obtained by
restricting the jammer to i.i.d. input states. Furthermore, we
demonstrate that the shared randomness required is at most
logarithmic in the block length, using a random matrix tail
bound. This implies a dichotomy theorem: either the classical
capacity of the QAVC is zero, and then also the quantum capacity
is zero, or each capacity equals its random coding variant.

I. F ULLY

QUANTUM

AVC AND

RANDOM CODES

We consider a simple, fully quantum model of arbitrarily
varying channel (QAVC). Namely, we have three agents, Alice
(sender), Bob (receiver) and Jamie (jammer), each controlling
a quantum system A, B and J, respectively. The channel is
simply a completely positive and trace preserving (cptp) map
N : L(A ⊗ J) −→ L(B), and we assume it to be memoryless
on blocks of length ℓ, i.e. N ⊗ℓ : L(Aℓ ⊗ J ℓ ) −→ L(B ℓ ), with
Aℓ = A ⊗ · · · ⊗ A (ℓ times), etc. However, crucially, neither
Alice’s nor Jamie’s input states need to be tensor product or
even separable states. We shall assume throughout that all
three Hilbert spaces A, B and J have finite dimension, |A|,
|B|, |J| < ∞. The previously introduced AVQC model of
Ahlswede and Blinovsky [5], and more generally Ahlswede
et al. [4], is obtained by channels N that first dephase the
input J in a fixed basis, so that the choices of the jammer
are effectively reduced to basis states |jihj| of J and their
convex combinations. Note that this generalises the classical
AVC, which is simply a channel with input alphabet X ×S and
output alphabet Y, given by transition probabilities N (y|x, s),
and such a channel can always be interpreted as a cptp map.
This model has been considered in [19], [20], however in those
works principally from the point of view that Jamie is helping
Alice and Bob, passively, by providing a suitable input state to
J. Contrary to the classical AVC and the AVQC considered in
[5], [4], where the jammer effectively always selects a tensor
product channel between Alice and Bob, the fact that we allow
general quantum inputs on J ℓ , including entangled states,
permits Jamie to induce non-classical correlations between the

different channel systems. These correlations, as was observed
in [19], [20], are not only highly nontrivial, but can also have a
profound impact on the communication capacity of the channel
between Alice and Bob. In the present context, however, Jamie
is fundamentally an adversary.
Define a (deterministic) classical code for N of block length
ℓ as a collection C = {(ρm , Dm ) : m = 1, . . . , M } of states
ℓ
ρm ∈ S(A
on B n ,
P)Mand POVM elements Dm ≥ 0 acting
1
such that m=1 Dm = 11. Its rate is defined as ℓ log M , the
number of bits encoded per channel use. Its error probability
is defined as the average over uniformly distributed messages
and with respect to a state σ on J ℓ :
Perr (C, σ) :=

M

1 X
Tr N ⊗ℓ (ρm ⊗ σ) (11 − Dm ).
M m=1

For the transmission of quantum information, define a
(deterministic) quantum code for N of block length ℓ as a
pair Q = (E, D) of cptp maps E : L(CL ) −→ L(Aℓ ) and
D : L(B ℓ ) −→ L(CL ). Its rate is 1ℓ log L, the number of
qubits encoded per channel use, and the error is quantified,
with respect to a state σ on J ℓ , as the “infidelity”

Fb(Q, σ) := 1 − Tr (id ⊗ D ◦ Nσ⊗ℓ ◦ E)ΦL ·ΦL ,
P
with the maximally entangled state ΦL = L1 ij |iiihjj|. Here,
we have introduced the channels Nσ : L(A) −→ L(B) defined
by fixing the jammer’s state to σ, Nσ (ρ) := N (ρ ⊗ σ).
Note that we use the language of “deterministic” code,
although in quantum information this is indistinguishable
from stochastic encoders; it is meant to differentiate from
“random” codes, which use shared correlation: A random
classical [quantum] code for N of block length ℓ consists
of a random variable λ with a well-defined distribution and a
family of deterministic codes Cλ [Qλ ]. The error probability
if (Cλ ), always with respect to a state σ on J ℓ , is simply the
expectation over λ, i.e. Eλ Perr (Cλ , σ). The error of the random
quantum code is similarly Eλ Fb (Qλ , σ).
The operational interpretation of the random code model is
that Alice and Bob share knowledge of the random variable
λ, and use Cλ accordingly, but that Jamie is ignorant of it.
This shared randomness is thus a valuable resource, which for
random codes is considered freely available, whose amount,
however, we would like to control at the same time.

The capacities associated to these code concepts are defined
as usual, as the maximum achievable rate as block length goes
to infinity and the error goes to zero:
1
log M s.t. sup Perr (C, σ) → 0,
ℓ
σ
1
Crand (N ) := lim sup log M s.t. sup Eλ Perr (Cλ , σ) → 0,
σ
ℓ→∞ ℓ
1
Qdet (N ) := lim sup log L s.t. sup Fb (Q, σ) → 0,
σ
ℓ→∞ ℓ
1
Qrand (N ) := lim sup log L s.t. sup Eλ Fb (Q, σ) → 0.
σ
ℓ→∞ ℓ
Cdet (N ) := lim sup
ℓ→∞

If in the above error maximisations Jamie is restricted to
tensor power states σ ⊗ℓ , the QAVC model becomes a com⊗ℓ
pound channel: Nσ⊗ℓ
, σ ∈ S(J). Its classical and
⊗ℓ = (Nσ )
quantum capacities are denoted C({Nσ }σ ) and Q({Nσ }σ ),
respectively.
II. R ANDOM CODING CAPACITIES :
FROM QAVC TO ITS COMPOUND CHANNEL
By definition, (see also [7], [8] and [4])
Cdet (N ) ≤ Crand (N ) ≤ C({Nσ }σ ), and
Qdet (N ) ≤ Qrand (N ) ≤ Q({Nσ }σ ).

(1)

Here, we show that for the random capacity, the rightmost
inequalities are identities, by proving bounds in the opposite
direction. For the quantum capacity, this was done in [19,
Appendix A]. To present the argument, define the permutation
operator U π acting on the tensor power Aℓ as permuting the
subsystems, for a permutation π ∈ Sℓ :

U π |α1 i|α2 i · · · |αℓ i = |απ−1 (1) i|απ−1 (2) i · · · |απ−1 (ℓ) i,

which extends uniquely by linearity. This is a unitary representation of the symmetric group, which is defined for any Hilbert
space. The quantum channel obtained by the conjugation
action of U π is denoted Uπ (α) = U π αU π† .
Proposition 1 Let Q = (E, D) be a quantum code for the
compound channel {Nσ }σ∈S(J) at block length ℓ of size L
and with fidelity 1 − ǫ, i.e. for all σ ∈ S(J),


Fb Q, σ ⊗ℓ = 1 − Tr (id ⊗ D ◦ Nσ⊗ℓ ◦ E)ΦL ·ΦL ≤ ǫ.

Then, the random quantum code (Qπ )π∈Sℓ with a uniformly
distributed random permutation π of [ℓ], defined by

Qπ = (Uπ ◦ E, D ◦ Uπ−1 ),

2
has infidelity Eπ Fb Qπ , σ ⊗ℓ ≤ ǫ′ ≤ ǫ(ℓ+1)|J| for the QAVC
N.
Proposition 2 Let C = {(ρm , Dm ) : m = 1, . . . , M } be a
code of block length ℓ for the compound channel {Nσ }σ∈S(J)
with error probability ǫ, i.e. for all σ ∈ S(J),
Perr (C, σ ⊗ℓ ) =

M

1 X
Tr Nσ⊗ℓ (ρm )(11 − Dm ) ≤ ǫ.
M m=1

Then, the random code (Cπ )π∈Sℓ with a uniformly distributed
random permutation π of [ℓ], defined by
Cπ := {(U π ρm U π† , U π Dm U π† ) : m = 1, . . . , M },
2

has error probability ǫ′ ≤ ǫ(ℓ + 1)|J| for the QAVC N .
Proof We only prove Proposition 2, since Proposition 1 has
been argued in [19, Appendix A], with analogous proofs. For
an arbitrary state ζ on J ℓ , the error probability of the random
code (Cπ )π∈Sℓ can be written as
Eπ Perr (Cπ , ζ)
=

M


1 X
Eπ Tr U π† N ⊗ℓ (U π ρm U π† , ζ) U π (11 − Dm )
M m=1

M


1 X
=
Tr N ⊗ℓ ρm , Eπ U π ζU π† (11 − Dm ) ,
M m=1

(2)

where in the last line we have exploited the Sℓ -covariance of
the tensor product channel N ⊗ℓ . The crucial feature of the
last expression is that it shows that the error probability that
the jammer can achieve with ζ is the same as that of the state
1 X π π†
U ζU .
ζ ′ = Eπ U π ζU π† =
ℓ!
π∈Sℓ

This is, by its construction, a permutation-symmetric state,
and we can apply the de Finetti reduction from [13]:
Z
2
2
ζ ′ ≤ (ℓ + 1)|J|
µ(dσ) σ ⊗ℓ =: (ℓ + 1)|J| F,
σ∈S(J)

with a universal probability measure µ on the states of J,
whose detailed structure is given in [13], but which is not
going to be important for us.
Indeed, inserting this into the last line of eq. (2), and using
complete positivity of N , we obtain the upper bound
Eπ Perr (Cπ , ζ) =

M


1 X
Tr N ⊗ℓ ρm , ζ ′ (11 − Dm )
M m=1

M


1 X
Tr N ⊗ℓ ρm , F (11 − Dm )
M m=1
Z
M

2
1 X  ⊗ℓ
= (ℓ + 1)|J|
µ(dσ)
Tr N
ρm , σ ⊗ℓ
M m=1
σ∈S(J)

·(11 − Dm )
Z
2
2
= (ℓ + 1)|J|
µ(dσ)Perr (C, σ ⊗ℓ ) ≤ (ℓ + 1)|J| ǫ,

≤ (ℓ + 1)|J|

2

σ∈S(J)

where in the last step we have used the assumption that for
every jammer state of the form σ ⊗ℓ , the error probability is
bounded by ǫ.
⊓
⊔
To apply this, we need compound channel codes with error
decaying faster than any polynomial. This is no problem,
as there are several constructions giving even exponentially
small error for rates arbitrarily close to the compound channel
capacity, both for classical [7], [21] and quantum codes [8].

Corollary 3 Let N be a QAVC. Its classical random coding
capacity is given by
1
max inf I(X : B ℓ ),
ℓ
ℓ {px ,ρA
σJ
x }
P
P
where I(X : B ℓ ) = S ( x px ωx) − x px S(ωx ) is the
Holevo information of the ensemble px , ωx = N ⊗ℓ (ρx ⊗ σ)
[7], [21].
Similarly, its quantum random coding capacity is


with G = TrAA′ (ΦL ⊗ 11) (id ⊗ E ∗ ◦ N ∗⊗ℓ ◦ D∗ )(11 − ΦL ) .
Obviously, for a random classical code (Cλ ), the expected
error probability is

Crand (N ) = C({Nσ }σ ) = lim

ℓ→∞

Qrand (N ) = Q({Nσ }σ ) = lim

ℓ→∞

1
max inf I(RiB ℓ ),
ℓ |φiRAℓ σJ

ℓ

where I(RiB ℓ ) = S(ΩB )− S(Ω) is the coherent information
ℓ
of the state Ω = (id ⊗ N )(φRA ⊗ σ) [8].
⊓
⊔
III. C APACITY DICHOTOMY:
E LIMINATION OF CORRELATION FROM RANDOM

CODES

For classical AVCs or AVQCs with classical jammer, the
observations of Ahlswede [2] show that the random coding
capacity can always be attained using at most O(log ℓ) bits of
shared randomness. This is done by i.i.d. sampling the shared
random variable λ, thus approximating, for each channel state
σ, Eλ Perr (Cλ , σ) by an empirical mean over n realisations
of λ, except with probability exponentially small in n. Then,
the union bound can be used because the jammer has “only”
exponential in ℓ many choices. On the face of it, this strategy
looks little promising for QAVCs: the jammer’s choices form
a continuum, and even if we realise that we can discretise
S(J ℓ ), any net of states is exponentially large in the dimension
[6], i.e. doubly exponentially large in ℓ, resulting in a naive
bound of O(ℓ) for the shared randomness required. However,
the linearity of the quantum formalism comes to our rescue.
Observation 4 From the point of view of the jammer, the error
probability of a classical code is an observable, Perr (C, σ) =
Tr σE, with a POVM element E = E(C) depending in
a systematic way on the code. Likewise, the infidelity of a
quantum code can be written Fb (Q, σ) = Tr σG for a POVM
element G = G(Q).
Proof
N ∗,

Indeed, using the Heisenberg picture (adjoint map)
M


1 X
Tr N ⊗ℓ (ρm ⊗ σ) (11 − Dm )
M m=1
"
#
M

1 X
= Tr σ
Tr ℓ (ρm ⊗ 11) N ∗⊗ℓ (11 − Dm ) ,
M m=1 A

PM
1
∗⊗ℓ
(11 − Dm ) ,
so that E = M
m=1 TrAℓ (ρm ⊗ 11) N
which is manifestly a POVM element, i.e. 0 ≤ E ≤ 11.
Likewise, for the infidelity,

Fb (Q, σ) = Tr (id ⊗ D ◦ N ⊗ℓ ◦ E)(ΦL ⊗ σ) ·(11 − ΦL )

= Tr(ΦL ⊗ σ)· (id ⊗ E ∗ ◦ N ∗⊗ℓ ◦ D∗ )(11 − ΦL )
Perr (C, σ) =

= Tr σG,

Eλ Perr (Cλ , σ) = Tr σ(Eλ Eλ ),
with the POVM elements Eλ = E(Cλ ) associated to each code
Cλ . Likewise for a random quantum code.
⊓
⊔
For a random classical code (Cλ ), the jammer’s goal is
to maximise the error probability, choosing σ in the worst
possible way. But from the present perspective that the error probability is an observable for Jamie, it is clear that
supσ Eλ Perr (Cλ , σ) is simply the maximum eigenvalue of
E = Eλ Eλ .
We say, following general convention, that a random classical or quantum code (Cλ ) or (Qλ ) has error ǫ (without
reference to any specific state of the jammer) if
sup Eλ Perr (Cλ , σ) ≤ ǫ or sup Eλ Fb(Qλ , σ) ≤ ǫ,
σ

σ

respectively. By the above discussion is equivalent to
Eλ Eλ ≤ ǫ11 or Eλ Gλ ≤ ǫ11,

(3)

in the sense of the operator order. This is an extremely useful
way of characterising that the random code has a given error.
Our goal now is to select a “small” number of λ’s, say
λ1 , . . . , λn , such that
n

1X
Eλ ≤ (ǫ + δ)11,
n ν=1 ν

(4)

ensuring that the random code (Cλν )nν=1 , with uniformly
distributed ν ∈ [n], has error probability ǫ+δ. This is precisely
the situation for which the matrix tail bounds in [3] were
developed. Indeed, quoting [3, Thm. 19], for i.i.d. λν ∼ Pλ ,
( n
)

1X
Pr
Eλν 6≤ (ǫ + δ)11 ≤ |J|ℓ · exp −nD(ǫ + δkǫ) ,
n ν=1

with the binary relative entropy D(ukv) = u ln uv + (1 −
u) ln 1−u
1−v , which can be lower bounded by Pinsker’s inequality, D(ukv) ≥ 2(u − v)2 . Note that both the logarithm (ln)
and the exponential (exp) are understood to base e.
Thus, for n > 2δ12 (ln |J|)ℓ, the right hand probability bound
above is less than 1, so that there exist λ1 , . . . , λn with (4).
The number of bits needed to be shared between Alice and
Bob to achieve this, is log n, which we may choose to be
≤ log ℓ − 2 log δ + log ln |J|, which is not zero, but has zero
rate as ℓ → ∞. Exactly the same argument applies to a random
quantum code (Qλ ). We record this as a quotable statement.
Proposition 5 Let (Cλ : λ ∈ Λ) be a random classical code
of block length ℓ for the QAVC N : A ⊗ J −→ B, with error
probability ǫ. Then for δ > 0, there exist λ1 , . . . , λn ∈ Λ, with
n ≤ 1 + 2δ12 (ln |J|)ℓ, such that the random code (Cλν : ν ∈R
[n]) has error probability ≤ ǫ + δ.

For a random quantum code (Qλ : λ ∈ Λ), with infidelity
ǫ, we similarly have that the random code (Qλν : ν ∈R [n])
has infidelity ≤ ǫ + δ.
⊓
⊔
Remark We have discussed here from the beginning the
version of the capacity with average probability of error
(and arbitrary encodings). Following Ahlswede [2] and the
generalisation of his method above, investing another O(log ℓ)
bits of shared randomness, or loosing O(log ℓ) bits from the
code, we can convert any code with error ǫ into one with
maximum error ≤ 2ǫ. We omit the details of this argument,
as it is exactly as in [2].
Proposition 5 allows us to assess the leftmost inequalities
in the capacity order from eq. (1). Because the randomness
needed is so little, it can be generated by a channel code
loosing no rate. Hence, in a certain sense, they are also identities, except in the somewhat singular case the deterministic
classical capacity vanishes:
Corollary 6 The classical capacity of a QAVC N is either 0
or, if it is positive, it equals the random coding capacity:
(
Crand (N ) if Cdet (N ) > 0,
Cdet (N ) =
0
otherwise.
Similarly, for the quantum capacity:
(
Qrand (N ) if Cdet (N ) > 0,
Qdet (N ) =
0
otherwise.
IV. D ISCUSSION

AND

⊓
⊔

O UTLOOK

We have shown that in a fully quantum jammer channel
model (QAVC), the random coding capacity, for both quantum
and classical transmission, can be reduced to the capacity of a
corresponding compound channel; furthermore, by extension
of the “elimination of correlation” technique, that the shared
randomness required has zero rate, thus implying dichotomy
theorems for the deterministic classical and quantum capacities. Since the derandamisation leaves so little randomness,
we can apply the results also to say something about the identification capacity of QAVCs: Either the ID-capacity vanishes,
or it equals the random coding capacity Crand (N ).
Our work leaves two important open questions: First, to
give necessary and sufficient conditions for vanishing classical
capacity. For classical AVCs this is the co-called “symmetrizability” [17], [14]. But what is the analogue of this condition
for quantum channels?
Second, both parts of our reasoning relied on the finite
dimensionality of the jammer system J. It is not so clear
how to deal with infinite dimension of J, on the other
hand. A priori we have a problem already in Proposition 2,
since the de Finetti reduction has an upper bound depending
on the dimension |J|. However, one can prove the random
coding capacity theorem directly from first principles, without
recourse to de Finetti reductions.

Then, we have the problem again in the derandomisation
step, which requires bounded |J| to apply the matrix tail
bound. We need some kind of quantum net argument to be able
to go to a finite dimensional subspace J ′ < J that somehow
approximates the relevant features of N up to error η and
block length ℓ. Classically, the finiteness of the alphabet of
channel states is irrelevant, as long as we have finite sender
and receiver alphabets. The reason is that for each block length
ℓ we can choose a subset of channel states of size polynomial
in ℓ, corresponding to an ηℓ -net of channels realised by the
jammer, for any fixed η > 0. Indeed, for the QAVC with
classical jammer, which may be described by a state set S, the
following statements are easily obtained by standard methods.
Lemma 7 For every η > 0, there exists a set S ′ ⊂ S of

2|A|2 |B|2
2
cardinality |S ′ | ≤ 10|A|
, with the property that
η
′
′
for every s ∈ S there is an s ∈ S with 21 kNs − Ns′ k⋄ ≤ η,
where the norm is the diamond norm (aka completely bounded
trace norm) on channels [1], [22].
⊓
⊔
By applying this lemma with ηℓ , the “telescoping trick” and
⊗ℓ
for sℓ ∈ S ℓ
the triangle inequality to bound 12 Ns⊗ℓ
ℓ − Nσ ℓ
⋄
ℓ
and σ ℓ ∈ S ′ , we obtain then:
Lemma 8 For every η > 0 and integer ℓ, there exists a subset

2|A|2 |B|2
2
ℓ
S ′ ⊂ S of cardinality |S ′ | ≤ 10|A|
, such that
η
sup Eλ Perr (C, σ ℓ ) ≤ sup Eλ Perr (C, sℓ )

σℓ ∈S ′ℓ

sℓ ∈S ℓ

≤ sup Eλ Perr (C, σ ℓ )
σℓ ∈S ′ℓ

for any random code (Cλ : λ ∈ Λ). Similar for the infidelity
of random quantum codes.
⊓
⊔
Since we need to entangle both the A’s and the J’s, it seems
that the most natural approach is to answer the following
question.
Question 9 Let N : L(A ⊗ J) −→ L(B) be a cptp map with
finite dimensional A and B, and η > 0. Is it possible to find a
subspace J ′ ⊂ J of dimension bounded by some polynomial
in η −1 , with the following property?
For every Hilbert space K and state σ on J ⊗ K,
there exists another state σ ′ on J ′ ⊗ K such that
1
′
2 kNσ − Nσ k⋄ ≤ η.
Here, Nσ and Nσ′ are channels from A to B ⊗ K, defined by
inserting the respective state into the jammer register:
Nσ (ρ) := (N ⊗ idK )(ρ ⊗ σ), Nσ′ (ρ) := (N ⊗ idK )(ρ ⊗ σ ′ ).
We can reduce this to the more elementary question of
approximating the output of the “Choi channel” Γ : L(J) →
′
L(C), with C = A⊗B, defined by Γ(σ) = (idA ⊗N )(ΦAA ⊗
σ), mapping each σ to the Choi state of the channel Nσ :
Namely, the question is whether for every Hilbert space K

and state σ on J ⊗ K, does there exist a state σ ′ on J ′ ⊗ K
1
such that k(Γ ⊗ id)(σ − σ ′ )k1 ≤ ηe := η/|A|2 ?
2
We now show that a positive answer to Question 9, with
deviation ηℓ , could be used to replace the ℓ environments of
N ⊗ℓ in ℓ steps each by a finite dimensional approximation. In
this way, we would be able to find, for every state σ on J ℓ ,
ℓ
another state σ ′ on J ′ , with


1
(5)
N ⊗ℓ σ − N ⊗ℓ σ′ ⋄ ≤ η.
2
Proof
Set σ (0) := σ; we shall define a sequence of
⊗i
approximants σ (i) on J ′ ⊗ J ℓ−i (i = 1, . . . , ℓ), as follows:
To obtain σ (1) , we apply Question 9 with K = J ⊗ℓ−1 (the
last ℓ − 1 of the J-systems) to obtain
1
η
[1]
[1]
Nσ(0) − Nσ(1) ≤ ,
2
ℓ
⋄
where the notation N [i] = id⊗i−1 ⊗ N ⊗ id⊗ℓ−i indicates
application of the channel to the i-th system in J ℓ . Proceeding
inductively, assume that we already have constructed a state
⊗i−1
σ (i−1) on J ′
⊗ J ⊗ℓ−i+1 , Question 9 applied to K =
⊗i−1
′
⊗ℓ−i
J
⊗J
(i.e. all the J ′ systems and the last ℓ − i of
the J’s) gives us a state σ (i+1) on J ′ ⊗i ⊗ J ⊗ℓ−i such that
1
η
[i]
[i]
Nσ(i−1) − Nσ(i) ≤ .
2
ℓ
⋄
Since the diamond norm is contractive under composition
with cptp maps, we obtain for all i = 1, . . . , ℓ that


1
η
N ⊗ℓ σ(i−1) − N ⊗ℓ σ(i) ⋄ ≤ ,
2
ℓ
and via the triangle inequality we arrive at eq. (5), by letting
⊓
⊔
σ ′ := σ (ℓ) and recalling σ = σ (0) .
This would mean that any behaviour that the jammer can
effect by choosing states on J ℓ , can be approximated up to
ℓ
±η (on block length ℓ) by choices from J ′ , analogously
to Lemma 8, which actually provides a positive answer to
Question 9 in the case of a classical jammer. Since |J ′ | is
bounded polynomially in ℓ, we could apply now Proposition
5 and incur an additional term of O(log ℓ) in the shared
randomness required, in particular it will still be of zero rate.
A third complex of questions concerns the extension of the
present results to other quantum channel capacities. This is
easy along the above lines for cases like the entanglementassisted capacity (cf. [11], [16]), but challenging for others,
such as the private capacity [12], [15]. This is interesting
because the error criterion (of decodability and privacy) does
not seem to correspond to an observable on the jammer
system. We leave this and the other open problems for future
investigation.
Acknowledgments. HB and CD were supported by the German BMBF through grants 16KIS0118K and 16KIS0117K.
JN was supported by the German BMWi and ESF,
grant 03EFHSN102. AW was supported by the ERC Advanced
Grant IRQUAT, the Spanish MINECO, projects no. FIS2013-

40627-P and FIS2016-86681-P, and the Generalitat de
Catalunya, CIRIT project 2014-SGR-966.
R EFERENCES
[1] D. Aharonov, A. Kitaev and N. Nisan, “Quantum circuits with
mixed states”, in: Proc. 30th STOC, pp. 20-30, ACM Press, 1998;
arXiv:quant-ph/9806029.
[2] R. Ahlswede, “Elimination of correlation in random codes for arbitrarily
varying channels”, Z. Wahrsch. Verw. Gebiete 44(2):159-175 (1978).
[3] R. Ahlswede and A. Winter, “Strong Converse for Identification via
Quantum Channels”, IEEE Trans. Inf. Theory 48(3):569-579 (2002);
arXiv:quant-ph/0012127.
[4] R. Ahlswede, I. Bjelaković, H. Boche and J. Nötzel, “Quantum Capacity under Adversarial Quantum Noise: Arbitrarily Varying Quantum
Channels”, Commun. Math. Phys. 317:103-156 (2013); arXiv[quantph]:1010.0418.
[5] R. Ahlswede and V. Blinovsky, “Classical Capacity of ClassicalQuantum Arbitrarily Varying Channels”, IEEE Trans. Inf. Theory
53(2):526-533 (2007).
[6] G. Aubrun and S. Szarek, Alice and Bob Meet Banach – The Interface
of Asymptotic Geometric Analysis and Quantum Information Theory,
Amer. Math. Soc. Math. Surveys & Monographs, vol. 223, Providence
RI, 2017.
[7] I. Bjelaković and H. Boche, “Classical capacities of compound and
averaged quantum channels”, IEEE Trans. Inf. Theory 55(7):3360-3374
(2009); arXiv[quant-ph]:0710.3027.
[8] I. Bjelaković, H. Boche and J. Nötzel, “Entanglement Transmission and
Generation under Channel Uncertainty: Universal Quantum Channel
Coding”, Commun. Math. Phys. 292(1):55-97 (2009). Erratum: Commun. Math. Phys. 317(1):99-102 (2013).
[9] I. Bjelaković, H. Boche, G. Janßen and J. Nötzel, “Arbitrarily varying
and compound classical-quantum channels and a note on quantum zeroerror capacities”, in: Information Theory, Combinatorics, and Search
Theory: In Memory of Rudolf Ahlswede (H. Aydinian, F. Cicalese,
C. Deppe, eds.), LNCS 7777, pp. 247-283, Springer Verlag, Berlin
Heidelberg, 2013; arXiv[quant-ph]:1209.6325v2.
[10] V. Blinovsky and M. Cai, “Classical-Quantum Arbitrarily Varying Wiretap Channel”, Information Theory, Combinatorics, and Search Theory:
In Memory of Rudolf Ahlswede (H. Aydinian, F. Cicalese, C. Deppe,
eds.), LNCS 7777, pp. 234-246, 2013; arXiv[]:1208.1151.
[11] H. Boche, G. Janßen and S. Kaltenstadler, “Entanglement-assisted classical capacities of compound and arbitrarily varying quantum channels”,
arXiv[quant-ph]:1606.09314 (2016).
[12] N. Cai, A. Winter and R. W. Yeung, “Quantum Privacy and Quantum
Wiretap Channels”, Problems Inf. Transm. 40(4):318-336 (2004).
[13] M. Christandl, R. König and R. Renner, “Postselection Technique for
Quantum Channels with Applications to Quantum Cryptography”, Phys.
Rev. Lett. 102:020504 (2009); arXiv[quant-ph]:0809.3019.
[14] I. Csiszár and P. Narayan, “The capacity of the arbitrarily varying channel revisited: positivity, constraints”, IEEE Trans. Inf. Theory 34(2):181193 (1988).
[15] I. Devetak, “The private classical information capacity and quantum
information capacity of a quantum channel”, IEEE Trans. Inf. Theory
51(1):44-55 (2005); arXiv:quant-ph/0304127.
[16] R. Duan, S. Severini and A. Winter, “On Zero-Error Communication via
Quantum Channels in the Presence of Noiseless Feedback”, IEEE Trans.
Inf. Theory 62(9):5260-5277 (2016); arXiv[quant-ph]:1502.02987.
[17] T. Ericson, “Exponential error bounds for random codes in the arbitrarily
varying channel”, IEEE Trans. Inf. Theory 31(1):42-48 (1985).
[18] P. Hayden, D. Leung, P. W. Shor and A. Winter, “Randomising Quantum
States: Constructions and Applications”, Commun. Math. Phys. 250:371391 (2004); arXiv:quant-ph/0307104.
[19] S. Karumanchi, S. Mancini, A. Winter and D. Yang, “Quantum Channel
Capacities with Passive Environment Assistance” IEEE Trans. Inf.
Theory 62(4):1733-1747 (2016); arXiv[quant-ph]:1407.8160v2.
[20] S. Karumanchi, S. Mancini, A. Winter and D. Yang, “Classical capacities of quantum channels with environment assistance”, Problems Inf.
Transm. 52(3):214-238 (2016); arXiv[quant-ph]:1602.02036v2.
[21] M. Mosonyi, “Coding Theorems for Compound Problems via Quantum
Rényi Divergences”, IEEE Trans. Inf. Theory 61(6):2997-3012 (2015);
arXiv[quant-ph]:1310.7525.
[22] J. Watrous, “Semidefinite Programs for Completely Bounded Norms”,
Theory of Computing 5(11):217-238 (2009); arXiv[quant-ph]:0901.4709.

