1

Covert Communication over Classical-Quantum
Channels
Azadeh Sheikholeslami∗† , Boulat A. Bash† , Don Towsley‡ , Dennis Goeckel∗ , Saikat Guha†
and Computer Engineering Department, University of Massachusetts, Amherst, MA
† Quantum Information Processing Group, Raytheon BBN Technologies, Cambridge, MA
‡ College of Information and Computer Sciences, University of Massachusetts, Amherst, MA

arXiv:1601.06826v4 [quant-ph] 25 Jun 2017

∗ Electrical

Abstract—The square root law (SRL) is the fundamental
limit of covert communication over classical memoryless
channels (with a classical adversary) and quantum lossynoisy bosonic channels (with√a quantum-powerful adversary). The SRL states that O( n) covert bits, but no more,
√
can be reliably transmitted in n channel uses with O( n)
bits of secret pre-shared between the communicating
parties. Here we investigate covert communication over
general memoryless classical-quantum (cq) channels with
fixed finite-size input alphabets, and show that the SRL
governs covert communications in typical scenarios.
√ We
characterize the optimal constants in front of n for
the reliably communicated covert bits, as well as for the
number of the pre-shared secret bits consumed. We assume a quantum-powerful adversary that can perform an
arbitrary joint (entangling) measurement on all n channel
uses. However, we analyze the legitimate receiver that is
able to employ a joint measurement as well as one that is
restricted to performing a sequence of measurements on
each of n channel uses (product measurement). We also
evaluate the scenarios where covert communication is not
governed by the SRL.

I. I NTRODUCTION
Security is important for many types of communication, ranging from electronic commerce to diplomatic
missives. Preventing the extraction of information from
a message by an unauthorized party has been extensively
studied by the cryptography and information theory
communities. However, the standard setting to analyze
secure communications does not address the situation
when not only must the content of the signal be protected, but also the detection of the occurrence of the
communication itself must be prevented. This motivates
the exploration of the information-theoretic limits of
This research was funded by the National Science Foundation
(NSF) under grants ECCS-1309573 and CNS-1564067, and DARPA
under contract number HR0011-16-C-0111. This document does not
contain technology or technical data controlled under either the
U.S. International Traffic in Arms Regulations or the U.S. Export
Administration Regulations. This work was presented in part at the
IEEE International Symposium on Information Theory, July 2016 [1].

Fig. 1. Covert communication setting. Alice has a noisy channel to
legitimate receiver Bob and adversary Willie. Alice encodes message
W with blocklength n code, and chooses whether to transmit. Willie
observes his channel from Alice to determine whether she is quiet
(null hypothesis H0 ) or not (alternate hypothesis H1 ). Alice and
Bob’s coding scheme must ensure that any detector Willie uses is
close to ineffective (i.e., a random guess between the hypotheses),
while allowing Bob to reliably decode the message (if one is
transmitted). Alice and Bob may share a secret prior to transmission.

covert communications, i.e., communicating with low
probability of detection/interception (LPD/LPI).
We consider a broadcast channel setting in Figure 1
typical in the study of the fundamental limits of secure
communications, where the intended receiver Bob and
adversary Willie receive a sequence of input symbols
from Alice that are corrupted by noise. We label one of
the input symbols (say, zero) as the “innocent symbol”
indicating “no transmission by Alice”, whereas the other
symbols correspond to transmissions, and are, therefore,
“non-innocent”. In a covert communications scenario,
Willie’s objective is to estimate Alice’s transmission status, while Bob’s objective is to decode Alice’s message,
given their respective observations. Thus, the transmitter
Alice must hide her transmissions in channel noise from
Willie while ensuring reliable decoding by Bob. The
properties of the noise in the channels from Alice to
Willie and Bob result in the following “six” scenarios:
(A) covert communication
is governed by the square
√
root law (SRL): O( n) covert bits (but no more)
can be reliably transmitted over n channel uses,
(B) corner cases:

2

1. covert communication is impossible,
2. O(1) covert bits can be reliably transmitted over
n channel uses,
3. covert communication is governed by the logarithmic law: O(log n) covert bits can be reliably
transmitted over n channel uses,
4. constant-rate covert communication is possible,
5. covert communication is governed
by the square
√
root logarithmic law: O( n log n) covert bits
(but no more) can be reliably transmitted over
n channel uses.
The research on the fundamental limits of covert communications in the setting described in Figure 1 has focused
on scenario (A), whereas scenarios in (B) are, arguably,
corner cases. The authors of [2], [3] examined covert
communications when Alice has additive white Gaussian
noise (AWGN) channels to both Willie and Bob. They
found that the SRL governs covert communications, and
that, to achieve it, Alice and Bob may have to share
a secret prior to communicating. The follow-on work
on the SRL for binary symmetric channels (BSCs) [4]
showed its achievability without the use of a pre-shared
secret, provided that Bob has a better channel from Alice
than Willie. The SRL was further generalized to the
entire class of discrete memoryless
channels (DMCs)
√
[5], [6] with [6] finding that O( n) pre-shared secret
bits were sufficient. However, the key contribution of
[5], [6] was √
the characterization of the optimal constants
in front of n in the SRL for both the communicated
bits as well as the pre-shared secret bits consumed in
terms of the channel transition probability p(y, z|x). We
note that, while zero is the natural innocent symbol for
channels that take continuously-valued input (such as the
AWGN channel), in the analysis of the discrete channel
setting an arbitrary input is designated as innocent. A
tutorial overview of this research can be found in [7].
It was recently shown that the SRL governs the fundamental limits of covert communications over a lossy
thermal-noise bosonic channel [8], which is a quantum
description of optical communications in many practical
scenarios (with vacuum being the innocent input). Notably, the SRL is achievable in this setting even when
Willie captures all the photons that do not reach Bob,
performs an arbitrary measurement that is only limited
by the laws of quantum mechanics, and has access to
unlimited quantum storage and computing capabilities.
Furthermore, the SRL cannot be surpassed even if Alice and Bob employ an encoding/measurement/decoding
scheme limited only by the laws of quantum mechanics,
including the transmission of codewords entangled over
many channel uses and making collective measurements.

Successful demonstration of the SRL for a particular
quantum channel in [7] motivates a generalization to
arbitrary quantum channels, which is the focus of this
article. We study the memoryless classical-quantum (cq)
channel: a generalization of the DMC that maps a finite
set of discrete classical inputs to quantum states at the
output. This allows us to prove achievability of the SRL
for an arbitrary memoryless quantum channel, since a cq
channel can be induced by a specific choice of modulation at Alice. Our main result is the following theorem
that establishes the optimal sizes log M and log K (in
bits) of the reliably-transmissible covert message and the
required pre-shared secret when the cq channel is used
n times:
Theorem 1. Consider a stationary memoryless
classical-quantum channel that takes input x ∈ X
at Alice and outputs the quantum states σx and
ρx at Bob and Willie, respectively, with x = 0
designating the innocent state. If, ∀x ∈ X , the supports
supp(σx ) ⊆ supp(σ0 ) and supp (ρx ) ⊆ supp (ρ0 ) such
that ρ0 is not a mixture of {ρx }x∈X \{0} , then there
exists a coding scheme that meets the covertness and
reliability criteria
B
lim D(ρ̄n kρ⊗n
0 ) = 0 and lim Pe = 0,

n→∞

n→∞

with optimal scaling coefficients of message length and
key length,
P
log M
x∈X \{0} p̃(x)D(σx kσ0 )
q
,
=
lim q
n→∞
1 2
χ
(ρ̃kρ
)
nD(ρ̄n kρ⊗n
)
0
0
2
and,
lim q

log K

n→∞

nD(ρ̄n kρ⊗n
0 )
hP
i+
p̃(x)(D(ρ
kρ
)
−
D(σ
kσ
))
x
0
x
0
x∈X \{0}
q
=
,
1 2
χ
(ρ̃kρ
)
0
2

where ρ̄n is the average state at Willie when a transmission occurs, PB
e is Bob’s decoding error probability,
p̃(x)
is
a
distribution
on non-innocent input symbols
P
p̃(x)
=
1
,
ρ̃
is
the average non-innocent state
x∈X \{0}
at Willie induced by p̃(x), [c]+ = max{c, 0}, D(ρkσ) ≡
Tr {ρ(log ρ − log σ)}
 is the quantum relative entropy,
and χ2 (ρkσ) ≡ Tr (ρ − σ)2 σ −1 is the quantum χ2 divergence.
Theorem 1 generalizes [6] by assuming that both
Willie and Bob are limited only by the laws of quantum
mechanics, and, thus, can perform arbitrary joint measurement over all n channel uses. While it is reasonable

3

to consider a quantum-powerful Willie, a practical Bob
would perform a symbol-by-symbol measurement. In
this case, we show that Theorem 1 still holds with quantum relative entropy D(σx kσ0 ) (characterizing Bob’s cq
channel from Alice) replaced by the classical relative
entropy characterizing the classical DMC induced by
Bob’s choice of measurement. We also develop explicit
conditions that differentiate covert communication corner cases for cq channels given in (B) above.
The scaling coefficients in Theorem 1 are optimal for
the discrete-input cq channels, as we prove both the
achievability and the converse in this setting. We leave
open the general converse, which should account for
Alice being able to encode her message in a codebook
comprising arbitrary quantum states that are entangled
over all n channel uses and for Bob to employ an
arbitrary joint measurement. Such a converse would
show that,
for an arbitrary quantum channel, no more
√
than O( n) bits can be sent both reliably and covertly
in n channel uses.
This paper is organized as follows: in the next section
we present the basic quantum information theory background, our system model, and metrics. In Section III we
state our main results, which we prove in the following
sections: we show the achievability of Theorem 1 in
Section IV, show the converse (that is limited to cq
channels) in Section V, and characterize in Section VI
the square-root law covert communications when Bob is
restricted to product measurement while Willie remains
quantum-powerful. In Section VII we show the converse
(that is again limited to cq channels) of the square root
logarithmic law, and in Section VIII, we prove that covert
communication is impossible if codewords with support
contained in the innocent state support at Willie are
unavailable. We conclude in Section IX with a discussion
of future work.
II. BACKGROUND , S YSTEM M ODEL , AND M ETRICS
A. Quantum Information Theory Background
Here we provide basic background on quantum information theory necessary for understanding the paper.
We refer the reader to [9]–[11] and other books for a
comprehensive treatment of quantum information. The
classical statistical description of a communication channel p(y|x) stems from the physics-based description of
the underlying quantum channel (e.g., the physical electromagnetic propagation medium) along with a choice
of the quantum states of the transmitted signals used
to modulate the information, and the specific chosen
receiver measurement. The most general quantum description of a point-to-point memoryless channel is given

by a trace-preserving completely-positive (TPCP) map
NA→B from Alice’s quantum input A to Bob’s quantum
output, B . In ith channel use, Alice can transmit a
quantum state φA
i ∈ D (HA ), where D (HA ) is the set of
unit-trace positive Hermitian operators (called “density
operators”) in a finite dimensional Hilbert space HA
at the channel’s input. This results in Bob receiving
the state σiB = NA→B φA
∈ D (HB ) as the ith
i
output of the channel. Then, over n independent and
identical
 Alice transmits a product
NnusesAof the channel,
⊗n
state
φ
∈
D
H
and Bob receives
a prodi=1
A


Nni B
N
n
A ∈ D H⊗n .
uct state
σ
=
N
φ
i
i=1 i
i=1 A→B
B
However, Alice, in general,
can transmit an entangled

n
⊗n
state φA ∈ D HA
over the n channel uses, resulting

B n = N ⊗n
An ∈
in a potentially
entangled
state
σ
φ
A→B

⊗n
D HB
at the channel’s output.1 Entangled states are
more general since they do not necessarily decompose
into product states.
One must measure a quantum state to obtain information from it. The most general quantum description of a
measurement is given by a set of positive operator-valued
measure
P (POVM) operators, {Πj }, where, ∀j, Πj ≥ 0
and
j Πj = I . When acting on a state σ , {Πj }
produces outcome j with probability p(j) = Tr (σΠj ). A
sequence of measurements acting individually on each of
n channel uses (followed by classical post-processing) is
called a product measurement. However, Bob, in general,
can employ a joint (entangling) measurement on the
n
output state σ B that cannot be realized by any product
measurement over n channel uses. Transmitting states
that are entangled over multiple channel uses and/or
employing joint measurements over multiple blocks of
channel uses at the output can increase the reliable
communication rate (in bits per channel use), even if
the underlying quantum channel acts independently and
memorylessly on each channel use.
Now consider the case when Alice uses a product
state for transmission, where she maps a classical index
x ∈ X , |X | < ∞, to a transmitted quantum state φA
x
in each channel use. The states transmitted in each
channel use are drawn from a predetermined input
alphabet that is a finite discrete
 subset of D (HA ).
B
A→B
A
Bob receives σx = N
φx ∈ D (HB ) , x ∈ X .
Suppose Bob is not restricted to a product measurement
for his receiver. This simplified description of a quantum
channel x → σxB is known as a classical-quantum (cq)
channel. The maximum classical communication rate
allowed by the cq channel is the Holevo capacity C =
n

The mostn general channel model NAn →B n takes a state σ A ∈
⊗n
⊗n
HA to σ B ∈ HB
, allowing the output of an entangled state for
an input product state. While we consider such a channel in Section
VIII, such generality is usually unnecessary.
1

4


 P

P
B
B
maxp(x) H
x∈X p(x)σx −
x∈X p(x)H σx
bits/sec, where H(σ) = −Tr (σ log2 σ) is the von
Neumann entropy of the quantum state σ [12], [13].
Restricting Bob to identical measurements on each
channel output that are described by the POVM{Πy },
y ∈ Y induces a DMC p(y|x) = Tr σxB Πy . The
Shannon capacity of this DMC, maxp(x) I(X; Y ), induced by any choice of product measurement POVM,
is generally strictly less than the Holevo capacity C of
the cq channel x → σxB . Furthermore, despite the fact
n
n
that the transmitted and received states φA and σ B are
product states over n uses of a memoryless cq channel,
n
a joint measurement on σ B is in general needed to
achieve the Holevo capacity.
A practically important quantum channel is the lossy
bosonic channel subject to additive thermal noise. It is a
quantum-mechanical model of optical communications.
This channel, when paired with an ideal laser light
(coherent state) transmitter and a heterodyne detection
receiver, induces a p(y|x) of a classical AWGN channel,
where x, y ∈ C and C denotes the set of complex
numbers. The same lossy thermal-noise bosonic channel
when paired with an ideal laser light transmitter and an
ideal photon counting receiver induces a Poisson channel
p(y|x), with x ∈ C and y ∈ N0 , where N0 denotes
the set of non-negative integers. The Holevo capacity
of the lossy thermal-noise bosonic channel without any
restrictive assumptions on the transmitted signals and
the receiver measurement is greater than the Shannon
capacities of both of the above channels, and those of all
simple classical channels induced by pairing the quantum channel with specific conventional transmitters and
receivers [14]. It is known that entangled inputs do not
help attain any capacity advantage for Gaussian bosonic
channels. In fact, transmission of a product state achieves
Holevo capacity: it is sufficient to send individuallymodulated laser-light pulses of complex-amplitude α on
each channel use with α drawn i.i.d. from a complex
Gaussian distribution p(α) [15]. On the other hand, using
joint measurements at the receiver increases the capacity
of the lossy thermal-noise bosonic channel over what is
achievable using any standard optical receiver, each of
which act on the received codeword by detecting a single
channel use at a time [16, Chapter 7].
It was recently shown that the SRL governs the
fundamental limits of covert communications over the
lossy thermal-noise bosonic channel [8], which motivates generalization to an arbitrary memoryless broadcast
quantum channel NA→BW from Alice to Bob and Willie.
Here we focus on the scenario depicted in Figure 2a,
where a TPCP map NA→BW and Alice’s product state
modulation x → φA
x , x ∈ X induces a cq channel

x → τxBW . However, if Bob and Willie use product measurements described by POVMs {Πy }⊗n and {Γz }⊗n
as depicted on Fig. 2c, then covert communication over
the induced classical DMC p(y, z|x) is governed by the
SRL [5], [6]. Therefore, our main goal is to characterize
the fundamental limits of covert communication on the
underlying cq channel x → τxBW in the following
scenarios:

1) no restrictions are assumed on Bob’s and Willie’s
measurement choices (depicted in Figure 2a), and,
2) a more practically important scenario when Bob is
given a specific product measurement {Πy } but no
assumptions are made on Willie’s receiver measurement (as depicted in Figure 2b).

B. System Model
As depicted in Figure 2, a transmitter Alice maps a
classical input x ∈ X , X = {0, 1, . . . , N }, to a quantum
state φA
x and sends it over a quantum channel NA→BW .
The induced cq channel is the map x → τxBW ∈
D(HBW ), where τxBW = NA→BW (φA
x ). The cq channel
from Alice to Bob is the map x → σxB ∈ D(HB ), where
σxB = TrW {τxBW } is the state that Bob receives, and the
cq channel from Alice to Willie is the map x → ρW
x ∈
BW } is the state that Willie
D(HW ), where ρW
=
Tr
{τ
B x
x
receives, and TrC {·} is the partial trace over system
C . The symbol 0 is taken to be the innocent symbol,
which is the notional channel input corresponding to
when no communication occurs, and symbols 1, . . . , N ,
the non-innocent symbols, comprise Alice’s modulation
alphabet. For simplicity of notation, we drop the systemlabel superscripts, i.e., we denote τ BW by τ , σ B by σ ,
n
n
ρW by ρ, σ B by σ n , and ρW by ρn . We consider
communication over a memoryless cq channel. Hence,
the output state corresponding to the input sequence
x = (x1 , . . . , xn ) ∈ X n , xi ∈ {0, 1, . . . , N }, at Bob
is given by:
⊗n
σ n (x) = σx1 ⊗ · · · ⊗ σxn ∈ D(HB
),

and at Willie is given by:
⊗n
ρn (x) = ρx1 ⊗ · · · ⊗ ρxn ∈ D(HW
).

The innocent input sequence is 0 = (0, . . . , 0), with the
corresponding outputs σ0⊗n = σ0 ⊗ · · · ⊗ σ0 and ρ⊗n
0 =
ρ0 ⊗ · · · ⊗ ρ0 at Bob and Willie, respectively.
Alice intends to transmit to Bob reliably, while keeping Willie oblivious of the transmission attempt. We thus
consider encoding of transmissions next.

5

(a)

(b)

(c)
Fig. 2. Classical-quantum channel scenarios. Alice encodes message W into n-symbol codeword x = (x1 , . . . , xn ), where xi ∈ X ,
X = {1, . . . , N }. As each symbol x ∈ X is mapped to the input quantum state φx , codeword x is mapped to product state input
th
A
φA (x) = φA
x1 ⊗ · · · ⊗ φxn . The i use of a quantum memoryless broadcast channel NA→BW from Alice to Bob and Willie produces the
BW
joint state τxi at the output (with the product joint state over n uses of the channel being τ BW (x) = τxBW
⊗· · ·⊗τxBW
). The corresponding
n
1
W
marginal product states at Bob’s and Willie’s receivers are σ B (x) = σxB1 ⊗ · · · ⊗ σxBn and φA (x) = ρW
x1 ⊗ · · · ⊗ ρxn , respectively. In (a)
Bob and Willie use joint quantum measurements over n channel uses, while (b) depicts a more practically important scenario where Bob
is restricted to using a specific product measurement (that induces a DMC p(y|x) on his channel from Alice) while Willie is unrestricted.
In (c) both Bob and Willie are restricted to using a specific product measurement, which reduces the cq channel x → τxBW to a classical
discrete memoryless broadcast channel, p(y, z|x).

C. Codebook Construction
Denote the message set by M = {1, . . . , M }. Covertness and reliability are fundamentally conflicting requirements: on one hand, the codewords must be “close” to
the innocent sequence to be undetected by Willie, while,
on the other hand, they must be “far enough apart” from
each other (and the innocent sequence) to be reliably
discriminated by Bob. Willie’s objective is fundamentally
easier than Bob’s, as he has to distinguish between
two simple hypotheses in estimating Alice’s transmission
state, while Bob must distinguish between at least M
codewords. Therefore, as is the case for other channels,
to ensure covert and reliable communications, Bob has
to have an advantage over Willie in the form of a preshared secret with Alice (though the pre-shared secret is
unnecessary if Bob’s channel from Alice is better than
Willie’s channel from Alice).

Alice and Bob employ a codebook, where messages
in M are randomly mapped to the set of n-symbol
codewords in {x(m, k)}M
m=1 based on the pre-shared
k∈K
secret k ∈ K = {1, . . . , K}. Formally, M −−−→ X n .
We assume that each message is equiprobable. Given
a pre-shared secret k ∈ K, Bob performs decoding
via POVM Λ = {Λm,k }M
his codeword received
m=1 on P
overP
n channel uses, such that
m Λm,k ≤ I , where
I − m Λm,k corresponds to decoding failure.
D. Reliability
The average probability of decoding error at Bob is:
PB
e

M
1 X
(1 − Tr {Λm,k σ n (m, k)}) .
=
M
m=1

where σ n (m, k) is a shorthand for σ n (x(m, k)).

(1)

6

Definition 1. A coding scheme is called reliable if it
guarantees that for sufficiently large n and for any δ > 0,
PB
e ≤ δ.
E. Covertness
We denote the state received by Willie over n channel
uses when message m is sent and the value of the shared
secret is k by ρn (m, k). Willie must distinguish between
the state that he receives when no communication occurs
(null hypothesis H0 ):
ρ⊗n
0 = ρ0 ⊗ · · · ⊗ ρ0 ,

(2)

and the average state that he receives when Alice transmits (alternate hypothesis H1 ):
M K
1 XX n
ρ (m, k).
ρ̄ =
MK
n

(3)

m=1 k=1

Willie fails by either accusing Alice of transmitting
when she is not (false alarm), or missing Alice’s transmission (missed detection). Denoting the probabilities
of these errors by PFA = P(choose H1 |H0 is true)
and PMD = P(choose H0 |H1 is true), respectively,
and assuming that Willie has no prior knowledge of
Alice’s transmission state (i.e., uninformative priors
P(H0 is true) = P(H1 is true) = 12 ), Willie’s probability of error is:
PFA + PMD
.
(4)
2
Randomly choosing whether or not to accuse Alice
1
yields an ineffective detector with PW
e = 2 . Therefore,
a transmission is covert when Willie’s detector is forced
to be arbitrarily close to ineffective:
PW
e =

1
≥ − ξ,
2
for any ξ > 0 and sufficiently large n.
PW
e

where D(ρkσ) ≡ Tr {ρ(log ρ − log σ)} is the quantum
relative entropy.
Combining (6) and (7), we have that

D ρ̄n kρ⊗n
<
0
√ implies the covertness criterion in
(5) with ξ , ( 2 ln 2)/4. We employ quantum relative entropy in the analysis that follows because of
its convenient mathematical properties such as additivity
for product states. Combining reliability and covertness
metrics, we define (δ, )-covertness as follows.
Definition 3. We call a scheme (δ, )-covert if for
sufficiently large n, PB
e ≤ δ for any δ > 0, and
D ρ̄n kρ⊗n
<

for
any
 > 0.
0
In some situations Alice can tolerate a (small) chance
of detection. That is, instead of ensuring that  > 0, she
must ensure a relaxed covertness condition  ≥ 0 , where
0 > 0 is a constant. This is a weaker covertness criteria,
and we define it as the weak covertness condition. A
coding scheme
 is called weak covert if it ensures that
⊗n
n
D ρ̄ kρ0 <  for any  > 0 where 0 > 0 is a small
constant, and for sufficiently large n.

III. M AIN R ESULTS
Here we present our main results, deferring the formal
proofs to latter sections. The properties of quantum
channels from Alice to Bob and Willie dictate the fundamental limits of covert communications, as discussed
in the scenarios below (we follow the labeling of the
scenarios from the introduction). Table III summarizes
our results using the asymptotic notation [19, Ch. 3.1]
that we employ throughout this paper, where:
•

(5)

Definition 2. A coding scheme is called covert if it
1
ensures that PW
e ≥ 2 − ξ, for any ξ > 0 and for n
large enough.

•

•

The trace distance
np between quantum
o states ρ and σ
†
is kρ − σk1 ≡ Tr
(ρ − σ)(ρ − σ) . The minimum
n
PW
e is related to the trace distance between the states ρ̄
⊗n
and ρ0 as follows [17], [18]:


1
1 n
⊗n
W
min Pe =
1 − kρ̄ − ρ0 k1 .
(6)
2
2

By the quantum Pinsker’s inequality [9, Theorem
11.9.2],
2

1
kρ̄n − ρ⊗n
≤ D ρ̄n kρ⊗n
,
(7)
0 k1
0
2 ln 2

•

•

f (n) = O(g(n)) denotes an asymptotic upper
bound on f (n) (i.e., there exist constants m, n0 > 0
such that 0 ≤ f (n) ≤ mg(n) for all n ≥ n0 ),
f (n) = o(g(n)) denotes an upper bound on f (n)
that is not asymptotically tight (i.e., for any constant
m > 0, there exists constant n0 > 0 such that 0 ≤
f (n) < mg(n) for all n ≥ n0 ),
f (n) = Ω(g(n)) denotes an asymptotic lower
bound on f (n) (i.e., there exist constants m, n0 > 0
such that 0 ≤ mg(n) ≤ f (n) for all n ≥ n0 ),
f (n) = ω(g(n)) denotes a lower bound on f (n)
that is not asymptotically tight (i.e., for any constant
m > 0, there exists constant n0 > 0 such that 0 ≤
mg(n) < f (n) for all n ≥ n0 ), and
f (n) = Θ(g(n)) denotes an asymptotically
tight bound on f (n) (i.e., there exist constants
m1 , m2 , n0 > 0 such that 0 ≤ m1 g(n) ≤ f (n) ≤
m2 g(n) for all n ≥ n0 ). f (n) = Θ(g(n)) implies
that f (n) = Ω(g(n)) and f (n) = O(g(n)).

7

TABLE I
S CALING LAWS FOR - RELIABLE COVERT TRANSMISSION OF log M

BIT MESSAGE OVER

n CQ CHANNEL USES

Willie
∀x 6= 0, supp(ρx ) * supp(ρ0 )

Bob
a
b
c

∀x 6= 0, supp(σx ) ⊆ supp(σ0 )
∃x 6= 0 s.t. supp(σx ) * supp(σ0 )
∃x 6= 0 s.t. supp(σx ) ∩ supp(σ0 ) = ∅

δ>0
0
0
0

a

δ ≥ δ0
0
O(1)c
O(log n)

∃x 6= 0 s.t. supp(ρx ) ⊆ supp(ρ0 )
P
P
ρ0 6= x6=0 pm (x)ρx b ρ0 = x6=0 pm (x)ρx b
√
Θ(
Θ(n)
√ n)
Θ(√n log n)
Θ(n)
Θ( n log n)
Θ(n)

Where δP
0 > 0 is a constant.
Where x6=0 pm (x) = 1.
If ∃x 6= 0, x0 6= 0 s.t. supp(σx ) ∩ supp(σx0 ) = ∅.

A. Square-root law covert communications
Consider the case when the supports of all noninnocent symbols are contained in the support of the
innocent symbol, i.e., ∀x ∈ X , supp(ρx ) ⊆ supp(ρ0 ).
The central theorem of this paper establishes the optimum number of transmissible (δ, )-covert information
bits and the optimum number of required key bits over
n uses of a classical-quantum channel that satisfies the
conditions described above. We re-state it here from the
introduction:
Theorem 1. Consider a stationary memoryless
classical-quantum channel that takes input x ∈ X
at Alice and outputs the quantum states σx and
ρx at Bob and Willie, respectively, with x = 0
designating the innocent state. If, ∀x ∈ X , the supports
supp(σx ) ⊆ supp(σ0 ) and supp (ρx ) ⊆ supp (ρ0 ) such
that ρ0 is not a mixture of {ρx }x∈X \{0} , then there
exists a coding scheme that meets the covertness and
reliability criteria
B
lim D(ρ̄n kρ⊗n
0 ) = 0 and lim Pe = 0,

n→∞

n→∞

with optimal scaling coefficients of message length and
key length,
P
log M
x∈X \{0} p̃(x)D(σx kσ0 )
q
lim q
,
=
n→∞
1 2
χ
(ρ̃kρ
)
nD(ρ̄n kρ⊗n
)
0
0
2
and,
lim q

log K

n→∞

nD(ρ̄n kρ⊗n
0 )
i+
hP
x∈X \{0} p̃(x)(D(ρx kρ0 ) − D(σx kσ0 ))
q
=
,
1 2
2 χ (ρ̃kρ0 )

where ρ̄n is the average state at Willie when a transmission occurs, PB
e is Bob’s decoding error probability,
p̃(x) is a distribution on non-innocent input symbols

P

x∈X \{0} p̃(x) = 1, ρ̃ is the average non-innocent state
at Willie induced by p̃(x), [c]+ = max{c, 0}, D(ρkσ) ≡
Tr {ρ(log ρ − log σ)}
 is the quantum relative entropy,
and χ2 (ρkσ) ≡ Tr (ρ − σ)2 σ −1 is the quantum χ2 divergence.

We can pick an input distribution on non-innocent
symbols p̃(x) to maximize the scaling coefficient of the
message length, or to minimize the scaling coefficient
of the key length, and, of course, those distributions
would not necessarily be the same. In fact, p̃(x) can
be optimized over some function of the two scaling
coefficients. Our main result is the generalization of
[6]: indeed, if Bob and Willie both employ symbolby-symbol measurements as in Figure 2, then the cq
channels from Alice reduce to DMCs. Replacing the
quantum relative entropy and χ2 -divergence between
states by the classical counterparts between the induced
probability distributions reduces to the results of [6].
In a practical setting, Bob is likely to be limited to a
product measurement, however, one cannot make such
an assumption about Willie. However, we show that
the expressions in Theorem 1 still hold in this setting
as long as D(σx kσ0 ) (characterizing Bob’s cq channel
from Alice) is replaced by the classical relative entropy
characterizing the classical channel induced by Bob’s
choice of measurement.
In Section IV, we present the proof of achievability of
Theorem 1. For simplicity of exposition, first we present
the proof of achievability for two symbols (one innocent
and one non-innocent symbol) and then we discuss the
required adjustments to extend it to the case of multiple
non-innocent symbols. In Section V, we present the
proof of converse of Theorem 1 for the case of multiple
non-innocent symbols.
B. Corner Cases
1) No covert communications: When the support for
all states received by Willie corresponding to Alice’s

8

codewords is not contained in the support of the innocent
sequence, then reliable covert communication is impossible. Denoting the support of state ρ by supp(ρ), this
is formally stated as follows:
Theorem 2. When, ∀m ∈ M, k ∈ K, and
supp(ρn (m, k)) * supp(ρ⊗n
0 ), (δ, )-covert communication is impossible.
We prove this theorem in Section VIII by showing that
for any n there exists a region where (δ, )-covertness is
not achievable, i.e., ensuring any level of covertness implies that transmission cannot be made reliable. Theorem
2 generalizes [8, Theorem 1] for lossy bosonic channels
to arbitrary quantum channels. Unlike other theorems in
this paper, this result is fully general, as it places no
restrictions on Alice’s transmitted states (they could be
entangled across n channel uses) and the channel (which
does not have to be memoryless).
2) Transmission of O(1) covert bits in n channel uses:
Now let’s return to the cq channel setting, and consider
the case when the support of every non-innocent state
at Willie is not contained in the support of the innocent
state, i.e., ∀x ∈ X \{0}, supp(ρx ) * supp(ρ0 ). Let’s
also assume that the support of every non-innocent state
at Willie is not orthogonal to the support of the innocent
state (i.e., ∀x ∈ X \{0}, supp(ρx ) ∩ supp(ρ0 ) 6= ∅),
precluding trivial errorless detection by Willie. Even so,
by Theorem 2, an (δ, )-covert communication scheme
does not exist in such setting. However, we can have a
weak-covert scheme as described in Section II-E. The
trace distance between the average received state at
Willie given in (3) and the innocent state ρ⊗n
over n
0
channel uses can be written as,

kρx∗ −ρ0 k1 , and, in (8) we denote theP
average
of
Pnumber
K
L
non-innocent symbols as L̄ = M1K M
m=1
k=1 m,k .
Hence, employing the relaxed covertness condition, rearranging (5), substituting (8), employing the quantum
Pinsker’s inequality, and solving for L̄ yields:
L̄ ≤

40
,
kρx∗ − ρ0 k1

(9)

(8)

which implies that Alice may be able to transmit L̄
non-innocent symbols on average and meet the relaxed
covertness criteria. This allows us to consider two corner
cases: transmission of O(1) covert bits in n channel uses,
and logarithmic law covert communication which will be
discussed in next section.
Under the weak covertness condition above, suppose
that ∀x ∈ X \{0}, supp(σx ) ∩ supp(σ0 ) 6= ∅, but
there exist at least two non-innocent symbols x, x0 ∈
X \{0} with non-overlapping supports, i.e., supp(σx ) ∩
supp(σx0 ) = ∅. Alice can meet the relaxed covertness
condition by transmitting L̄ non-innocent symbols on
average. Choosing x or x0 equiprobably conveys a single
bit of information to Bob, as σx and σx0 are perfectly
distinguishable. Since L̄ is a constant, on average O(1)
covert bits of information can thus be conveyed from
Alice to Bob in n channel uses in this scenario.
3) Logarithmic law covert communication: Under the
relaxed covertness condition above, suppose there exists
at least one x ∈ X \{0} such that the support of the
corresponding symbol at Bob does not overlap with that
of innocent state, i.e., supp(σx ) ∩ supp(σ0 ) = ∅. Then,
Alice can use L̄ non-innocent symbols x to indicate
positions within a block of n symbols to Bob while
meeting the relaxed covertness condition. Since Bob can
perfectly distinguish between the innocent state σ0 and
non-innocent state σx , this conveys O(log n) bits of
information on average in n channel uses.
4) Constant rate covert communication: Consider the
case when Willie’s state is such that ρ0 is a mixture of
{ρx }x∈X
π(·) where
P \{0} , i.e., there exists a distribution
P
ρ0 = x∈X \{0} π(x)ρx such that x∈X \{0} π(x) = 1,
but π(·) on non-innocent
symbols does not induce σ0 at
P
Bob, i.e., σ0 6= x∈X \{0} π(x)σx . Define the distribution:

απ(x) if x 6= 0, and
p(x) =
1 − α if x = 0,

where (a) follows from the convexity of the trace distance [9, Eq. (9.9)], and (b) follows from the fact that ρn
is a tensor-product state and the telescoping property of
the trace distance [9, Eq. (9.15)]. In (c), Lm,k is the number of non-innocent symbols in the (m, k)th codeword,
and x∗ is the symbol such that ∀x ∈ X , kρx − ρ0 k1 ≤

where 0 < α ≤ 1 is the probability of using a
non-innocent symbol. Using {p(x)} on input symbols
results in an ensemble {p(x), σx } at Bob that has positive Holevo information by the Holevo-SchumacherWestmoreland (HSW) theorem [9, Chapter 19]. Thus,
Alice can simply draw her codewords from the set of

kρ̄n − ρ⊗n
0 k1 = k
(a)

≤

(b)

≤

(c)

≤

M K
1 XX n
ρ (m, k) − ρ0⊗n k1
MK

1
MK
1
MK
1
MK

m=1 k=1
M
K
XX

kρn (m, k) − ρ⊗n
0 k1

m=1 k=1
M X
K X
n
X

kρ(xi (m, k)) − ρ0 k1

m=1 k=1 i=1
M X
K
X

Lm,k kρx∗ − ρ0 k1

m=1 k=1

= L̄kρx∗ − ρ0 k1

9

states using the probability distribution {p(x)} and transmit at the positive rate undetected by Willie. Therefore,
in the results that follow, we assume that ρ0 is not a
mixture of
√ the non-innocent symbols
5) O( n log n) covert communication: Now suppose
there exists xs ∈ X \{0} such that supp(σxs ) *
supp(σ0 ) and supp(ρxs ) ⊆ supp(ρ0 ). That is, part of
the support of the output state corresponding to xs lies
outside of the innocent state support at Bob while lying
inside the innocent state support at Willie. Also suppose
Alice only uses {0, xs } for transmission. Let Bob use
a POVM {(I − P0 ), P0 } on each of his n received
states, where P0 is the projection onto the innocent
state support. This measurement results in a perfect
identification of the innocent symbol, and an error in
identification of xs with probability Tr{P0 σxs }. Since
specifying a POVM induces a classical DMC, we can
use the achievability part in the proof of [6, Theorem
7] (with the probability that xs is identified
by Bob
√
κ = 1 − Tr{P0 σxs }) to show that O( n log n) (δ, )covert bits are achievable in n channel uses. However,
for a converse in a cq channel setting we must show
that exceeding this limit is impossible in n uses of
such channel even when Bob uses an arbitrary decoding
POVM. We provide this proof in Section VII.
IV. ACHIEVABILITY OF THE SRL
In this section we prove the achievability of the
square root scaling stated in Theorem 1. As mentioned
earlier, for simplicity first we provide a proof for the
case of two symbols, i.e., X = {0, 1}, where 0 is the
innocent symbol and 1 is the non-innocent symbol. The
achievability is formally stated as follows:

A. Prerequisites
1) Prior Probability Distribution: We consider the
following distribution on X = {0, 1}:

αn
if x = 1, and
p(x) =
(10)
1 − αn if x = 0,
where 1 is the non-innocent symbol, 0 is the innocent
symbol, and αn is the probability of transmitting 1. The
output of the classical-quantum channel corresponding to
this input distribution in a single channel use is denoted
by,
X
p(x)τx = (1 − αn )τ0 + αn τ1 .
(11)
ταn =
x∈X

Hence, the state corresponding to this input distribution
that Bob receives is σαn = TrW {ταn }, and that Willie
receives is ραn = TrB {ταn }, respectively. From the
linearity of the trace,
X
σ αn =
p(x)σx = (1 − αn )σ0 + αn σ1 ,
(12)
x∈X

and,
ραn =

X

p(x)ρx = (1 − αn )ρ0 + αn ρ1 .

(13)

x∈X

2) Characterization of αn : In this section we show
that for a specific choice of αn , the quantum relative
entropy between Willie’s state induced by p(x) over n
channel-uses, ρ⊗n
αn , and the state induced by the innocent
symbol over n channel uses, ρ⊗n
0 , vanishes as n tends to
infinity. This is the generalization of a similar concept
introduced in [6] to classical-quantum systems.
First consider the following lemmas:

Lemma 1 ([20]). For any positive semi-definite operaTheorem 3. For any stationary memoryless classical- tors A and B and any number c ≥ 0,
quantum channel with supp (σ1 ) ⊆ supp (σ0 ) and
1
supp (ρ1 ) ⊆ supp (ρ0 ), there exists a coding scheme,
D(AkB) ≥ Tr{A − A1−c B c }
(14)
c
such
that,
for
n
sufficiently
large
and
γ
=
o(1)
∩
n
 
1 
D(AkB) ≤ Tr A1+c B −c − A .
(15)
ω √1n ,
c


√
γn
log M = (1 − ς)γn nD (σ1 kσ0 ) ,
√n ,
Lemma 2. For αn = √
and γn = o(1) ∩ ω log
n
n
√
log K = γn n [(1 + ς)D (ρ1 kρ0 ) − (1 − ς)D (σ1 kσ0 )]+ ,

⊗n
D ρ⊗n
≤ ς3 γn2 ,
(16)
αn kρ0
and,
√
where ς3 > 0 is a constant.
−ς1 γn n
PB
,
e ≤e
√
Proof. From the memoryless property of the channel and
⊗n ⊗n
−ς2 γn n
D(ρ̄n kρ⊗n
,
0 ) − D(ραn kρ0 ) ≤ e
additivity of relative entropy,
⊗n
2
D(ρ⊗n

αn kρ0 ) ≤ ς3 γn ,
⊗n
D ρ⊗n
= nD(ραn kρ0 ).
(17)
αn kρ0
where ς ∈ (0, 1), ς1 > 0, ς2 > 0, and ς3 > 0 are
Using (15) in Lemma 1 with c = 1 and some algebraic
constants, and [c]+ = max{c, 0}.
manipulations, we obtain:
Before we proceed to the proof, we state important
n
o
D(AkB) ≤ Tr (A − B)2 B −1 .
(18)
definitions and lemmas.

10

Substituting A = ρ0 + αn (ρ1 − ρ0 ) and B = ρ0 in (18)
we obtain:
n
o
D(ραn kρ0 ) ≤ Tr (ρ0 + αn (ρ1 − ρ0 ) − ρ0 )2 ρ−1
0
n
o
2 −1
2
= αn Tr (ρ1 − ρ0 ) ρ0
= αn2 χ2 (ρ1 kρ0 ),

(19)

where χ2 (ρkσ) is the χ2 -divergence between ρ and σ
γn
,
[21]. Combining (17) and (19), and choosing αn = √
n

⊗n
D ρ⊗n
≤ ς3 γn2 ,
αn kρ0
where ς3 > 0 is a constant.
We prove Theorem 3 by first establishing the reliability of the coding scheme, and then its covertness.
B. Reliability Analysis
We restate [22, Lemma 2] and use it in the analysis
of the error probability:

Consider the encoding map {1, . . . , M } → x ∈ X n
and the square-root measurement decoding POVM for n
channel uses,
!−1/2
!−1/2
M
M
X
X
n
Λm =
Πk
Πm
Πk
,
(23)
k=1

Πm = {σ̂ n (m) − ea σ0⊗n > 0}.

(24)

Here σ̂ n (m) = Eσ0⊗n (σ n (m)) is the pinching of σ n (m)
as defined in Appendix A, and a > 0 is a real number
to be determined later.
For compactness of notation, we
P denote the summations are over x ∈ X n by
x . Bob’s average
decoding error probability over the random codebook is
characterized by the following lemma:
Lemma 5. For any a > 0,
 
E PB
e
X
≤2
p(x) Tr{σ n (x){σ̂ n (x) − ea σ0⊗n ≤ 0}}
x

Lemma 3. For operators 0 < A < I and B > 0, we
have,


+4M e−a exp γn2 Tr{σ0−1 σ12 } .

(25)

Proof. Bob’s average decoding error probability is:

I − (A + B)−1/2 A(A + B)−1/2
≤ (1 + c) (I − A) + (2 + c + c−1 )B,

M
1 X
(1 − Tr{σ n (m)Λnm })
M
m=1



M

X
1 X  n
≤
Πj  ,
Tr σ (m) 2(1 − Πm ) + 4


M

PB
e =

where c > 0 is a real number and I is an identity
operator.
Next, we provide a lemma that is useful for proving
both the reliability and the covertness. First, consider a
self-adjoint
P operator A and its spectral decomposition
A =
i λi |ai i hai |, where {λi } are eigenvalues, and
|ai i hai | are the projectors on the associated eigenspaces.
Then, the non-negative spectral projection on A is defined as in [22]:
X
{A ≥ 0} =
|ai i hai | ,
(20)
i:λi ≥0

which is the projection to the eigenspace corresponding to non-negative eigenvalues of A. The projections
{A > 0}, {A ≤ 0}, and {A < 0} are defined similarly.
Lemma 4. For any Hermitian matrix A and positivedefinite matrix B ,
Tr {BA {A < 0}} ≤ 0,

k=1

where we define the projector Πm as,

m=1

j6=m

where the inequalityP
follows from Lemma 3 with c = 1,
A = Πm , and B = j6=m Πj . Hence,
 
E PB
e
#
"
M
2 X
n
n
a ⊗n
≤E
Tr{σ (m){σ̂ (m) − e σ0 ≤ 0}}
M
m=1


M X
X
4
+E 
Tr{σ n (m){σ̂ n (j) − ea σ0⊗n > 0}}
M
m=1 j6=m
X
p(x) Tr{σ n (x){σ̂ n (x) − ea σ0⊗n ≤ 0}}
=2
x∈X n

+4(M − 1)

X

p(x) Tr{σα⊗n
{σ̂ n (x) − ea σ0⊗n > 0}},
n

x∈X n

(26)
(21)
We can upper-bound the second sum of (26) as follows:
X

p(x) Tr σα⊗n
{σ̂ n (x) − ea σ0⊗n > 0}
n

and,
Tr {BA {A > 0}} ≥ 0.

Proof. See Appendix B.

(22)

x
(a)

=

X
x


p(x) Tr σ̂α⊗n
{σ̂ n (x) − ea σ0⊗n > 0}
n

11

(b)

=

X

n
o
≤ (n + 1)rd tr Tr An (B n )r/2 (An )−r (B n )r/2 ,

p(x)

x

Tr
(c)

≤

X

n

σ0⊗n

−1

o
⊗n
n
a ⊗n
σ̂α⊗n
σ
{σ̂
(x)
−
e
σ
>
0}
0
0
n

p(x)

x

n
o
−1 ⊗n n
e−a Tr σ0⊗n
σ̂αn σ̂ (x){σ̂ n (x) − ea σ0⊗n > 0}
n
(d) X
−1 ⊗n n o
≤
p(x)e−a Tr σ0⊗n
σ̂αn σ̂ (x)

(30)
where Ân = EB n (An ) and d = dim HB . Applying this
to states An = σ n (x) and B n = σ0⊗n and setting t = ea
yields,
X
p(x) Tr{σ n (x){σ̂ n (x) − ea σ0⊗n ≤ 0}}
x

≤

X

p(x)(n + 1)rd

x

x

= e−a Tr

n


⊗n −1

σ0


n
o
r/2
r/2
ar+log Tr σ n (x)(σ0⊗n ) (σ n (x))−r (σ0⊗n )

 o
⊗n 2

σ̂αn
n

e

= (n + 1)rd


= e−a Tr σ0−1 σ̂α2 n

n
(e) −a
=e
Tr σ0−1 σα2 n
,

and then
using linearity of trace; (d) follows since

⊗n −1
σ0
, σ̂α⊗n
, and σ̂ n (x) commute, which implies
 n
⊗n −1 ⊗n n
that σ0
σ̂αn σ̂ (x) is positive-definite; and, finally,
(e) follows from the second property of pinching in
Appendix A.
Now, Tr{σ0−1 σα2 n } can be simplified and upperbounded as follows:
Tr{σ0−1 σα2 n } = Tr{σ0−1 ((1 − αn )σ0 + αn σ1 )2 }
=
≤
≤

p(x)

x

(27)

where (a) follows from the second property of pinching
in Appendix A and the fact that {σ̂ n (x) − ea σ0⊗n > 0}
commutes with σ0⊗n ; (b) follows from the fact that σ̂α⊗n
n
commutes with σ0⊗n ; (c) follows by applying Lemma 4
−1 ⊗n
with A = σ̂ n (x) − ea σ0⊗n and B = σ0⊗n
σ̂αn to
obtain:
n

−1 ⊗n n
Tr σ0⊗n
σ̂αn σ̂ (x) − ea σ0⊗n
o
 n
σ̂ (x) − ea σ0⊗n > 0
≥ 0,

1 − αn2 + αn2 Tr{σ0−1 σ12 }
1 + αn2 Tr{σ0−1 σ12 }

exp αn2 Tr{σ0−1 σ12 } .

X

e(ar+

log Tr{σ(xi )σ0 r/2 (σ(xi ))−r σ0 r/2 })

Since ϕ(σ0 , r) = 0, only terms with xi = 1 contribute to
the sum in (31). Define the random variable L indicating
the number of non-innocent symbols in x. We define the
set similar to the one used in [6],
√
√
Cµn = {l ∈ N : |l − µγn n| < γn n},
(32)
describing the values that the random variable L takes,
where 0 < µ < 1 is a constant. Using a Chernoff bound,
2

P (L ∈
/ Cµn ) ≤ 2e−µ

√
γn n/2

Now we evaluate the first term of the right-hand side
of (25). In [23, Section 3] it is shown that for any tensor
product states An and B n and any number t > 0 and
0 ≤ r ≤ 1,
Tr{An {Ân − tB n ≤ 0}}

.

(33)

Hence,
!
n
X
X
p(x) exp ar −
ϕ(σ(xi ), r)
x

i=1

X

≤

X

p(x) exp ar −

L
X

!
ϕ(σ1 , r)

i=1

p(L = l) exp (ar − lϕ(σ1 , r)) + P (L ∈
/ Cµn )

l∈Cµn

√

√
2
≤ exp ar − (1 − µ)γn nϕ(σ1 , r) + 2e−µ γn n/2 .

(34)

x


≤ e−a exp nαn2 Tr{σ0−1 σ12 }

= e−a exp γn2 Tr{σ0−1 σ12 } . (29)

,

where the equality follows from the memoryless property
of the channel. Let us define the function
n
o
ϕ(σ(xi ), r) = − log Tr σ(xi )σ0 r/2 (σ(xi ))−r σ0 r/2

x

Substituting (28) into (27) yields:
X
{σ̂ n (x) − ea σ0⊗n > 0}}
p(x) Tr{σα⊗n
n

i=1

(31)

= EL

(28)

Pn

∂
∂r ϕ(σ1 , r)

Appendix C shows that
is uniformly continuous, and
∂
ϕ(σ1 , 0) = D(σ1 kσ0 ).
∂r
Moreover, we have ϕ(σ1 , 0) = 0. Now let ε > 0 be
∂
an arbitrary constant. Because ∂r
ϕ(σ1 , r) is uniformly
continuous, there exists 0 < κ < 1 such that
ϕ(σ1 , r) − ϕ(σ1 , 0)
− D(σ1 kσ0 ) < ε for 0 < r ≤ κ.
r−0
(35)

12

Substituting (34)
and (35) into (31), and letting a =
√
(1−ν)(1−µ)γn nD (σ1 kσ0 ) where ν > 0 is a constant,
and realizing that r ≤ κ, yields,
X
p(x) Tr{σ n (x){σ̂ n (x) − ea σ0⊗n ≤ 0}}
x



≤ (n + 1)κd e−νκ(1−µ)γn

√

n

+ 2e−µ

2

√

γn n/2



.

(36)
Consequently, substituting (36) into (25) yields,
 
E PB
e


√
√
2
≤ 2(n + 1)κd e−νκ(1−µ)γn n + 2e−µ γn n/2
+ 4M e−(1−ν)(1−µ)γn

√

nD(σ1 kσ0 ) γn2 Tr{σ0−1 σ12 }

e

.

(37)
Hence, if,
√
log M = (1 − ς)γn nD(σ1 kσ0 ),

(38)

where 1 − ς = (1 − ς5 )(1 − µ)(1 − ν) for some constant
ς5 > 0, then, for sufficiently large n there must exist a
constant $ > 0 such that the expected error probability
is upper-bounded as,
√
 
−$γn n
E PB
.
(39)
e ≤e
C. Covertness Analysis
The goal is now to show that the average state that
Willie receives overPn channel
PK usesn when communication
occurs, ρ̄n = M1K M
m=1
k=1 ρ (m, k), is close to the
state he receives when no communication occurs, i.e.,
ρ⊗n
0 . In order to show this, we first prove the following
lemma.
Lemma 6. For sufficiently large n there exists a coding
scheme with
√
log M + log K = (1 + ς)γn nD(ρ1 kρ0 ),
(40)

M X
K
o

 1 X
−1
−
1
ρn (m0 , k 0 ) ρ⊗n
αn
MK 0
0
m =1 k =1

M X
K
n 1 X
 1
= E Tr
ρn (m, k)
ρn (m, k)
MK
MK

1
+
MK

m=1 k=1
M
K
X X


 o
⊗n −1
ρ (m , k ) ραn
−1
0

n

0

m0 =1 k0 =1
(m0 ,k0 )6=(m,k)

n
 1
ρn (x)
= Ex Ex0 Tr ρn (x)
MK
M K − 1 n 0  ⊗n −1 o
+
ρ (x ) ραn
−1
MK
n
 1
ρn (x)
= Ex Tr ρn (x)
MK
M K − 1 ⊗n  ⊗n −1 o
+
ραn ραn
−1
MK
n
o
−1
1
MK − 1
=
+
Ex Tr (ρn (x))2 ρ⊗n
−1
αn
MK
MK
n
o n
−1 o
1
1
−
≤
Ex Tr (ρn (x))2 Tr ρ⊗n
,
αn
MK
MK
(42)
where the inequality is because both (ρn (x))2 and
−1
are positive-definite, and for any positiveρ⊗n
αn
definite matrices A and B we have:
p
Tr{AB} ≤ Tr{A2 } Tr{B 2 }
p
≤ Tr{A}2 Tr{B}2
≤ Tr{A} Tr{B}.

(43)

We upper-bound each trace in (42) in turn. First, let the
ordered sets of eigenvalues of ραn , ρ0 , and ρ1 be denoted
by a1 ≥ a2 ≥ · · · ≥ ad , b1 ≥ b2 ≥ · · · ≥ bd and
c1 ≥ c2 ≥ · · · ≥ cd , respectively. Then,
n
−1 o

Tr ρ⊗n
= n Tr ρ−1
αn
αn
=n

d
X

a−1
i

i=1

≤ nda−1
d

such that,
−ζγn
D(ρ̄n kρ⊗n
αn ) ≤ e

√

n

,

(41)


√n .
where ζ > 0 is a constant and γn = o(1) ∩ ω log
n
Proof. Using Lemma 1 with S = ρ̄n , T = ρ⊗n
αn and
c = 1, the expected quantum relative entropy can be
upper-bounded as:


E D(ρ̄n kρ⊗n
αn )
n
o
−1
≤ Tr (ρ̄n )2 ρ⊗n
−
1
αn
M X
K
n 1 X

ρn (m, k)
= E Tr
MK
m=1 k=1

(a)

≤ nd((1 − αn )bd + αn cd )−1

≤ nd((1 − αn )bd )−1


(b)
2nd
≤
,
(44)
bd
where (a) follows from Weyl’s inequalities for Hermitian
matrices [24] and the fact that ραn = (1 − αn )ρ0 + αn ρ1 ,
while (b) follows from the assumption that n is large
enough for αn < 12 .
To upper-bound the second trace in (42), let us define
the projector
n
o
Υnb = ρn (x) − eb ρ⊗n
(45)
0 ≤0 ,

13

with b > 0 a constant. Then
n
o
Tr (ρn (x))2
n
o
n
o
= Tr (ρn (x))2 Υnb + Tr (ρn (x))2 (I − Υnb ) .
(46)

Let us define the function
n
o
ψ(ρ(xi ), r) = log Tr (ρ(xi ))1+r (ρ0 )−r .
Since ψ(ρ0 , r) = 0, terms with xi = 0 vanish and only
terms with xi = 1 contribute to the summation. Let the
random variable L indicate the number of non-innocent
symbols in x, and, as in the previous section,
√
√
Cµn = {l ∈ N : |l − µγn n| < γn n}.
(51)

In what follows, we find an upper-bound for each term
in the right-hand side of (46).
Applying Lemma 4 with B = ρn (x) and A = ρn (x)− is a set of the values that random variable L takes. Using
eb ρ⊗n
0 yields:
a Chernoff bound, we have:
√
n

n
oo
2
n
b ⊗n
P (L ∈
/ Cµn ) ≤ 2e−µ γn n/2 .
(52)
Ex Tr ρn (x) ρn (x) − eb ρ⊗n
ρ
(x)
−
e
ρ
≤
0
0
0
≤ 0. Hence,
!
n
X
X
p(x) exp −br +
ψ(ρ(xi ), r)
Hence, the expected value of the first term in right-hand
x
i=1
side of (46) can be upper-bounded as:
!
L
n
o
X
X
2 n
n
Ex Tr (ρ (x)) Υb
ψ(ρ1 , r)
= EL
p(x) exp −br +
n
o
x
i=1
n
X
≤ Ex Tr ρn (x)eb ρ⊗n
0 Υb
≤
p(L = l) exp (−br + lψ(ρ1 , r)) + P (L ∈
/ Cµn )
r
n
o
n
o
(a)
2 n
l∈Cµn
Υb
≤ eb Ex Tr (ρn (x))2 Tr ρ⊗n
√

√
0
2
≤ exp −br + (1 + µ)γn nψ(ρ1 , r) + 2e−µ γn n/2 .
r
n
o n
2 o
(53)
≤ eb Ex Tr (ρn (x))2 Tr ρ⊗n
0
∂
ψ(ρ1 , r) is uniformly continuous and
By Appendix C, ∂r
= eb ,
(47) ∂ ψ(ρ1 , 0) = D(σ1 kσ0 ). Let ε > 0 be an arbitrary
∂r
∂
constant.
By the uniform continuity of ∂r
ψ(ρ1 , r), there
where (a) follows from the Cauchy-Schwartz inequality:
exists 0 < κ < 1 such that, for 0 < r ≤ κ, we have:
p
Tr{AB} = Tr{A2 } Tr{B 2 }
ψ(ρ1 , r) − ψ(ρ1 , 0)
− D(ρ1 kρ0 ) < ε,
(54)
r−0
n.
for density operators A = ρn (x) and B = ρ⊗n
Υ
0
b
(53) and (54)
Now consider the second term in the right-hand side where ψ(ρ1 , 0) = 0. Thus, substituting √
n
in
(50)
and
setting
b
=
(1
+
ν)(1
+
µ)γ
n nD (ρ1 kρ0 ),
of (46). Since ρ (x) is positive-definite and unit-trace,
all of its eigenvalues are positive and not greater than where ν > 0 is a constant, we obtain:
one, and, thus,
Ex Tr {ρn (x) (I − Υnb )}
n
o
√
√
2
Tr (ρn (x))2 (I − Υnb ) ≤ Tr {ρn (x) (I − Υnb )} .
≤ e(−κν(1+µ)γn nD(ρ1 kρ0 )) + 2e−µ γn n/2 . (55)
(48) Combining (42)-(54), we have:


In [25, Section 2] it is shown that for any states A
E D(ρ̄n kρ⊗n
αn )


and B and any numbers t > 0 and 0 ≤ r ≤ 1,
√
1
2nd  b
(−κν(1+µ)qγn nD(ρ1 kρ0 ))

≤
e
+
e
MK
bd
Tr {A {A − tB > 0}} ≤ t−r Tr A1+r B −r . (49)

√
−µ2 γn n/2
⊗n
n
+2e
.
(56)
Applying this result with A = ρ (x) and B = ρ0 and
letting t = eb , we obtain
Hence, we should choose
Ex Tr {ρn (x) (I − Υnb )}
X
=
p(x) Tr{ρn (x){ρn (x) − eb ρ0 ⊗n > 0}}
x

≤

X

≤

X

1+r
n
⊗n −r
p(x)e(−br+log Tr{(ρ (x)) (ρ0 ) })

x

x

p(x)e(−br+

Pn
i=1

log Tr{(ρ(xi ))1+r (ρ0 )−r })

. (50)

log M + log K

√
= (1 + ς5 )(1 + ν)(1 + µ)γn nD (ρ1 kρ0 ) ,

(57)

and with this choice of M and K , there exists a constant
ζ > 0 such that for sufficiently large n,
√

−ζγn n
D ρ̄n kρ⊗n
.
(58)
αn ≤ e

14

D. Identification of a Specific Code
We choose ς , ζ and $, M , and K such that both (38)
and (40) are satisfied. In Appendix D we use Markov’s
inequality to show that, for a constants ς1 > 0 and
sufficiently large n, there exists at least one coding
scheme such that:
PB
e

≤e

√
−ς1 γn n

n

and D(ρ̄

kρ⊗n
αn )

√
−ζγn n

≤e

The quantum relative entropy between

ρ̄n

and

.

ρ⊗n
0

(59)
is:

D(ρ̄n kρ⊗n
0 )
⊗n
= D(ρ̄n kρ⊗n
) + D(ρ⊗n
αn kρ0 )
 αnn


⊗n
+ Tr ρ̄ − ρ⊗n
log ρ⊗n
. (60)
αn
αn − log ρ0

To show that the last term in right-hand side of (60)
vanishes as n tends to infinity, let the eigenvalues of
⊗n
⊗n
A = ρ̄n −ρ⊗n
αn and B = log ραn −log ρ0 be enumerated
in decreasing order as ϑ1 ≥ ϑ2 ≥ · · · ≥ ϑd and κ1 ≥
κ2 ≥ · · · ≥ κd , respectively. Then:



⊗n
Tr ρ̄n − ρ⊗n
log ρ⊗n
αn
αn − log ρ0
(a)

≤

d
X

ϑi κi

d
X

≤

! 12

d
X

ϑ2i

! 12
κ2i

,

(61)

where (a) follows from von Neumann’s trace inequality
[26], and (b) follows from the Cauchy-Schwarz inequality. The first summation on the right-hand side of (61)
is upper-bounded as follows:
ϑ2i = Tr

n

ρ̄n − ρ⊗n
αn

2 o

i=1

≤ Tr

q
n

ρ̄n

−

2
ρ⊗n
αn



≤e

√
− ζγn n
1
2

i=1

κ2i

≤

d
X
i=1
d
X

(log (ani ) − log (bnd ))2


ai 2
=
n log
bd
i=1

2
a1
.
≤ n2 d log
bd
2



(63)

Substituting (62) and (63) into (61) yields:



⊗n
Tr ρ̄n − ρ⊗n
log ρ⊗n
αn
αn − log ρ0


√
√
a1
≤ n d log
e−ζγn n/2 .
bd

(64)

Re-arranging (60), substituting (64) and the result of
Lemma 6, and appropriately choosing a constant ς2 > 0
yields:
√

n

.

(65)

Application of Lemma 2 completes the proof of
Theorem 3, the achievability of the SRL for covert
communication over a cq channel.

,

E. Multiple Symbols
The proof of achievability with a single non-innocent
symbol described above can be used mutatis mutandis to
prove achievability with multiple non-innocent symbols.
Following the notation of Section IV-A1, with multiple
non-innocent symbols, the average state at Bob can be
written as:
X
σαn = (1 − αn )σ0 + αn
p̃(x)σx
x∈X \{0}

ρ⊗n
αn 1

= (1 − αn )σ0 + αn σ̃
P
where p̃(.) is defined such that x∈X \{0} p̃(x) = 1, i.e.,

= ρ̄ −
r
(a)

1
≤
D ρ̄n kρ⊗n
αn
2
(b)

d
X

i=1

i=1

d
X

Hence, setting j = 1,

−ς2 γn
⊗n ⊗n
D(ρ̄n kρ⊗n
0 ) − D(ραn kρ0 ) ≤ e

i=1
(b)

− log(bnd ) ≥ · · · ≥ − log(bn2 ) ≥ − log(bn1 ). Using Weyl’s
inequalities [24] we obtain

κi+j−1 ≤ log(ani ) − log bnd−j+1 .

(62)

where (a) follows from the quantum Pinsker’s inequality
[9, Ch. 11] and (b) follows from (59).
To upper-bound the second summation on the righthand side of (61) denote the ordered sets of eigenvalues of ραn and ρ0 by a1 ≥ a2 ≥ · · · ≥ ad
and b1 ≥ b2 ≥ · · · ≥ bd , respectively.
Hence, the

respective eigenvalues of log ρ⊗n
and
−
log
ρ⊗n
are
αn
0
n
n
n
enumerated as log(a1 ) ≥ log(a2 ) ≥ · · · ≥ log(ad ) and

p̃(x) = p(x)
αn , and thus σ̃ is the average non-innocent state
at Bob. Similarly, the average state at Willie is,
ραn = (1 − αn )ρ0 + αn ρ̃,

where ρ̃ is the average non-innocent state at Willie,
X
ρ̃ =
p̃(x)ρx .
x∈X \{0}

By replacing σ1 with σ̃ in (28)-(29), D(σ1 kσ0 ) with
P
x∈X
\{0} p̃(x)D(σx kσ0 ) in (37)-(38), and D(ρ1 kρ0 )
P
with x∈X \{0} p̃(x)D(ρx kρ0 ) in (56)-(57), and making

15

Theorem 4. For any stationary memoryless cq channel
where, ∀u ∈ X , supp(σx ) ⊆ supp(σ0 ) and supp (ρx ) ⊆
supp (ρ0 ) such that ρ0 is not a mixture of 
{ρx }x∈X
 \{0} ,
for n sufficiently large and γn = o(1) ∩ ω
√
log M = (1 − ς)γn n

X

log
√n
n

,

P
=

X

−ς2 γn
D(ρ̄n kρ⊗n
0 ) ≥ nD(ραn kρ0 ) − e

x∈X \{0}

,

−ς1 γn
PB
e ≤e
n


⊗n

D ρ̄ kρ0

n

,

⊗n
− D ρ⊗n
αn kρ0



≤ e−ς2 γn

√

n

,

Now, consider the following lemma which quantifies
the quantum relative entropy between ραn and ρ0 .
Lemma 7. Let A = αC + (1 − α)B , where B and C
are states, and α satisfies 0 ≤ α ≤ min{1, kB −1 (C −
B)k−1 }. Then,

Thus, since γn = o(1) ∩ ω

Theorem 5. For any stationary memoryless cq channel,
where, ∀u ∈ X , supp(σx ) ⊆ supp(σ0 ) and supp (ρx ) ⊆
supp (ρ0 ) such that ρ0 is not a mixture of {ρx }x∈X \{0} ,
there exists a coding scheme such that,

.



√1
n



lim q

n→∞

log M
nD(ρ̄n kρ⊗n
0 )

and,
lim q

n→∞

log K
nD(ρ̄n kρ⊗n
0 )

+
√ P
γn n
p̃(x)((1 + ς)D(ρx kρ0 ) − (1 − ς)D(σx kσ0 ))


lim PB
e = 0,

x∈X
x6=0

=

n→∞

q

2
γn
2
2 χ (ρ̃kρ0 )

+



P

nD ρ̄n kρ0

and,
log K
nD(ρ̄n kρ⊗n
0 )

x∈X \{0} p̃(x)D (σx kσ0 )

q

1 2
2 χ (ρ̃kρ0 )

,

√ P
(1 − ς)γn n x∈X \{0} p̃(x)D(σx kσ0 )
q
=
γn2 2
2 χ (ρ̃kρ0 )
P
(1 − ς) x∈X \{0} p̃(x)D(σx kσ0 )
q
=
,
1 2
χ
(ρ̃kρ
)
0
2

lim D(ρ̄n kρ⊗n
0 ) = 0,

=
⊗n

(66)

Using Theorem 4 and (66),

n→∞

lim q

n

lim D(ρ̄n kρ⊗n
0 ) = 0.

Using Theorem 4 and Lemma 7, it follows that the
following specific scaling coefficients are achievable.

n→∞

,

n→∞

α2 2
D(AkB) =
χ (CkB) + O(α3 ),
2
Proof. See Appendix E.

n→∞

n

αn2 2
χ (ρ̃kρ0 ) + O(nαn3 )
2
 3
γ2
γ
= n χ2 (ρ̃kρ0 ) + O √n
2
n

where ς ∈ (0, 1), ς1 > 0, ς2 > 0, and ς3 > 0 are
constants, and [c]+ = max{c, 0}.

log M

√

D(ρ̄n kρ⊗n
0 )=n


⊗n
D ρ⊗n
≤ ς3 γn2 ,
αn kρ0

lim q

√

Hence, using Lemma 7,

and,
√

1 2
2 χ (ρ̃kρ0 )

−ς2 γn
D(ρ̄n kρ⊗n
0 ) ≤ nD(ραn kρ0 ) + e

p̃(x) (1 + ς)D (ρx kρ0 )

 i+

q

Proof. From (65),

p̃(x)D (σx kσ0 ) ,

− (1 − ς)D (σx kσ0 )

p̃(x) (D (ρx kρ0 ) − D (σx kσ0 ))

x∈X \{0}

where ρ̃ is the average non-innocent state at Willie
induced by p̃(x), and [x]+ = max{x, 0}.

x∈X \{0}

√ h
log K = γn n

#+

"

the required adjustments, we prove the following theorem:

,


=

P

p̃(x)((1 + ς)D(ρx kρ0 ) − (1 − ς)D(σx kσ0 ))

x∈X
x6=0

q

.
1 2
2 χ (ρ̃kρ0 )

Since ς > 0 is arbitrary, the statement of the theorem
follows.

16
n

V. C ONVERSE OF THE SRL FOR CQ CHANNELS

σ̄ =

In this section, we prove that the limiting values of
M and K given in Theorem 1 are optimal for the cq
channels. The proof adapts [6, Section VI] based on [27].
Theorem 6. For any stationary memoryless cq channel
with ∀x ∈ X , supp(σx ) ⊆ supp(σ0 ) and supp (ρx ) ⊆
supp (ρ0 ) such that ρ0 is not a mixture of {ρx }x∈X \{0} ,
if
lim PB
e = 0,

n→∞

lim D(ρ̄n kρ⊗n
0 ) = 0,

and,

(69)

i=1

and (e) follows because Holevo information is concave
in the input distribution. Rearranging (67) we have,
1
log M ≤
(nχ(p̄, σ̄) + 1).
(70)
1 − δn
Generalizing [28, Section 5.2.3] to cq channels, we
obtain:
log M + log K

n→∞

= H(X n )

then,

n

(71)
n

≥ I(X ; ρ̄ )

lim q

n→∞

1X
σ(xi );
n

log M

P

x∈X \{0} p̃(x)D(σx kσ0 )
q
,
1 2
χ
(ρ̃kρ
)
0
2

≤

nD(ρ̄n kρ⊗n
0 )

and,
log M + log K
≥
lim q
n→∞
nD(ρ̄n kρ⊗n
)
0

P

x∈X \{0} p̃(x)D(ρx kρ0 )

q

.

≥ I(X n ; ρ̄n ) + D(ρ̄n kρ⊗n
0 ) − n
= H(ρ̄n ) − H(ρ̄n |X n ) − H(ρ̄n )

− Tr{ρ̄n log ρ⊗n
0 } − n
n
n
X
X
=−
H(ρ(xi )|Xi ) −
Tr{ρ(xi ) log ρ0 } − n
i=1

1 2
2 χ (ρ̃kρ0 )

n ⊗n
Proof. Let us define PB
e ≤ δn and D(ρ̄ kρ0 ) ≤ n
for a length n code, where limn→∞ δn = 0 and
limn→∞ n = 0 are the reliability and covertness criteria,
respectively. Let Y n be the classical random variable
describing the output of the channel at Bob, and S the
random variable describing the pre-shared secret. We
have:

log M = H(W )
= I(W ; Y n S) + H(W |Y n S)

p(u)H(ρ(xi )|Xi = u)

i=1 u∈X
n
X

Tr{ρ(xi ) log ρ0 } − n

i=1

=

n X
X

p(u) [Tr{ρu (xi ) log ρu (xi )}

i=1 u∈X

− Tr{ρu (xi ) log ρ0 }] − n
X
=n
p̄(u) (Tr{ρu log ρu } − Tr{ρu log ρ0 }) − n
≥n

= I(W ; Y n |S) + 1 + δn log M

X

p̄(u) (Tr{ρu log ρu } − Tr{ρu log ρ0 })

u∈X

−n − nD(ρ̄kρ0 )
X
=n
p̄(u) Tr{ρu log ρu } − Tr{ρ̄ log ρ0 }

= I(W S; Y n ) + 1 + δn log M
(b)

≤ I(X n ; Y n ) + 1 + δn log M

u∈X

−n Tr{ρ̄(log ρ̄ − log ρ0 )} − n
X
= −n Tr{ρ̄ log ρ̄} + n
p̄(u) Tr{ρu log ρu } − n

(c)

≤ I(X n ; σ n ) + 1 + δn log M

≤ χ(pX n , σ n ) + 1 + δn log M
n
(d) X
=
χ(pi , σ(xi )) + 1 + δn log M

u∈X

= nχ(p̄, ρ̄) − n ,

i=1
(e)

(67)

where (a) follows from Fano’s inequality; (b) follows
from the data processing inequality; (c) is the Holevo
bound; (d) is due to σ n being a product state; p̄ and σ̄
are defined as follows:
n
1X
p̄(u) =
p(xi = u)
n

−

i=1

n X
X

u∈X

≤ I(W ; Y n S) + 1 + δn log M

≤ nχ(p̄, σ̄) + 1 + δn log M

=−

(b)

(a)

i=1

(a)

(68)

(72)

where (a) follows from the covertness condition
D(ρ̄n kρ⊗n
0 ) ≤ n , ρ̄ is the average output state at Willie,
n

ρ̄ =

1X
ρ(xi ),
n

(73)

X

(74)

i=1

or equivalently,
ρ̄ =

p̄(x)ρx ,

x∈X

and (b) follows because D(ρ̄kρ0 ) ≥ 0.

17

= µn

As in [27],

X

n ≥ D(ρ̄n kρ⊗n
0 )
n
(a) X
D(ρ(xi )kρ0 )
=

− Tr{σµn log σµn }
X
p̃(x)σx + (1 − µn )σ0 ) log σ0 }
+ Tr{(µn

n=1

x∈X
x6=0

(b)

≥ nD(ρ̄kρ0 )

(75)

where (a) follows from the memoryless property of
the channel and (b) follows from the convexity of the
quantum relative entropy. Using the quantum Pinsker’s
inequality,

= µn

(76)

n→∞

(77)

Denote the average probability
of transmitting a nonP
innocent state by µn =
x∈X \{0} p̄(x). Similarly to
(13), the average state induced by p̄(x) at Willie is:
ρ̄ = ρµn = (1 − µn )ρ0 + µn ρ̃,

(78)

where ρ̃ is the average non-innocent state at Willie,
X
p(x)
.
ρ̃ =
p̃(x)ρx , and p̃(x) =
µn
x∈X \{0}

Since we are limited to cq channels, the set of classical
inputs X at Alice maps to a fixed set of output states at
Willie (and Bob). This implies that (77) holds (and thus
from (76) the covertness criterion is maintained) only
when:
lim µn = 0.

n→∞

(79)

− Tr{σµn log σµn } + Tr{σµn log σ0 }
X
p̃(x)D(σx kσ0 ) − D(σµn kσ0 )
= µn
x∈X
x6=0

x∈X \{0}

Expanding the Holevo information of the average state
σ̄ = σµn at Bob we have:
χ(p̄, σµn )

X

p̃(x)H(σx )

x∈X

= − Tr{σµn log σµn } + (1 − µn ) Tr{σ0 log σ0 }
X
+µn
p̃(x) Tr{σx log σx }
x∈X
x6=0

p̃(x)D(σx kσ0 ).

(82)

Similarly, expanding the Holevo information of the average state ρ̄ = ρµn at Willie yields:
X
χ(p̄, ρµn ) = µn
p̃(x)D(ρx kρ0 ) − D(ρµn kρ0 ). (83)
x∈X
x6=0

By Lemma 7 we have:
µ2n 2
χ (ρ̃kρ0 ) + O(µ3n ).
(84)
2
Again, the assumption of a cq channel implies that
Alice’s classical inputs in X are mapped to a fixed set of
output states at Willie, which means that χ2 (ρ̃kρ0 ) > 0.
Thus, the covertness condition in the right-hand side of
(76) can only be maintained by ensuring that
√
lim nµn = 0.
(85)
D(ρµn kρ0 ) ≥

n→∞

From (70) and (82) we have,
X

nµn
p̃(x)D(σx kσ0 ) ≥ nχ(p̄, σµn )
≥ (1 − δn ) log M − 1.

(80)

where σ̃ is the average non-innocent state at Bob,
X
p(x)
.
(81)
σ̃ =
p̃(x)σx , and p̃(x) =
µn

= H(σµn ) −

≤ µn

X

x∈X
x6=0

The state induced by p̄(x) at Bob is
σ̄ = σµn = (1 − µn )σ0 + µn σ̃,

p̃(x) Tr{σx (log σx − log σ0 )}

x∈X
x6=0

Hence, by (76), the covertness criterion implies:
lim ρ̄ = ρ0 .

X
x∈X
x6=0

2

kρ̄ − ρ0 k
n
≤ D(ρ̄kρ0 ) ≤ .
2 log 2
n

p̃(x) Tr{σx (log σx − log σ0 )}

x∈X
x6=0

Since we assume that supp(σx ) ⊆ supp(σ0 ),
P
x∈X \{0} p̃(x)D(σx kσ0 ) < ∞. However, we know that
limn→∞ log M = ∞ is achievable. Thus, we require
lim nµn = ∞.

n→∞

(86)

Now, for n large enough, log M is upper-bounded as
follows:
(a)
nχ(p̄, σµn ) + 1
log M
q
p
≤
(1 − δn ) n2 D(ρµn kρ0 )
nD(ρ̄n kρ⊗n
)
0
P
x∈X p̃(x)D(σx kσ0 ) + 1
(b) nµn
x6=0
q
≤
,
2 2
(1 − δn ) n 2µn χ2 (ρ̃kρ0 )
(87)

18

where (a) follows from (70) and (75), and (b) follows
from (82) and (84). Thus, using (86) and applying the
reliability criteria we obtain:
P
x∈X p̃(x)D(σx kσ0 )
log M
x6=0
q
. (88)
lim q
≤
n→∞
1 2
⊗n
n
χ
(ρ̃kρ
)
nD(ρ̄ kρ0 )
0
2
Recall from Theorem 5 that there exists a sequence of
codes such that
P
x∈X p̃(x)D(σx kσ0 )
log M
x6=0
q
lim q
. (89)
=
n→∞
1 2
⊗n
χ
(ρ̃kρ
)
nD(ρ̄n kρ0 )
0
2
From (70) and (82) we have:
1
(nχ(p̄, σ̄) + 1)
log M ≤
1 − δn
X
1
≤
(nµn
p̃(x)D(σx kσ0 ) + 1)
1 − δn
x∈X

(90)

x6=0

Combining (89) and (90) for arbitrary β > 0 yields:
P
nµn p̃(x)D(σx kσ0 )
u6=0

lim

q

n→∞

nD(ρ̂n kρ⊗n
0 )
P
(1 − β) p̃(x)D(σx kσ0 )
u6=0

≥

q

.

(91)

1 2
2 χ (ρ̃kρ0 )

Now we can find a lower bound for log M + log K ,
log M + log K (a) nχ(p̄, ρ̄) − n
q
≥q
nD(ρ̄n kρ⊗n
)
nD(ρ̄n kρ⊗n
0
0 )
P
nµn p̃(x)D(ρx kρ0 ) − nD(ρµn kρ0 ) − n
(b)

≥

≥

When Bob applies a specific symbol-by-symbol measurement described by POVM {Πy } and observes the
classical output of the channel Y , the channel between
Alice and Bob is classical with transition probability
pY |X (y|x) = Tr{σx Πy }.

q
P

Theorem 7. For any covert communication scenario
when the channel from Alice to Bob is a stationary memoryless classical channel, where, ∀x ∈ X , supp(Px ) ⊆
supp(P0 ) and the channel from Alice to Willie is a cq
channel with ∀x ∈ X , supp(ρx ) ⊆ supp(ρ0 ) such that
ρ0 is not a mixture of {ρx }x∈X \{0} , there exists a coding
scheme such that,
lim D(ρ̄n kρ⊗n
0 ) = 0,

n→∞

lim PB
e = 0,

nD(ρ̄n kρ⊗n
0 )

p̃(x)D(ρx kρ0 ) −

u6=0

q

(96)

This implies that Bob is not able to perform joint
measurement and, thus, the capacity of the classical
channel between Alice and Bob is in general less than
the capacity of the cq channel considered in Sections IV
and V. On the other hand, when Willie is not restricted
to a specific detection scheme, he has a cq channel from
Alice. We aim to show that, if certain conditions are
maintained, the SRL for reliable covert communication
applies to this scenario. Denoting by Px the probability
distribution for the classical output of the channel at
Bob conditioned on Alice transmitting x ∈ X and by
supp(Px ) the support of the distribution Px , we prove
the following theorem:

u6=0

(1 − β)(
(c)

VI. B OB RESTRICTED TO PRODUCT MEASUREMENT

n→∞
1
µn D(ρµn kρ0 )

−

n
nµn )

,
1 2
2 χ (ρ̃kρ0 )

(92)
where (a) follows from (72), (b) follows from (83), and
(c) follows from (91) for any β > 0.
Let us take the limit of right-hand side of (92) as n
tends to ∞. By Lemma 7, we have:
1
µn 2
D(ρµn kρ0 ) = lim
χ (ρ̃kρ0 ) = 0, (93)
lim
n→∞ 2
n→∞ µn
and from (86),
n
lim
= 0.
(94)
n→∞ nµn
Hence, since β > 0 is arbitrary,
P
x∈X p̃(x)D(ρx kρ0 )
log M + log K
x6=0
q
lim q
≥
. (95)
n→∞
1 2
⊗n
n
χ
(ρ̃kρ
)
nD(ρ̄ kρ0 )
0
2

lim q

n→∞

log M
nD(ρ̄n kρ⊗n
0 )

P
=

x∈X \{0} p̃(x)D(Px kP0 )

q

,

1 2
2 χ (ρ̃kρ0 )

and,
lim q

n→∞

log K

nD(ρ̄n kρ⊗n
0 )
hP
i+
x∈X \{0} p̃(x)(D(ρx kρ0 ) − D(Px kP0 ))
q
=
1 2
2 χ (ρ̃kρ0 )

where ρ̃ is the average non-innocent state at Willie
induced by p̃(x), and [c]+ = max{c, 0}.
Proof. First, consider the achievability of the limits
stated in the theorem. For reliability analysis, since the
channel between Alice and Bob is classical, we can
consider a typical set similar to the typical set defined
in [6, Section V] and follow the steps in the proof of

19

[6, Theorem 2]. Since the channel between Alice and
Willie is a cq channel similar to the channel considered
in previous sections of the paper, the covertness analysis
of the achievability is the same as in Section IV-C.
Now we consider the converse. The proof follows the
proof of Theorem 6, and we just mention the necessary
changes here. Denoting by Y n the classical random
variable that describes the output of the channel at Bob,
and applying Fano’s and data processing inequalities as
in (67), we have:
log M = H(W )

+ µn

= −EPµn [log Pµn ]
+ (1 − µn )EP0 [log P0 ] + µn
+ µn

X

p̃(x)EPx [log Px ] − µn

(98)

i=1

and Ȳ is output of the channel between Alice and
Bob induced by X̄ . The last inequality follows from
the concavity of the mutual information in the input
distribution. From (97),
(99)

X

p̃(x)D(Px kP0 ) − D(Pµn kP0 )

x∈X
x6=0

≤ µn

X

p̃(x)D(Px kP0 ).

(102)

x∈X
x6=0

Recalling (83), the Holevo information of the average
state ρ̄ = ρµn is upper bounded by
X
χ(p̄, ρµn ) = µn
p̃(x)D(ρx kρ0 ) − D(ρµn kρ0 ).
x∈X
x6=0

(103)
From (99) and (102) we have,
X

nµn
p̃(x)D(Px kP0 ) ≥ nI(X̄, Ȳ )
x∈X
x6=0

≥ (1 − δn ) log M − 1.

(100)

where, as in Section V, ρ̄ is the average output state at
Willie.
The probability distribution P̄ of Bob’s average output
(induced by the average input distribution p̄(u)) is:
(101)

where P̃ is the average probability distribution of noninnocent symbols at Bob,
X
p̄(x)
.
P̃ =
p̃(x)Px , and p̃(x) =
µn
x∈X \{0}

Expanding the mutual information of the average probability distribution P̄ = Pµn at Bob yields,
X
I(X̄, Ȳ ) = H(Ȳ ) −
p̃(x)H(Ȳ |X̄ = x)
x∈X

= −EPµn [log Pµn ] − (1 − µn )H(Ȳ |X̄ = 0)
X
− µn
p̃(u)H(Ȳ |X̄ = u)
u6=0

= −EPµn [log Pµn ] + (1 − µn )EP0 [log P0 ]

p̃(x)EPx [log P0 ]

= −EPµn [log Pµn ] + EPµn [log P0 ]
X
+ µn
p̃(x)D(Px kP0 )

Repeating the steps of (72), we have,

P̄ = Pµn = (1 − µn )P0 + µn P̃ ,

X
x∈X
x6=0

x∈X
x6=0

(97)

n

log M + log K ≥ nχ(p̄, ρ̄) − n ,

p̃(x)EPx [log P0 ]

x∈X
x6=0

= µn

where X̄ is the average input symbol with distribution,

1
log M ≤
(nI(X̄, Ȳ ) + 1).
1 − δn

X

x∈X
x6=0

≤I(X n ; Y n ) + 1 + δn log M

1X
p(xi = u)
p̄(u) =
n

p̃(x)EPx [log Px ]

x∈X
x6=0

= I(W S; Y n ) + 1 + δn log M
≤nI(X̄, Ȳ ) + 1 + δn log M

X

P

As supp(Px ) ⊆ supp(P0 ), x∈X \{0} p̃(x)D(Px kP0 ) <
∞. Thus, in order for limn→∞ M = ∞, we require
lim nµn = ∞.

n→∞

(104)

For n sufficiently large,
log M
nI(X̄, Ȳ ) + 1
q
p
≤
(1 − δn ) n2 D(ρµn kρ0 )
nD(ρ̄n kρ⊗n
)
0
P
nµn x∈X p̃(x)D(Px kP0 ) + 1
x6=0
q
≤
,
n2 µ2n 2
(1 − δn )
2 χ (ρ̃kρ0 )
(105)
Thus, using (104) and applying the reliability criteria we
obtain
P
x∈X p̃(x)D(Px kP0 )
log M
x6=0
q
lim q
≤
. (106)
n→∞
1 2
⊗n
χ
(ρ̃kρ
)
nD(ρ̄n kρ0 )
0
2
Finally, using the same steps as in Section V yields
P
x∈X p̃(x)D(ρx kρ0 )
log M + log K
x6=0
q
lim q
≥
. (107)
n→∞
1 2
⊗n
n
χ
(ρ̃kρ
)
nD(ρ̄ kρ0 )
0
2

20

√
VII. O( n log n) COVERT COMMUNICATION

+ µn

X

p̃(x) Tr{P0 σx (log σx − log σµn )}

x∈X
x6=0

In Section III-B5 we argue that, if there exists
xs ∈ X \{0} such that supp(σxs ) * supp(σ0 ) and
√
supp(ρxs ) ⊆ supp(ρ0 ), then O( n log n) (δ, )-covert
bits are achievable in n channel uses. We specify a
POVM for Bob that induces a classical DMC and use
[6, Theorem 7] to argue achievability. Here we prove
the converse result, demonstrating that, even when Bob
uses an arbitrary decoding
POVM, it is not possible to
√
convey more than O( n log n) (δ, )-covert bits in n
channel uses.
Since we are interested in the converse, let’s assume
that, for all x ∈ X \{0}, supp(σx ) * supp(σ0 ) and
supp(ρx ) ⊆ supp(ρ0 ). As in the proof of Theorem 6,
n ⊗n
suppose PB
e ≤ δn and D(ρ̄ kρ0 ) ≤ n for a length n
code, where limn→∞ δn = 0 and limn→∞ n = 0 are
the reliability and covertness criteria, respectively. We
can apply the results and notation in (67)-(81) here, as
they do not rely on the supports of the received states at
Bob. However, since supp(σx ) 6⊆ supp(σ0 ), the bound
on the Holevo information of the average state at Bob
in (82) cannot be used. Instead we expand the Holevo
information as follows, denoting the projection into the
support of σ0 as P0 :
χ(p̄, σµn )
= H(σµn ) −

X

p(x)H(σx )

n
o
X
− µn log µn Tr (1 − P0 )
p̃(x)σx
x∈X
x6=0

= (1 − µn ) Tr{P0 σ0 log σ0 }
X
p̃(x) Tr{P0 σx log σx } − Tr{P0 σµn log σµn }
+ µn
x∈X
x6=0

n
o
X
− µn log µn Tr (1 − P0 )
p̃(x)σx
x∈X
x6=0

(a)

= Tr{P0 σµn (log σ0 − log σµn )}
X
p̃(x)D(P0 σx kσ0 )
+ µn
x∈X
x6=0

n
o
X
− µn log µn Tr (1 − P0 )
p̃(x)σx
x∈X
x6=0

(b)

≤ log

X
1
+ µn
p̃(x)D(P0 σx kσ0 ) − κµn log µn
1 − µn
x∈X
x6=0

(108)
where (a)P follows from adding and subtracting
µn Tr P0 x∈X \{0} p̃(x)σx log σ0 , and (b) follows
from the fact that the logarithmic function is operative
monotone, and since quantum states are positive definite,

x∈X

Hence, log M is upper-bounded as,

x∈X
x6=0

n

(1 − µn )σ0 + µn

p̃(x)σx > (1 − µn )σ0 .

x∈X \{0}

= − Tr{σµn log σµn } + (1 − µn ) Tr{σ0 log σ0 }
X
+ µn
p̃(x) Tr{σx log σx }
= − Tr

X

σµn = (1 − µn )σ0 + µn

X


o
p̃(x)σx log σµn

x∈X
x6=0

+ (1 − µn ) Tr{σ0 log σ0 } + µn

X

p̃(x) Tr{σx log σx }

log M

q

nD(ρ̄n kρ⊗n
0 ) log n

(a)

nχ(p̄, σµn ) + 1
p
(1 − δn ) n2 D(ρµn kρ0 ) log n
P
1
log 1−µ
+ µn p̃(x)D(P0 σx kσ0 ) − κµn log µn +
n

≤

x∈X
x6=0

= (1 − µn ) Tr{σ0 (log σ0 − log σµn )}
X
+ µn
p̃(x) Tr{σx (log σx − log σµn )}

(b)

≤

=

− log(1−µn )
µn log n

+

(1 − δn )

q

1
nµn log n

(109)
where (a) is from (70) and (75), and (b) follows from
(108) and (84). Recalling (85) from Section V,

x∈X
x6=0

= (1 − µn ) Tr{P0 σ0 (log σ0 − log σµn )}

+

1 2
2 χ (ρ̃kρ0 )

x∈X
x6=0

+ (1 − µn ) Tr{(1 − P0 )σ0 (log σ0 − log σµn )}
X
+ µn
p̃(x) Tr{(1 − P0 )σx (log σx − log σµn )}

1
n

q

µ2n 2
2 χ (ρ̃kρ0 ) log n
P
p̃(x)D(P0 σx kσ0 )
u6=0
− κµnloglogn µn
log n

(1 − δn )

x∈X
x6=0

= (1 − µn ) Tr{P0 σ0 (log σ0 − log σµn )}
X
+ µn
p̃(x) Tr{P0 σx (log σx − log σµn )}

u6=0

lim

n→∞

√

nµn = 0.

(110)

,

21

Hence, µn can be written as µn = √ιnn where ιn = o(1). the performance (since that is equivalent to transmitting
a randomly chosen pure state from an ensemble and
From (70) and (108) we have,


X
discarding the knowledge of that choice).
1
n log
+ µn
p̃(x)D(P0 σx kσ0 ) − κµn log µn
A TPCP map NAn →W n describes the quantum chan1 − µn
x∈X
nel
from Alice to Willie acting on n channel uses (not
x6=0
necessarily
memorylessly). Thus, the innocent state at
(111)
≥ nχ(p̄, σµn ) ≥ (1 − δn ) log M − 1.
Willie is expressed as ρn0 ≡ NAn →W n (|0ih0|). When
The term κµn log µn is the asymptotically dominant Wm is transmitted, Willie’s hypothesis test reduces to
term on the left-hand side of (111). Thus, in order for discriminating between the states ρn and ρn , where
m
0
limn→∞ M = ∞,
ρnm = NAn →W n (φnm ). Let Willie use a detector that is
√
1
given by the positive operator-valued measure (POVM)
lim nµn log µn = lim nιn ( log n + log ιn−1 ) = ∞,
n→∞
n→∞
{P0n , I − P0n }, where P0n is the projection onto the
2


support of the innocent state ρn0 . Thus, Willie’s average
which requires that ι = ω √n 1log n . Hence, we have
error probability is:


ι = o(1) ∩ ω √n 1log n . Applying this and the reliability
M
1 X
criteria to (109), in the limit as n → ∞,
PW
=
Tr {P0n ρnm } ,
(112)
e
2M
−1
m=1
ι
κ( 12 + limn→∞ log
log M
log n )
q
≤
,
lim q
since messages are sent equiprobably. Note that the error
n→∞
1 2
χ
(ρ̃kρ
)
nD(ρ̄n kρ⊗n
is entirely because of missed codeword detections, as
0
0 ) log n
2
n P
o
Willie’s receiver never raises a false alarm because the
where κ = 1 − Tr P0 x∈X \{0} p̃(x)σx .
support of the innocent state at Willie is a strict subset
of the supports of each of the non-innocent states. Now,
VIII. P ROOF OF T HEOREM 2
Tr {P0n ρnm }
Here we prove that (δ, )-covert communication is
= Tr {P0n NAn →W n (φnm )}
(113)

impossible when there are no input states available



whose supports are contained within the support of the

= Tr P0n NAn →W n |a0 (m)|2 |0ih0|
innocent state at Willie. Unlike other proofs in this


paper, this proof is for a general input state that may be

entangled over n channel uses and a general quantum


X
channel from Alice to Willie NAn →W n that may not
†
0 
b
b
+
a
(m)a
(m)

b
b0
be memoryless across n channel uses. Since this is a


b6=0 or
b0 6=0
converse, to simplify the analysis, we assume that Bob’s
 
channel from Alice is identity. This generalizes the proof


(a)

of [8, Theorem 1] to arbitrary channels.
= Tr P0n |a0 (m)|2 ρn0


Proof. Alice sends one of M (equally likely) log M 

bit messages by choosing an element from an arbi
n

A
X
trary codebook {φm , m = 1, . . . , M }, where a state



†
0
n
n
n
+ NAn →W n 
ab (m)ab0 (m) b b 
A A
A
φm = |ψx i
hψm | encodes a log M -bit message


b6=0 or
An
b0 6=0
Wm . State |ψm i
∈ H is a general pure state for n
n 


o
(b)
channel uses, where H is an infinite-dimensional Hilbert
= Tr P0n |a0 (m)|2 ρn0 + 1 − |a0 (m)|2 ρnm0̄
space corresponding to a single channel use. Denoting


the set of non-negative integers by N0 and a complete
= |a0 (m)|2 + 1 − |a0 (m)|2 (1 − cm ),
(114)
orthonormal basis (CON) ofPH by B = {|bi , b ∈ N0 },
n
n
of TPCP map NAn →W n
we can express |ψm iA = b∈Nn0 ab (m) |biA , where where (a) is by the linearity
n
of ρ0 , (b) follows from the substi|bi ≡ |b1 i ⊗ |b2 i ⊗ · · · ⊗ |bn i is a tensor product of and the definition
n , which is a quantum state that satisfies
An
tution
of
ρ
m0̄ 

n states drawn from CON B . We designate |0i
=
2
2
|0i ⊗ |0i ⊗ · · · ⊗ |0i as the innocent state. As in the |a0 (m)| ρn0 + 1 − |a0 (m)| ρnm0̄ = ρnm and correrest of the paper, for simplicity of notation, we drop sponds to the part of ρnm that is not an innocent state.
n
the system label superscripts, i.e., we denote |biA by Since part of the support of ρnm is outside the support
|bi. We limit our analysis to pure input states since, by of the innocent state ρn0 , part of the support of ρnm0̄
convexity, using mixed states as inputs can only degrade has to lie outside the innocent state support. Thus, in

22


(114) we denote by cm = Tr (I − P n )ρnm0̄ > 0
the constant corresponding to the “amount” of support
that ρnm0̄ has outside of the innocent state support. Let
cmin = minm cm , and note that cmin > 0. This yields an
upper-bound for (112):
!
M
X
1
c
1
min
2
1−
|a0 (m)| .
−
PW
e ≤
2
2
M
m=1

1
2

PW
e

Thus, to ensure
≥ − , Alice must use a codebook
with the probability of transmitting the innocent state:
M
1 X
2
.
|a0 (m)|2 ≥ 1 −
M
cmin

(115)

m=1

Equation (115) can be restated as an upper bound on
the probability of transmitting one or more non-innocent
states:
M

1 X
2
1 − |a0 (m)|2 ≤
.
(116)
M
cmin
m=1

Now we show that there exists an interval (0, 0 ], 0 > 0
such that if  ∈ (0, 0 ], Bob’s average decoding error
probability PB
e ≥ 0 where 0 > 0, thus making covert
communication over a pure-loss channel unreliable.
Analysis of Bob’s decoding error follows that in the
proof of [8, Theorem 1] with minor substitutions. Denote
by Em→l the event that the transmitted message Wm
is decoded by Bob as Wv 6= Wm . Given that Wm
is transmitted, the decoding error probability is the
probability of the union of events ∪M
l=0,l6=m Em→l . Let
Bob choose a POVM {Λ∗j } that minimizes the average
probability of error over n channel uses:
M

1 X
P ∪M
l=0,l6=m Em→l .
{Λj } M

PB
e = inf

(117)

m=1

Now consider a codebook that meets the necessary condition for covert communication given in equation (116).
Define
{φnm , u ∈ A} where
n the subset of this codebook
o
4
. We lower-bound (117)
A = u : 1 − |a0 (m)|2 ≤ cmin
as follows:

1 X
P ∪M
PB
=
e
l=0,l6=m Em→l
M
u∈Ā

1 X
+
P ∪M
(118)
l=0,l6=m Em→l
M
u∈A

1 X
≥
P ∪M
(119)
l=0,l6=m Em→l ,
M
u∈A

where the probabilities in equation (118) are with respect
to the POVM {Λ∗j } that minimizes equation (117) over
the entire codebook. Without loss of generality, let’s

assume that |A| is even, and split A into two equalsized non-overlapping subsets A(left) and A(right) (formally, A(left) ∪ A(right) = A, A(left) ∩ A(right) = ∅, and
|A(left) | = |A(right) |). Let g : A(left) → A(right) be a
bijection. We can thus re-write (119):

 
M
P
∪
E
l=0,l6=m m→l
1 X
PB
2
e ≥
M
2
u∈A(left)


M
P ∪l=0,l6=g(m) Eg(m)→l

+
2
!

P Eg(m)→m
P Em→g(m)
1 X
≥
,
2
+
M
2
2
(left)
u∈A

(120)
where the second lower bound is because the events
Em→g(m) and Eg(m)→m are contained in the unions
M
∪M
l=0,l6=m Em→l and ∪l=0,l6=g(m) Eg(m)→l , respectively.
The summation term in equation (120),


P Em→g(m)
P Eg(m)→m
Pe (m) ≡
+
,
(121)
2
2
is Bob’s average probability of error when Alice only
sends messages Wm and Wg(m) equiprobably. We thus
reduce the analytically intractable problem of discriminating between many states in equation (117) to a
quantum binary hypothesis test.
The lower bound on the probability of error in discriminating two received codewords is obtained by lowerbounding the probability of error in discriminating two
codewords before they are sent (this is equivalent to
Bob having an unattenuated unity-transmissivity channel from Alice). Recalling that φnm = |ψm ihψm | and
φng(m) = ψg(m) ψg(m) are pure states, the lower bound
on the probability of error in discriminating between
|ψm i and ψg(m) is [18, Ch. IV.2 (c), Eq. (2.34)]:


q

Pe (m) ≥ 1 − 1 − F |ψm i , ψg(m)
2 , (122)
where F (|ψi , |φi) = | hψ|φi |2 is the fidelity between the pure states |ψi and |φi. Lower-bounding
F |ψm i , ψg(m) lower-bounds the RHS of equation
(122). For pure states |ψi
2 and |φi, F (|ψi , |φi) = 1 −
1
2 k |ψi hψ| − |φi hφ| k1 , where kρ − σk1 is the trace
distance [9, Equation (9.134)]. Thus,

F |ψm i , ψg(m)

2
1 n
n
=1−
kφ − φg(m) k1
2 m
!2
n
kφnm − |0ih0| k1 kφg(m) − |0ih0| k1
≥1−
+
2
2

23

=1−

q

2

1 − |h0|ψm i| +

q

1−

0 ψg(m)

2

2
,

(123)
where the inequality is from the triangle inequality for
trace distance. Substituting (123) into (122) yields:
q
q
2
1 − 1 − |h0|ψm i|2 − 1 − 0 ψg(m)
.
Pe (m) ≥
2
(124)
Since |h0|ψm i|2 = |a0 (m)|2 and, by the construction of
4
4
A, 1 − |a0 (m)|2 ≤ cmin
and 1 − |a0 (g(m))|2 ≤ cmin
, we
have:
r
1

Pe (m) ≥ − 2
.
(125)
2
cmin
Recalling the definition of Pe (m) in equation (121), we
substitute (125) into (120) to obtain:


r
|A| 1

B
Pe ≥
−2
,
(126)
M 2
cmin
Now, re-stating the condition for covert communication
(116) yields:

1 X
2
≥
1 − |a0 (m)|2
cmin
M
u∈A

≥

(M − |A|) 4
M
cmin

(127)

4
for
with inequality (127) because 1 − |a0 (m)|2 > cmin
all codewords in A by the construction of A. Solving
inequality in (127) for |A|
M yields the lower bound on the
fraction of the codewords in A,

|A|
1
≥ .
(128)
M
2
Combining equations (126) and (128) results in a positive lower bound
q on Bob’s probability of decoding error
cmin
1

PB
≥
−
and any n, and
e
4
cmin for  ∈ 0, 16
demonstrates that (δ, )-covert communication when the
support of the innocent state at Willie is a strict subset
of the supports of each of the non-innocent states is
impossible.

IX. D ISCUSSION
In this section we put our results in the context
of research in quantum-secure covert communication.
Theorem 3 proves the achievability of the square root
scaling law for covert communication over an arbitrarily non-trivial memoryless quantum channel. This
is true notwithstanding the restriction to a specific set
of the input states imposed by our classical-quantum
channel model. Achievability shows a lower bound on

the covert communication performance, as relaxing the
classical-quantum channel restriction and allowing Alice
to choose arbitrary codewords from the entire n-fold
d-dimensional Hilbert space H⊗n could only improve
the system. However, the extent of such improvement
is an important open problem that is outside the scope
of this work. Even showing the square root scaling law
for arbitrary non-trivial quantum channels is an open
challenge. Our converse in Theorem 6 is limited to
classical-quantum channels. In fact, the assumption that
Alice’s set of input classical states maps to a set of fixed
quantum states, which in turn maps to a set of fixed
output states at Bob and Willie plays a critical role in
its proof: meeting the covertness criterion in this setting
requires that the fraction µn of non-innocent
states in an
√
n-state codeword scales as µn = O(1/ n). This greatly
simplifies the proof of the converse. This assumption
can be slightly relaxed by allowing Alice to vary a set
of input states with n. This implies that Alice could
meet the covertness criteria without ever transmitting
the innocent state by using states that get progressively
closer (in relative entropy or trace norm) to the innocent
state. However, even this small change complicates the
analysis, precluding our proof from proceeding. That
being said, a general converse for the square root law
that allows the use of arbitrary codewords from H⊗n has
been proven for the bosonic channel [8, Theorem 5]. We
conjecture that the square root scaling indeed holds for
all non-trivial quantum channels.
ACKNOWLEDGMENT
The authors thank Mark M. Wilde for pointing out
[20], a lemma from which was instrumental to proving
the main result of this paper.
R EFERENCES
[1] A. Sheikholeslami, B. A. Bash, D. Towsley, D. Goeckel, and
S. Guha, “Covert communication over classical-quantum channels,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT), 2016,
pp. 2064–2068.
[2] B. A. Bash, D. Goeckel, and D. Towsley, “Square root law for
communication with low probability of detection on AWGN
channels,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT),
Cambridge, MA, Jul. 2012.
[3] B. Bash, D. Goeckel, and D. Towsley, “Limits of reliable
communication with low probability of detection on AWGN
channels,” IEEE J. Select. Areas Commun., vol. 31, no. 9, pp.
1921–1930, 2013.
[4] P. H. Che, M. Bakshi, and S. Jaggi, “Reliable deniable
communication: Hiding messages in noise,” in Proc. IEEE
Int. Symp. Inform. Theory (ISIT), Istanbul, Turkey, Jul. 2013,
arXiv:1304.6693.
[5] L. Wang, G. W. Wornell, and L. Zheng, “Limits of lowprobability-of-detection communication over a discrete memoryless channel,” in Proc. IEEE Int. Symp. Inform. Theory (ISIT),
2015, pp. 2525–2529.

24

[6] M. R. Bloch, “Covert communication over noisy channels: A
resolvability perspective,” IEEE Trans. Inf. Theory, vol. 62,
no. 5, pp. 2334–2354, 2016.
[7] B. A. Bash, D. Goeckel, S. Guha, and D. Towsley, “Hiding
information in noise: Fundamental limits of covert wireless
communication,” IEEE Commun. Mag., vol. 53, no. 12, 2015.
[8] B. A. Bash, A. H. Gheorghe, M. Patel, J. L. Habif, D. Goeckel,
D. Towsley, and S. Guha, “Quantum-secure covert communication on bosonic channels,” Nature Commun., vol. 6, 2015.
[9] M. M. Wilde, Quantum information theory. Cambridge Univ.
Press, 2013, arXiv:1106.1445v5 [quant-ph].
[10] A. S. Holevo, Quantum Systems, Channels, Information: A
Mathematical Introduction. Berlin, Boston: De Gruyter, 2012.
[11] M. A. Nielsen and I. L. Chuang, Quantum Computation and
Quantum Information.
New York, NY, USA: Cambridge
University Press, 2000.
[12] A. Holevo, “The capacity of quantum channel with general
signal states,” IEEE Trans. Inf. Theory, vol. 44, 1998.
[13] B. Schumacher and M. D. Westmoreland, “Sending classical
information via noisy quantum channels,” Phys. Rev. A, vol. 56,
p. 131, 1997.
[14] M. Takeoka and S. Guha, “Capacity of optical communication
in loss and noise with general quantum Gaussian receivers,”
Phys. Rev. A, vol. 89, no. 4, p. 042309, 2014.
[15] V. Giovannetti, R. Garcı́a-Patrón, N. Cerf, and A. Holevo,
“Ultimate classical communication rates of quantum optical
channels,” Nature Photonics, vol. 8, no. 10, pp. 796–800, 2014.
[16] S. Guha, “Classical capacity of the free-space quantum-optical
channel,” Master’s thesis, Massachusetts Institute of Technology, 2004.
[17] C. W. Helstrom, “Quantum detection and estimation theory,” J.
Stat. Phys., vol. 1, no. 2, pp. 231–252, 1969.
[18] ——, Quantum detection and estimation theory. Academic
press, 1976.
[19] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
Introduction to Algorithms, 2nd ed. Cambridge, Massachusetts:
MIT Press, 2001.
[20] M. Ruskai and F. H. Stillinger, “Convexity inequalities for
estimating free energy and relative entropy,” J. Phys. A, vol. 23,
no. 12, p. 2421, 1990.
[21] K. Temme, M. J. Kastoryano, M. Ruskai, M. M. Wolf, and
F. Verstraete, “The χ2-divergence and mixing times of quantum
Markov processes,” J. Math. Phys., vol. 51, no. 12, p. 122201,
2010.
[22] M. Hayashi and H. Nagaoka, “General formulas for capacity of
classical-quantum channels,” IEEE Trans. Inf. Theory, vol. 49,
no. 7, pp. 1753–1768, 2003.
[23] T. Ogawa and M. Hayashi, “On error exponents in quantum
hypothesis testing,” IEEE Trans. Inf. Theory, vol. 50, no. 6, pp.
1368–1372, 2004.
[24] R. Bhatia, “Linear algebra to quantum cohomology: the story of
Alfred Horn’s inequalities,” Amer. Math. Monthly, pp. 289–318,
2001.
[25] T. Ogawa and H. Nagaoka, “Strong converse and Stein’s
lemma in quantum hypothesis testing,” IEEE Trans. Inf. Theory,
vol. 46, no. 7, pp. 2428–2433, 2000.
[26] L. Mirsky, “A trace inequality of John von Neumann,” Monatsh.
für Math., vol. 79, no. 4, pp. 303–306, 1975.
[27] L. Wang, “Optimal throughput for covert communication over
a classical-quantum channel,” arXiv:1603.05823, 2016.
[28] J. Hou et al., “Coding for relay networks and effective secrecy for wire-tap channels,” Ph.D. dissertation, Univ. der TU
München, 2014.
[29] D. Petz, “Quasi-entropies for finite quantum systems,” Rep.
math. phys., vol. 23, no. 1, pp. 57–65, 1986.

A PPENDIX A
D EFINITION OF THE P INCHING M AP
In this section we briefly define the pinching of an
operator.PLet spectral decomposition of an operator A
A
be A = ni=1
λi Ei , where nA is the number of distinct
eigenvalues of A, and Ei are the projectors onto their
corresponding eigenspaces. The following map is called
the pinching [23]:
EA : B → EA (B) =

nA
X

Ei BEi

(129)

i=1

Some of the properties of pinching of an operator that
we use are:
1) EA (B) commutes with A.
2) For any operator C commuting with A, Tr{BC} =
Tr{EA (B)C}.
A PPENDIX B
P ROOF OF L EMMA 4
In this section we present the proof of Lemma 4.
Consider the spectral decompositions of A and B ,
X
X
A=
λi |ai ihai | , and, B =
µj |bj ihbj | ,
i

j

where µj > 0 because B is positive-definite. Hence,



X
X
µj |bj ihbj |
λi |ai ihai |
Tr{BA {A < 0}}= Tr


j
i:λi <0
X X
=
µj λi | hai |bi i |2 ≤ 0.
j

i:λi <0

The second inequality in the lemma (equation 22) follows by replacing λi < 0 with λi > 0 and applying the
same reasoning.
A PPENDIX C
D ERIVATIVES
In this section, we evaluate the matrix derivatives used
in Section IV-B and Section IV-C. First, note for matrices
A and B and scalars x and c,
∂ cx log A
∂ cx
A =
e
= c(log A)Acx .
(130)
∂x
∂x
Now, consider the matrix derivative in Section IV-B.
n
o
∂
∂
r/2
r/2
ϕ(σ1 , r) =
− log Tr σ1 σ0 σ1−r σ0
∂r
∂r
n
o
r/2 −r r/2
∂
Tr
σ
σ
σ
σ
1 0
1
0
∂r
n
o .
=−
(131)
r/2
r/2
Tr σ1 σ0 σ1−r σ0

25

We have,

A PPENDIX D

∂ x −x x
B2A B2
∂x 



x
x
x
∂ x
∂ −x
=
B 2 A−x B 2 + B 2
A
B2
∂x
∂x


x
∂ x
+ B 2 A−x
B2
∂x
x
x
x
x
1
= (log B)B 2 A−x B 2 − B 2 (log A)A−x B 2
2
x
1 x
(132)
+ B 2 A−x (log B)B 2 .
2
Applying this to (131) with A = σ1 , B = σ0 , and x = r
yields,

Suppose that we choose δ , ζ and $, M , and K such
that,
−$γn
E[PB
e ]≤e

√

n

,

(138)

and,
−ζγn
E[D(ρ̄n kρ⊗n
αn )] ≤ e

√

n

.

(139)

Thus, for sufficiently large n and any 1 > 0 and 2 > 0
there exists at least one coding scheme such that,

n
p PB
e < 1 ∩ D(ρ̄ kραn ) < 2
n
≥ 1 − p(PB
e < 1 ) − p(D(ρ̄ kραn ) < 2 )
√

√

∂
(a)
e−$γn n e−ζγn n
ϕ(σ1 , r) =
≥1−
−
,
(140)
∂rn
1
2

o
 r
r
r
r
r
r
Tr σ1−rσ02 σ1 σ02 log σ1 − 12 σ02 σ1−r σ02 σ1 +σ02 σ1 σ02 σ1−r log σ0
n
o
, where (a) is from Markov’s inequality. Thus, for any
r/2
r/2
ς1 < $ and ς3 < ζ ,
Tr σ1 σ0 σ1−r σ0

√
√ 
(133)
p PB < e−ς1 γn n ∩ D(ρ̄n kρ ) < e−ς3 γn n

which is uniformly continuous with respect to r ∈ [0, 1],
and we have,
∂
ϕ(σ1 , 0) = D(σ1 kσ0 ).
∂r
Next, consider the matrix derivative in Section IV-C,
∂
∂
−r
ψ(ρ1 , r) =
log Tr{ρ1+r
1 ρ0 }
∂r
∂r
−r
∂
Tr{ρ1+r
1 ρ0 }
= ∂r
.
−r
Tr{ρ1+r
1 ρ0 }

αn

e

≥1−e

√
−($−ς1 )γn n

− e−(ζ−ς3 )γn

√

n

→ 1 as n → ∞.

(141)

A PPENDIX E
P ROOF OF L EMMA 7
First recall from Lemma 1 that, for any quantum states
A and B , and a real number c > 0,

(134)

We have,

 

∂ 1+x −x
∂ −x
∂ 1+x
A
B = A1+x
B
+
A
B −x
∂x
∂x
∂x
= A1+x (− log B)B −x + A(log A)Ax B −x .
(135)

Applying this to (134) with A = ρ1 , B = ρ0 , and x = r
yields,
−r
r −r
Tr{ρ1+r
∂
1 (− log ρ0 )ρ0 +ρ1 (log ρ1 )ρ1 ρ0 }
ψ(ρ1 , r)=
−r
∂r
Tr{ρ1+r
1 ρ0 }
1+r
Tr{ρ−r
0 ρ1 (log ρ1 − log ρ0 )}
=
,
(136)
−r
Tr{ρ1+r
1 ρ0 }

which is uniformly continuous with respect to r ∈ [0, 1],
and we have,
∂
ψ(ρ1 , 0) = D(ρ1 kρ0 ).
(137)
∂r
The development of (134)-(137) is known as the convergence of the Rényi relative entropy to the quantum
relative entropy [29].

1
Tr{A − A1−c B c }
(142)
c
1 
D(AkB) ≤ Tr A1+c B −c − A .
(143)
c
Let X be a Hermitian matrix, I an identity matrix, and
r a real number. Provided that kXk ≤ 1, where k.k is
any submultiplicative norm (e.g., trace norm), we have,
∞  
X
r
r
(I + X) =
Xi
(144)
i
D(AkB) ≥

i=0

We have A = αC+(1−α)B = B+α(C−B), where 0 ≤
α ≤ 1 to make A a quantum state. By (143), D(AkB)
can be upper-bounded as follows:
D(AkB) ≤ c−1 (Tr{(B + α(C − B))1+c B −c } − 1)
= c−1 (Tr{B 1+c (I + αB −1 (C − B))1+c B −c } − 1)

∞ 
X
1+c
(a) −1
= c (Tr{B
(αB −1 (C − B))i } − 1)
i
i=0

∞ 
X
1+c i
−1
=c (
α Tr{B(B −1 (C − B))i } − 1)
i
i=0

−1

=c

(Tr{B} + (1 + c)α Tr{(C − B)}

26

(1 + c)c 2
α Tr{(C − B)2 B −1 }
2
(1 + c)c(−1 + c) 3
+
α Tr{B(B −1 (C − B))3 }
6

∞ 
X
1+c i
+
α Tr{B(B −1 (C − B))i } − 1)
i

+

i=4

=

(1 + c) 2
α Tr{(C − B)2 B −1 }
2
(1 − c2 ) 3
−
α Tr{B(B −1 (C − B))3 }
6

∞ 
X
1+c i
−1
+c
α Tr{B(B −1 (C − B))i } (145)
i
i=4

where (a) follows from (144) when α ≤ kB −1 (C −
B)k−1 .
By (142), D(AkB) can be lower-bounded as follows:
D(AkB) ≥ c−1 Tr{A − (B + α(C − B))1−c B c }

∞ 
X
1 − c i 1−c −1
(a) −1
= c (1 − Tr{
α B (B (C − B))i B c })
i
i=0

∞ 
X
1−c i
−1
= c (1 −
α Tr{B(B −1 (C − B))i })
i
i=0

−1

(1 − Tr{B} − (1 − c)α Tr{(C − B)}
(1 − c)(−c) 2
α Tr{B −1 (C − B)2 }
−
2
(1 − c)(−c)(−1 − c) 3
α Tr{B(B −1 (C − B))3 }
−
6

∞ 
X
1−c i
−
α Tr{B(B −1 (C − B))i })
i

=c

i=4

(1 − c) 2
=
α Tr{(C − B)2 B −1 }
2
1 − c2 3
−
α Tr{B(B −1 (C − B))3 }
6

∞ 
X
1−c i
−1
−c
α Tr{B(B −1 (C − B))i } (146)
i
i=4

where again (a) follows from (144) when α ≤ kB −1 (C−
B)k−1 .
By (145) and (146) we have:
D(AkB) ≤

(1 + c) 2
α Tr{(C − B)2 B −1 } + O(α3 )
2

and,
(1 − c) 2
α Tr{(C − B)2 B −1 } + O(α3 ).
2
Since c > 0 is arbitrary, we conclude:
D(AkB) ≥

α2
Tr{(C − B)2 B −1 } + O(α3 ).
2
for 0 ≤ α ≤ min{1, kB −1 (C − B)k−1 }.
D(AkB) =

