arXiv:1802.07795v1 [quant-ph] 21 Feb 2018

Communication Complexity of One-Shot Remote
State Preparation ∗
Shima Bab Hadiashar
U. Waterloo

†

Ashwin Nayak
U. Waterloo

‡

Renato Renner
ETH Zurich

§

Abstract
Quantum teleportation uses prior shared entanglement and classical communication to send an unknown quantum state from one party to another. Remote state preparation (RSP) is a similar distributed
task in which the sender knows the entire classical description of the state to be sent. (This may also be
viewed as the task of non-oblivious compression of a single sample from an ensemble of quantum states.)
We study the communication complexity of approximate remote state preparation, in which the goal is
to prepare an approximation of the desired quantum state.
Jain [Quant. Inf. & Comp., 2006] showed that the worst-case communication complexity of approximate RSP can be bounded from above in terms of the maximum possible information in an encoding.
He also showed that this quantity is a lower bound for communication complexity of (exact) remote
state preparation. In this work, we tightly characterize the worst-case and average-case communication
complexity of remote state preparation in terms of non-asymptotic information-theoretic quantities.
We also show that the average-case communication complexity of RSP can be much smaller than the
worst-case one. In the process, we show that n bits cannot be communicated with less than n transmitted
bits in LOCC protocols. This strengthens a result due to Nayak and Salzman [J. ACM, 2006] and may
be of independent interest.

1

Introduction

Quantum teleportation [3] is an archetypical protocol in information processing that is impossible in the
absence of quantum resources like shared entanglement. Through quantum teleportation, one party is able
to communicate an arbitrary qubit state to another party using only two classical bits of communication
and a previously shared maximally entangled pair of qubits. The two classical bits of communication and
a maximally entangled pair of qubits are both necessary and sufficient for the task. This is a remarkable
phenomenon, as the entire classical description of the state being communicated is potentially infinite in
length.
In Ref. [33], Lo introduced a similar distributed task in which the sender (called Alice in the literature) knows
a classical description of the quantum state. This task is called remote state preparation (RSP). In particular,
remote state preparation is a task involving two parties, Alice and Bob, who share qubits in an entangled
∗ Much

of the work in this article was reported in S.B.’s Master’s thesis [2].
of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo, 200
University Ave. W., Waterloo, ON, N2L 3G1, Canada. Email: sbabhadi@uwaterloo.ca . Research supported in part by
NSERC Canada.
‡ Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo, 200
University Ave. W., Waterloo, ON, N2L 3G1, Canada. Email: ashwin.nayak@uwaterloo.ca . Research supported in part by
NSERC Canada.
§ Institute for Theoretical Physics, ETH Zurich, Wolfgang-Pauli-Str. 27, 8093 Zurich, Switzerland.
Email:
renner@itp.phys.ethz.ch .
† Department

1

state. Alice is given the description of a state, Q(x), chosen from a subset of quantum states {Q(1), . . . , Q(n)},
and their goal is to prepare that quantum state on Bob’s side using only local operations and classical
communication (LOCC). This may also be viewed as the task of compression (which is non-oblivious at the
sender’s end), of a single sample from an ensemble of quantum states with entanglement-assisted classical
communication.
We say an RSP protocol is oblivious to Bob if he can get no more information about the prepared state
than what is contained in a single copy of the state [32]. A relaxed version of RSP is approximate remote state preparation (ARSP) in which we wish to prepare an approximation σx of the specified quantum state Q(x). We define the error of a protocol for approximate remote state preparation in terms of
the fidelity between Q(x)√and σx . We say a protocol has worst-case error at most ǫ, if for every x ∈
− ǫ2 . Similarly, a protocol
{1, . . . , n}, F(Q(x), σx ) ≥ 1P
√ has average-case error at most ǫ with respect to a
n
probability distribution p, if x=1 px F(Q(x), σx ) ≥ 1 − ǫ2 .

Lo [33] gave several examples of ensembles which can be remotely prepared using a one-way communication
protocol with classical communication cost less than that in quantum teleportation. However, he conjectured
that to prepare arbitrary pure n-qubit states remotely, Alice has to necessarily send the same number of
classical bits as in quantum teleportation i.e., 2n classical bits. The task has been studied extensively since
then, largely in the asymptotic setting.
Bennett et al. [4] showed that in the presence of a large amount of shared entanglement, Alice can prepare
general quantum states on Bob’s side with the asymptotic classical communication rate of one bit per qubit.
This amount of classical communication from Alice to Bob is also necessary by causality [33]. They also
showed that unlike for quantum teleportation, there is a trade-off between the communication cost and
the amount of entanglement in remote state preparation. In particular, they proved that at the cost of
using more entanglement, the communication cost of preparing a one-qubit state ranges from one bit in the
high entanglement limit to an infinite number of bits in the case of no previously shared entanglement. In
addition, they suggested that the Lo conjecture is true in a more restricted setting, such as when the protocol
is faithful and oblivious to Bob [4]. (A protocol is said to be faithful if it is exact and deterministic.)

Devetak and Berger [17] found an analytic expression for the trade-off curve between the shared entanglement
and classical communication of teleportation based RSP protocols in the low-entanglement region (less than 1
singlet state per qubit). They conjectured that teleportation based protocols are optimal among all lowentanglement protocols. Later, Leung and Shor [32] proved the Lo conjecture for a special case. They
proved that if a one-way RSP protocol for a generic ensemble of pure states is faithful and oblivious to Bob,
then it necessarily uses at least as much classical communication as in teleportation. (A generic ensemble
is an ensemble of states whose density matrices span the operators in the input Hilbert space.) Hayashi,
Hashimoto and Horibe [21] showed that in order to remotely prepare one qubit in an arbitrary state using
a one-way faithful, but not necessarily oblivious protocol, Alice requires two classical bits of communication
as in teleportation.
Berry and Sanders [7] studied ARSP, the approximation variant of RSP, of an ensemble E of mixed states
(which might be entangled with some other system on Alice’s part) such that their entanglement with
other systems does not change significantly. They showed that approximate remote state preparation with
arbitrary small average-case error ǫ can be done asymptotically using communication per prepared state
arbitrarily close to the Holevo information χ(E ) of the ensemble. (See Section 2.4 for a definition of Holevo
information.) Later Bennett, Hayden, Leung, Shor, and Winter [6] proved that approximate remote state
preparation with small worst-case error ǫ requires an asymptotic rate of one bit of classical communication
per qubit from Alice to Bob. They also showed that this amount of classical communication is sufficient.
Moreover, they derived the exact trade-off curve between shared entangled bits and classical communication
bits for an arbitrary ensemble of candidate states.
Jain [25] studied remote state preparation in the one-shot scenario. He considered the total communication
cost when given access to an arbitrary amount of entanglement. He showed that the communication cost
required for exact remote state preparation is at least T(Q)/2 and ARSP with worst-case error at most ǫ can
2

Protocol Type
Faithful RSP [4]

Faithful RSP [21]
Faithful and
oblivious RSP [32]
ARSP with small
average-case
error [7]
ARSP with small
worst-case error [6]
Exact RSP [25]
ARSP with
worst-case error
ǫ [25]

Conditions
an arbitrary state,
one-way communication,
in asymptotics
one pure qubit in a
general state,
one-way communication
a generic ensemble of
pure states,
one-way communication
an ensemble E of mixed
states preserving their
entanglement,
one-way communication,
in asymptotics
an arbitrary pure state,
two-way communication,
in asymptotics
an arbitrary state,
two-way communication,
in one-shot scenario
an arbitrary state,
one-way communication,
in one-shot scenario

Entanglement

Classical Communication

high entanglement

= 1 classical bit per qubit

= 1 ebit(singlet)
per qubit

= 2 classical bit

= 1 ebit(singlet)
per qubit

= 2 classical bit per qubit

no limit

≈ χ(E ) classical bits per
prepared state

= 1 ebit(singlet)
per qubit

= 1 classical bit per qubit
from Alice to Bob

no limit

≥ T(Q)/2

no limit

≤

(1−

√

8
2 (4T(Q)
1−ǫ2 )

+ 7)

Table 1: A summary of previous works on communication cost of Remote State Preparation
8
√
2 (4T(Q) + 7), where T(Q) denotes the maximum
(1− 1−ǫ2 )
possible information in an encoding Q. (A precise definition can be found in Section 2.4.)

be accomplished with communication at most

These abovementioned results on remote state preparation are summarized in Table 1 .

1.1

Our results

Intuitively, relaxing the remote state preparation problem so that Bob produces some approximation to the
ideal state should lower the communication complexity of the task. This suggests that the bounds provided
by Jain [25] are not tight.
In this work, we characterize the communication complexity of remote state preparation in two different
cases. First, we consider ARSP with average-case error at most ǫ, and bound its communication complexity
by the smooth max-information Bob has about Alice’s input. (See Section 2.4 for a precise definition of this
quantity.) Then we consider ARSP with worst-case error at most ǫ, and give lower and upper bounds for
its communication complexity in terms of smooth max-relative entropy and show that these bounds may be
arbitrarily tighter than that in Ref. [25].
Our main results about the remote state preparation problem are summarized below, using notions introduced in Section
√ 2. Recall that a protocol has worst-case error at most ǫ, if for every x ∈ {1, . . . , n},
F(Q(x), σx ) ≥ P1 − ǫ2 , and a protocol√has average-case error at most ǫ with respect to a probability distribution p, if nx=1 px F(Q(x), σx ) ≥ 1 − ǫ2 . We denote the average-case communication complexity of
ARSP by Q∗p (RSP(S, Q), ǫ), and the worst-case communication complexity of ARSP by Q∗ (RSP(S, Q), ǫ).

3

Theorem 1.1. For any finite set S, and set of quantum states {Q(x) : x ∈ S},
P let p be a probability
distribution over S and ρAB (p) ∈ D(H′ ⊗H) be the bipartite quantum state ρAB (p) = x∈S px |xihx|A ⊗Q(x)B .
Then
1. For any fixed ǫ ∈ (0, 1], we have
Iǫmax (A : B)ρ(p)

≤

Q∗p (RSP(S, Q), ǫ)

≤

ǫ
√

2 2
Imax
(A : B)ρ(p) + f (ǫ) ,

where f (ǫ) ∈ Θ(log log 1ǫ ) is a function of ǫ, and Iǫmax (A : B) denotes the smooth max-information part
B has about part A.
2. For any fixed ǫ ∈ (0, 1] and for any 0 < δ < 1 − ǫ2 , we have
√ 2
2(ǫ +δ)
min max Dmax
(Q(x)kσ) + g1 (ǫ, δ) ≤ Q∗ (RSP(S, Q), ǫ)
σ∈D(H) x∈S

≤

min

√

ǫ
2

1+ǫ
max Dmax
(Q(x)kσ) + g2 (ǫ) ,

σ∈D(H) x∈S



3
where g1 , g2 are functions such that g1 (ǫ, δ) ∈ Θ log ǫ2δ+δ , g2 (ǫ) ∈ Θ(log log 1ǫ ), and Dǫmax (Q(x)kσ)
denotes the smooth max-relative entropy of Q(x) with respect to σ.
It is relatively straightforward to show that the one-shot information expressions appearing in the above
theorem are continuous in ǫ. This indicates the tightness of the characterization. In fact, a bound on the
difference between lower and upper bounds in the above theorem, in terms of the ensemble, may be inferred
from the continuity property.
We remark that the quantity appearing in the second part of the theorem is similar to the notion of information radius. It may be possible to relate the quantity to smooth max-information with respect to
a distribution over S using ideas from Ref. [18, Lemma 3] (which extends Ref. [50, Lemma 14]), and the
connection between max-relative entropy and the sandwiched Rényi relative entropy. Finally, earlier works
have considered remote state preparation of states drawn from infinite sets of states. We discuss how the
bounds in Theorem 1.1 may be applied to that case in Appendix B.
The communication cost of ARSP may decrease dramatically when more error is allowed,and if we consider
average-case error instead of worst-case error. In particular, we show that for every ǫ ∈ [0, √12 ), there exists
a set of n quantum states for which there is a log n gap between the worst-case error and average-case error
remote preparation of that set. In addition, for a special set of quantum states, we derive a gap between
the worst-case error and average-case communication complexity in terms of ǫ. This confirms our intuition
that the more skewed the probability distribution is, the bigger the gap between worst-case and average-case
error variants may be.
In the process of establishing the first gap described above, we strengthen a result due to Nayak and
Salzman [35]; we prove a bound on the communication required by any LOCC protocol for transmitting a
uniformly random n bit string with some probability p. This bound is optimal, and may be of independent
interest.
Theorem 1.2. Let Y be the output of Bob in any two-way LOCC protocol in which Alice receives a uniformly
distributed n-bit input X (that is not known to Bob, and is independent of their joint quantum state). Let mA
be the total number of bits Alice sends to Bob and p := Pr[Y = X] be the probability that Bob obtains the
output X. Then
mA ≥ n + log p .

4

Worst-case protocols for ARSP capture precisely the task of compression in one-way communication complexity. Average-case protocols for ARSP are relevant in the distributional setting in communication complexity,
and in asymptotic information theory. The results in this paper thus supercede those due to Jain, Radhakrishnan, and Sen [29] (and due to Touchette [47] for the same setting). We also show how a characterization
due to Berry and Sanders [7] may be reproduced from ours, via a quantum asymptotic equipartition property
(cf. Theorem 2.6). Thus, we believe the results presented here have wider ramifications.

1.2

Organization

The organization of this paper is as follows. In Section 2, we review some concepts, fix notation, and the
terminology used in the paper. Then we define remote state preparation, and explain an efficient protocol
for this problem introduced in Ref. [29]. In Section 3 and Section 4, we give bounds on average-case error
and worst-case communication complexity of ARSP, respectively. We make some observations, including a
comparison with previously known results in Section 5. We analyze LOCC protocols for communicating a
uniformly random n bit string in Section 6. The paper ends with a summary of our results and an outlook
in Section 7. In the Appendix, we present the proofs of some properties of information-theoretic quantities,
and discuss remote state preparation of states drawn from an infinite set.

Acknowledgments
We are grateful to Matthias Christandl for discussions which led to the research reported in this article.
S.B. thanks Marco Tomamichel for his help with the proof of Theorem 4.2 during her internship at CQT,
Singapore. We also thank the reviewers and the Associate Editor, Mark Wilde, for their comments and
suggestions.

2

Preliminaries

In this section, we review some notions in quantum computing and quantum information theory, such as
LOCC protocols, quantum communication complexity, asymptotic and non-asymptotic quantum information
theory, as well as some mathematical tools like the minimax theorem. We also define remote state preparation
formally and describe a non-trivial protocol for this problem. We refer the reader to the books by Nielsen
and Chuang [37] and Watrous [49] for basic notions and results in quantum information, and largely only
describe the potentially non-standard notation and terminology we use.

2.1

Some basic notions

We denote Hilbert spaces either by capital script letters like H and K, or as Cm where m is the dimension of
the Hilbert space. We concern ourselves only with finite dimensional Hilbert spaces in this article. We denote
the set of all linear operators from H to K by L(H, K). We abbreviate L(H, H) as L(H). We denote the set
of all positive semidefinite operators in H by Pos(H). An operator A is called sub-normal if it is positive
semidefinite and has trace at most 1. (The term “subnormalized” is also often used for such operators.)
We denote the identity operator on a Hilbert space by 1 and the set of all unitary operators on space H
by U(H).
We call a physical quantum system with a finite number of degrees of freedom a register. Every register
is associated with a Hilbert space. We denote registers by capital letters, e.g., X, Y and Z. We use the
5

notation |X| to denote the dimension of the Hilbert space associated with register X. The state of a register X
is modelled as a density operator, i.e., a positive semidefinite operator with trace one, and is called a quantum
state. We denote density operators by lower case Greek letters (e.g., ρ, σ, . . . ), and the set of all density
operators over a Hilbert space H by D(H). We may also denote a state by ρX to indicate its register X.
A bipartite register XY with Hilbert space H ⊗ K is called a classical-quantum
register in the context of
P
an information processing task, if it only assumes states of the form i pi |ei ihei | ⊗ ρi where {|ei i} is the
standard basis of H and p is a probability distribution over the basis.
√ states are
P In that case we say
Pthe
√ that
classical on X. For any ω ∈ Pos(H) with spectral decomposition i λi |ψi ihψi |, we let ω = i λi |ψi ihψi |.
We denote the partial trace over Hilbert space K of a quantum state ρAB ∈ D(H ⊗ K) by either TrK (ρAB )
or TrB (ρAB ). We say that ρAB ∈ D(H ⊗ K) is an extension of ρA ∈ D(H) if TrK (ρAB ) = ρA .

We call completely positive and trace preserving linear maps √
L(H) → L(K) quantum channels. Quantum
measurements are quantum channels with Kraus operators { Ea ⊗ |ai : a ∈ Γ}, where Γ is the set of
outcomes of
P the measurement and Ea is a positive semidefinite operator associated with the outcome a ∈ Γ
such that a∈Γ Ea = 1. We refer to the operators Ea as measurement operators.

The fidelity F(ρ, σ) between two quantum states ρ and σ, is defined as
q
√ √
F(ρ, σ) := Tr
ρσ ρ .

In the literature, fidelity is sometimes defined as the square of the above quantity. Fidelity may be extended
to sub-normal states ρ, σ as follows:
q
p
√ √
F(ρ, σ) := Tr
ρ σ ρ + (1 − Tr(ρ)) (1 − Tr(σ)) .

The fidelity function is monotone under the application of quantum channels, and is jointly concave over the
set of quantum states. Other useful properties of fidelity are stated in the following propositions.
Proposition 2.1. For any quantum state ρ and sub-normal state σ, it holds that
F(ρ, σ)2

≤

Tr(σ) .

Proposition 2.2. Let ρ, σ ∈ D(H) be two quantum states. Then
1 + F(ρ, σ)

=

max {F(ρ, ξ)2 + F(σ, ξ)2 : ξ ∈ D(H)} .

For a proof of the above property, see Ref. [36, Lemma 3.3].
We use the purified distance (see Ref. [45]) as a metric for sub-normal states. This is an extension of the
metrics developed in Refs. [40, 41, 20, 42]. Suppose that ρ and σ are two sub-normal states. Then the
purified distance of ρ and σ is defined as
p
P(ρ, σ) :=
1 − F(ρ, σ)2 .

There are other metrics over sub-normal states, such as the trace distance. However, we choose purified
distance since it turns out to be more convenient to use in non-asymptotic quantum information theory.
Let ρ ∈ D(H) be a quantum state and ǫ ∈ [0, 1). Then, we define
Bǫ (ρ)

:=

{ρ̃ ∈ Pos(H) : P(ρ, ρ̃) ≤ ǫ, Tr ρ̃ ≤ 1}

as the ball of sub-normal states that are within purified distance ǫ of ρ. We say that σ is ǫ-close to ρ,
or equivalently, σ is an ǫ-approximation of ρ, if σ ∈ Bǫ (ρ). The following property of purified distance
states that any state ρ′A that is ǫ-close to ρA may be extended to a state ρ′AB that is ǫ-close to any given
extension ρAB of ρA .
6

Proposition 2.3. Let ρA ∈ D(HA ) be a quantum state in the Hilbert space HA and ρAB ∈ D(HA ⊗HB ) be an
extension of ρA over the Hilbert space HA ⊗HB , i.e. ρA = TrB (ρAB ). Let ρ′A ∈ Bǫ (ρA ) be an ǫ-approximation
of ρA . Then there exists ρ′AB ∈ Bǫ (ρAB ) such that ρ′A = TrB (ρ′AB ).
Proof: Let |vi ∈ D(HA′ ⊗ HB ′ ⊗ HA ⊗ HB ) be a purification of ρAB and therefore also of ρA , and |v ′ i ∈
D(HA′ ⊗ HB ′ ⊗ HA ⊗ HB ) be a purification of ρ′A , such that F(ρA , ρ′A ) = |hv|v ′ i|. Such |vi and |v ′ i exist
by the Uhlmann theorem. Define ρ′AB = TrA′ B ′ (|v ′ ihv ′ |). By definition, we have F(ρA , ρ′A ) = F(ρAB , ρ′AB ).
Therefore ρ′AB ∈ Bǫ (ρAB ).
The above property is in fact an extension of the Uhlmann theorem for purified distance.

2.2

LOCC protocols

The notion of LOCC, short for local operations and classical communication, plays an important role in
quantum information, especially in the study of properties of entanglement (see, e.g., Ref. [5]). This notion
has been described formally in terms of quantum instruments in Ref. [14]. In this article, we only study
two-party LOCC protocols, in which one party receives a classical input, and the other party produces a
quantum output. We describe these protocols informally below.
Suppose we have two parties, Alice and Bob, who communicate with each other using only classical bits,
share parts of a possibly entangled quantum state, and are allowed to perform any local quantum channels
on their registers. We call the registers (or qubits) accessible by only one of the parties private registers
(or qubits). Alice is given a classical input; Bob does not receive any input. Let A be the register which
holds Alice’s input, Y0 := P0 V0 and Z0 := Q0 W0 be Alice’s and Bob’s initial classical-quantum private
registers, respectively. Registers Pi and Qi are classical registers with Alice and Bob, respectively, after
the ith message. These registers hold the message transcript thus far. Initially, P0 , Q0 are both empty.
Registers V0 and W0 are initialized to a quantum state independent of the inputs. Note that the state
in V0 W0 might be entangled across the registers. If there are k messages, Pk+1 and Vk+1 denote Alice’s
final classical and quantum registers, respectively, and Qk+1 Wk+1 denote Bob’s, potentially after a local
operation. Register A remains unchanged throughout the protocol. Bob produces the output, which is a
sub-register B of Qk+1 Wk+1 .
A one-way LOCC protocol is an LOCC protocol in which the communication consists of one message from
Alice to Bob. The three steps of the protocol are:
1) Alice measures her register V0 , obtains the outcome in register P1 (and a residual state in V1 ). The
measurement is controlled by her input in A.
2) Alice sends a copy of her measurement outcome to Bob, in classical register M . Bob sets Q1 = M .
3) Bob measures his register W1 (which is the same as W0 ), controlled by the register Q1 . The outcome
and residual state are stored in classical-quantum registers Q2 W2 , where Q2 includes Q1 . The output
of the protocol is a designated sub-register B of his registers Q2 W2
A two-way LOCC protocol is a protocol with communication in both directions, from Alice to Bob and Bob
to Alice. It has several rounds of communication in which the two parties alternately do a local measurement
and send a message. Either party may start or end the protocol. Suppose in round i, it is Alice’s turn. Then
• First, Alice measures her quantum register in that round, Vi−1 , controlled by her input A and her
classical register Pi−1 . She copies the outcome Mi in a fresh register Ni . The register Pi := Pi−1 Ni .

7

• Alice then sends Mi to Bob using mi classical bits, and Bob includes the received message Mi in his
transcript register: Qi := Qi−1 Mi .
Bob’s actions are similar in a round in which it is his turn (except that he does not have any input), using
registers Qi Wi . At the end of a protocol with k rounds of communication, Bob makes a measurement on
the quantum register Wk controlled by Qk , and he includes the outcome Mk+1 of the measurement in the
register Qk+1 . A pre-designated sub-register B of Qk+1 Wk+1 is the output of the protocol.

2.3

Quantum communication complexity

Quantum communication complexity was introduced by Yao [51], and has been studied extensively since.
Here we describe it in the context of LOCC protocols.
Let X, Y be two finite sets, Z be a set (not necessarily finite), and f ⊆ X × Y × Z be a relation such that
for every (x, y) ∈ X × Y , there exists some z ∈ Z such that (x, y, z) ∈ f . The sets X, Y, Z might be sets of
quantum states. For example, in remote state preparation Z is the set of quantum states over some space.
In an LOCC protocol, Alice and Bob get as their inputs x ∈ X and y ∈ Y , respectively, and their goal is
to output an element z ∈ Z such that (x, y, z) ∈ f . In the protocols we consider, one party may not get
any input, e.g., Y may be empty. Also, in general the output of the protocol is probabilistic. If Wx,y is the
random output that the protocol produces on inputs (x, y), we define the error of the protocol as
δ

:=

max Pr((x, y, Wx,y ) 6∈ f ) .

x∈X,y∈Y

We then say the protocol computes f with error δ.
Definition 2.1. The entanglement-assisted communication complexity of f with error δ is defined as the
minimum number of bits exchanged in an LOCC protocol computing f with error δ.
Now consider a relation f ⊆ X × Y × Z, with Z = D(H), the set of quantum states over H. In this
context we may allow a protocol to produce an approximation to the desired quantum state. Suppose the
output quantum state that an LOCC protocol for f produces on inputs (x, y) is denoted by wxy . Let p be a
probability distribution over X × Y . We say a protocol computes an approximation of f with average-case
error at most ǫ if there are quantum states {zxy : x ∈ X, y ∈ Y, (x, y, zxy ) ∈ f } such that
p
X
pxy F(wxy , zxy ) ≥
1 − ǫ2 .
x∈X,y∈Y

P
The above condition may equivalently
P be written as P(ζ, ω) ≤ ǫ, where ζ := x,y pxy |xyihxy| ⊗ zxy is an
ideal input-output state, and ω := x,y pxy |xyihxy| ⊗ wxy is the actual input-output state of the protocol.

Definition 2.2. The average-case communication complexity of f is defined as the minimum number of
bits exchanged in an LOCC protocol computing an approximation of f with average-case error at most ǫ,
and is denoted by Q∗p (f, ǫ).
Similarly, we say a protocol computes an approximation of f with worst-case error at most ǫ if there are
quantum states {zxy : x ∈ X, y ∈ Y, (x, y, zxy ) ∈ f } such that
max P(wxy , zxy )

x∈X,y∈Y

≤

ǫ .

Definition 2.3. The worst-case communication complexity of f is defined as the minimum number of bits
exchanged in an LOCC protocol computing an approximation of f with worst-case error at most ǫ, and is
denoted by Q∗ (f, ǫ).
Note that “error” here refers to the quality of approximation in the output state. The result of any probabilistic error made by the protocol is included in the output state, and hence this kind of error is reflected
in the quality of approximation.
8

2.4

Quantum information theory

Let X be a register in quantum state ρ ∈ D(H). Then the von Neumann entropy S(ρ) of X is defined as
:=

S(ρ)

−Tr(ρ log ρ) .

Let X and Y be two registers in quantum states ρX ∈ D(H) and σY ∈ D(H), respectively. The relative
entropy denoted by S(ρX kσY ) is defined as
:=

S(ρX kσY )

Tr (ρX log ρX − ρX log σY )

if supp(ρ) ⊆ supp(σ), and as ∞ otherwise. Suppose that ρXY ∈ D(H ⊗ K) is the joint state of registers X
and Y , then the mutual information of X and Y is defined as
:=

I(X : Y )ρ

S(ρX ) + S(ρY ) − S(ρXY ) ,

where ρX = TrY (ρXY ) and ρY = TrX (ρXY ). When the register whose state is ρ is clear from the context,
we may omit it from the subscript of ρ. Similarly, when the state ρ of the registers XY is clear from the
context, we may omit it from the subscript of I(X : Y ).
For ρ, σ ∈ D(H), the observational divergence [28] between ρ and σ is defined as


Tr(M ρ)
Dobs (ρkσ) := sup Tr(M ρ) log
: 0 ≤ M ≤ 1, Tr(M σ) 6= 0 .
Tr(M σ)

P
Let E = (pj , ρj ) : 1 ≤ j ≤ n be an ensemble of quantum states, i.e., 0 ≤ pj ≤ 1 for 1 ≤ j ≤ n, nj=1 pj = 1,
and ρj ∈ D(H) are quantum states over the same space. The Holevo information of E , denoted as χ(E ), is
defined as
n
X
pj S(ρj kρ) ,
χ(E ) :=
j=1

where ρ is the ensemble average, i.e., ρ =
denoted as Dobs (E ), as

Pn

Dobs (E )

j=1

pj ρj . Similarly, we define the divergence information of E ,

:=

n
X
j=1

pj Dobs (ρj kρ) .

Let S be a set, and Q : S → D(H) be a function which “encodes” each x ∈ S asP
a quantum state. Let p be
a probability distribution over S, and ρAB (p) be the bipartite state ρAB (p) := x px |xihx|A ⊗ Q(x)B . We
define the maximum possible information in Q [25], denoted by T(Q), as
T(Q)

:=

max I(A : B)ρ(p) ,
p

where the maximum is taken over all probability distributions p over S.
P
Note that for a classical-quantum state ρAB = nj=1 pj |jihj| ⊗ ρj , the mutual information of A and B is

equal to the Holevo information of the quantum ensemble E = (pj , ρj ) : 1 ≤ j ≤ n , i.e., χ(E ) = I(A : B),
and therefore T(Q) ≥ χ(E ).
Most of the entropic quantities defined above arise naturally in the analysis of information processing tasks
in the asymptotic setting, i.e., when the available resources may be used to jointly complete arbitrarily
long sequences of tasks on independent, identically distributed (iid) inputs. The asymptotic setting is an
idealization that may not be realistic in certain scenarios. More often, we are faced with single instances of
a task which we wish to accomplish with the fewest resources. Recently, researchers have begun to formally
study tasks in the non-iid or one-shot setting, and the entropic notions that arise therein. Several one-shot
9

entropic concepts have been implicit in traditional (iid) information theory and in communication complexity.
For example, Jain, Radhakrishnan, and Sen implicitly studied the concept of smooth max-relative entropy in
Ref. [28]. However, non-asymptotic concepts were formalized only later (see, e.g., Refs. [43, 44, 16]). In this
work, we use one-shot entropic quantities to tightly characterize the communication complexity of remote
state preparation.
Let ρ, σ ∈ D(H) be two quantum states. The max-relative entropy of ρ with respect to σ is defined as
Dmax (ρkσ)

min{λ : ρ ≤ 2λ σ} ,

:=

when supp(ρ) ⊆ supp(σ), and is ∞ otherwise [16]. This notion captures how two states ρ, σ behave relative
to each other under the application of a measurement. For a bipartite quantum state ρAB ∈ D(H′ ⊗ H), the
max-information part B has about part A [9] is defined as
Imax (A : B)ρ

:=

min Dmax (ρAB k ρA ⊗ σB ) .

σ∈D(H)

Note that this quantity is asymmetric with respect to the parts A and B. As for mutual information,
we include the state as a subscript only when it is not clear from the context. The smoothed versions of
these quantities come into play when approximations are allowed in the tasks at hand. Smooth max-relative
entropy is defined as
Dǫmax (ρkσ) :=
min
Dmax (ρ̃kσ) ,
ǫ
ρ̃∈B (ρ)

and smooth max-information is defined as
Iǫmax (A : B)ρ

:=

min Imax (A : B)ρ̃ .

ρ̃∈Bǫ (ρ)

There are several ways to define max-information using max-relative entropy [15]. We choose the above
definition in this work since it can be used to characterize average-case communication complexity of the
remote state preparation problem.
The following are some properties of max-information we use. Both the exact and smooth versions of this
quantity are monotonic under the application of a quantum channel [9].
Proposition 2.4 (Monotonicity under quantum channels). Let Φ : L(H′ ) → L(K) be a quantum channel,
ρAB a bipartite sub-normal state over H′ ⊗ H, σAB ∈ D(H′ ⊗ H) a bipartite quantum state, and ǫ ∈ [0, 1].
Then
Imax (A′ : B)ρ′
Iǫmax (A′

: B)σ′

≤

≤

Imax (A : B)ρ ,
Iǫmax (A

and

: B)σ ,

′
where A′ , B denote two parts of the states ρ′A′B := (Φ ⊗ 1)(ρ) and σA
′B := (Φ ⊗ 1)(σ).

For a classical-quantum state ρAB , the value of smooth max-information is achieved by a classical-quantum
state ρ′AB that is ǫ-close to ρAB . A proof is included in Appendix A.
Proposition 2.5. Let ρAB ∈ D(H′ ⊗ H) be a bipartite quantum state that is classical on A. For any ǫ ≥ 0,
there exists ρ′AB ∈ Bǫ (ρAB ) ∩ D(H′ ⊗ H) classical on A such that
Iǫmax (A : B)ρ

=

Imax (A : B)ρ′ .

Smooth max-information satisfies the Asymptotic Equipartition Property, as proven by Berta, Christandl,
and Renner [9]. Let H denote the binary entropy function H(α) := −α log α − (1 − α) log(1 − α).

10

Theorem 2.6 (Quantum Asymptotic Equipartition property). Let ǫ > 0, n an integer such that n ≥
2(1 − ǫ2 ), and ρAB ∈ D(HAB ). Then
I(A : B)ρ −

3
H(ǫ) − 2ǫ log(|A| |B|)
n

≤

1 ǫ
I
(A : B)ρ⊗n ,
n max

(2.1)

and
1 ǫ
I
(A : B)ρ⊗n
n max
√
where ξ(ǫ) = 8 13 − 4 log ǫ (2 +

1
2

2
ǫ2
ξ(ǫ)
,
I(A : B)ρ + √ − log
n
n
24

≤

(2.2)

log |A|). Therefore,

lim lim

ǫ→0 n→∞

1 ǫ
I
(A : B)ρ⊗n
n max

=

I(A : B)ρ .

For ǫ ∈ [0, 1), the ǫ-hypothesis testing relative entropy [48] of two quantum states ρ, σ ∈ D(H) is defined as
Dǫh (ρkσ)

:=

− log

βǫ (ρkσ)
,
1−ǫ

where
βǫ (ρkσ)

:=

inf {hQ, σi | 0 ≤ Q ≤ 1 and hQ, ρi ≥ 1 − ǫ} .

(2.3)

The infimum in the above definition is always achieved and βǫ (ρkσ) is between 0 and 1. In this definition,
we interpret (Q, 1 − Q) as a measurement for distinguishing ρ from σ, i.e., as a strategy in hypothesis testing.
So βǫ (ρkσ) corresponds to the minimum probability of incorrectly identifying σ when ρ is identified correctly
with probability at least 1 − ǫ. This one-shot entropic quantity has been studied for a long time either
implicitly (see, e.g., Refs. [24, 38]) or explicitly, albeit without giving it a name (see, e.g., Refs. [13, 12]). It
also arises in the context of channel coding [23, 48] and other tasks [22].
The error in hypothesis testing may only increase under the action of a quantum channel. This has been
known for some time; see, e.g., Ref. [10, Eq. (44)] for a proof.
Proposition 2.7 (Data Processing Inequality). Let ρ, σ ∈ D(H) for some Hilbert space H, and Φ : L(H) →
L(K) be a quantum channel. Then
βǫ (ρkσ)

≤

βǫ (Φ(ρ) k Φ(σ)) .

The following two properties have been proved implicitly by Matthews and Wehner [34]. For completeness,
we include their proofs in Appendix A.
Hypothesis testing error satisfies a restricted form of joint convexity in its two arguments.
Proposition 2.8. Let ρAB (p) ∈ D(HA ⊗ HB ) be a state classical on A such that the distribution on A is
given by the probability vector p. Let ρA (p) = TrB (ρAB (p)), and σ ∈ D(HB ) be a quantum state on Hilbert
space HB . Then the function βǫ (ρAB (p) k ρA (p) ⊗ σ) is convex with respect to p.
Hypothesis testing error is concave in its second argument.
Proposition 2.9. For any fixed quantum state ρ ∈ D(H), the function βǫ (ρkσ) is a concave function with
respect to σ.
It turns out that hypothesis testing relative entropy is closely related to smooth max-relative entropy, as
captured by the following theorem.
11

Theorem 2.10 ([19, 46]). Let ρ, σ ∈ D(H) be two quantum states in Hilbert space H. For any ǫ ∈ (0, 1)
and δ ∈ (0, ǫ), the following inequalities hold:
√
2(1−ǫ)
Dmax
(ρkσ) ≤ Dǫh (ρkσ) ,
and
(2.4)
√

1−ǫ
Dmax
(ρkσ)

2.5

≥

Dǫ−δ
h (ρkσ) − log

ǫ(1 − ǫ + δ)
− 3 log 3 .
δ3

(2.5)

The minimax theorem

The minimax theorem is a powerful result that provides conditions under which switching the order of
minimization and maximization in certain optimization problems does not change the optimum.
Theorem 2.11 ([39]). Let n be a positive integer, and A1 , A2 be non-empty, convex and compact subsets
of Rn . Let f : A1 × A2 → R be a continuous function such that
1. ∀a2 ∈ A2 , the set {a1 ∈ A1 : (∀a′1 ∈ A1 ) f (a1 , a2 ) ≥ f (a′1 , a2 )} is convex.
2. ∀a1 ∈ A1 , the set {a2 ∈ A2 : (∀a′2 ∈ A2 ) f (a1 , a2 ) ≤ f (a1 , a′2 )} is convex.
Then
max min f (a1 , a2 )

a1 ∈A1 a2 ∈A2

2.6

=

min max f (a1 , a2 ) .

a2 ∈A2 a1 ∈A1

Remote state preparation

Let S be a finite, non-empty set, and let Q : S → D(H) be a function that maps each element x ∈ S to a
quantum state Q(x) over the Hilbert space H. Recall that remote state preparation, denoted as RSP(S, Q),
is a communication task in which one party, Alice, is given an input x ∈ S, and engages in an LOCC protocol
with another party, Bob, so that Bob is able to prepare Q(x). The function Q is known to both parties. In
the approximate remote state preparation, we allow Bob to prepare an approximation σx ∈ D(H) to Q(x).
We consider two notions of error in approximation: worst case and average case. Let ǫ ∈ [0, 1], and let p be
a probability distribution on S. We say a protocol for RSP(S, Q) makes worst-case error ǫ if P(σx , Q(x)) ≤ ǫ
for each x ∈ S. We say a protocol for RSP(S, Q) makes average-case error ǫ w.r.t. the distribution p over S
if the purified distance between the ideal and actual joint input-output states is at most ǫ. By the definitions
of purified distance and fidelity, this condition is equivalent to
p
X
px F(σx , Q(x)) ≥
1 − ǫ2 .
x∈S

In Sections 3 and 4, we characterize the communication complexity of this problem for the two different
kinds of approximation. We emphasize that Alice and Bob communicate with a noiseless classical channel,
they have access to an arbitrarily large amount of entanglement of their choice, and they have unlimited
computational power.
A straightforward protocol for approximate remote state preparation is as follows. Alice sends her input x
directly to Bob and Bob creates the desired state Q(x). Thus Bob prepares the target state with zero error
(ǫ = 0) using ⌈log(n + 1)⌉ bits of classical communication, where n = |S|.
Jain, Radhakrishnan, and Sen [28, 29] proposed the following, potentially more efficient protocol, which we
call the JRS protocol in the sequel. Let K be a Hilbert space with dim(K) ≥ dim(H) and {σx }x∈S ⊆ D(H)
12

be a set of quantum states such that for all x ∈ S, P(σx , Q(x)) ≤ δ for some δ ∈ [0, 1]. Suppose that for
some λ ∈ [0, ∞) and some σ ∈ D(H), we have
σx

≤

2λ σ

=

2−λ σx + (1 − 2−λ )ξx ,

for all x ∈ S .

(2.6)

This can be rewritten for a fixed x ∈ S as
σ

where ξx ∈ D(H) is a quantum state. Let |vx i ∈ K ⊗ H be a purification of σx in the Hilbert space K ⊗ H,
and |ux i ∈ K ⊗ H be a purification of ξx . Then
p
√
|wx i =
2−λ |0i|vx i +
1 − 2−λ |1i|ux i ,

is a purification of σ. Let |wi be an arbitrary but fixed purification of σ in C2 ⊗ K ⊗ H. By the unitary
equivalence of purifications, there is a unitary operation Ux on the space C2 ⊗K which transforms |wi to |wx i.
We are ready to describe the JRS protocol.
JRS Protocol: Alice and Bob agree on a parameter t, that depends on the quality of approximation they
desire. Initially, Alice and Bob share t copies of the quantum state |wi. The registers corresponding to
Hilbert spaces C2 and K in the ith copy of |wi are called Ci and Ki , respectively, and are held by Alice. The
register corresponding to the Hilbert space H is called Hi and is held by Bob.
1. On getting input x, Alice performs the unitary operation Ux on registers Ci Ki for each i ∈ [t]. This
transforms all copies of |wi to copies of |wx i. Then she measures the register Ci for all i ∈ [t]. If at
least one of the measurement outcomes, say the jth, is equal to zero, she sends the index j to Bob,
using ⌈log(t + 1)⌉ bits. (She may choose to send any such index.) Otherwise, if the outcomes of all t
measurements are equal to one, she sends 0 to Bob.
2. On receiving an integer k, where 0 ≤ k ≤ t, Bob outputs the state in register Hk if k ∈ [t], and outputs
the maximally mixed state over H if k = 0.
The output of this protocol is
the output state is

1
|H|

with probability 1 − 2−λ

t

and σx with the remaining probability. Hence,

1
.
|H|
By choosing the approximation parameter δ small enough and t large enough, Bob produces a state σ̃x with
the desired accuracy. We use this protocol to give upper bounds on the worst-case error and average-case
communication complexity of RSP(S, Q).
σ̃x

3

=



1 − 1 − 2−λ

t 

σx + 1 − 2−λ

t

Average-case communication complexity

Let p be a probability distribution over S and Q∗p (RSP(S, Q), ǫ) denote the average-case entanglementassisted communication complexity of approximate remote state preparation (ARSP), with respect to p,
and with (average) error at most ǫ. We characterize this quantity in terms of smooth max-information, a
one-shot analogue of mutual information.

3.1

An upper bound

First, we show that the average-case communication complexity with error ǫ of ARSP is bounded above
essentially by Iδmax (A : B)ρ(p) , where ρ(p) is the ideal joint state of Alice’s input and Bob’s output, and δ ∈
Θ(ǫ). To do so, we use the JRS protocol described in Section 2.6.
13

Theorem 3.1. For any finite set S, function Q : S → D(H), and ǫ ∈ (0, 1], let p beP
a probability distribution
over S and ρAB (p) ∈ D(H′ ⊗ H) be the bipartite classical-quantum state ρAB (p) = x∈S px |xihx|A ⊗ Q(x)B .
Then
8
Q∗p (RSP(S, Q), ǫ) ≤ Iδmax (A : B)ρ(p) + log2 ln 2 + 2 ,
ǫ
√
where δ = ǫ/2 2.
Proof: Fix some ǫ ∈ (0, 1], and let λ be equal to Iδmax (A : B)ρ(p) with δ as in the statement of the
′
δ
′
theorem. By Proposition 2.5,
P there exist quantum
Pstates ρAB ∈ Bx (ρAB ) and σB ∈′ D(H)
P such that ρAB ≤
λ ′
′
x
2 ρA ⊗ σB ,where ρAB = x qx |xihx| ⊗ σB with x qx = 1 and σB ∈ D(H), and ρA = x qx |xihx|. Then
x
σB

2λ σB ,

≤

(3.1)

x
for all x ∈ S with qx 6= 0. For each x ∈ S with qx = 0, we assume, w.l.o.g., that σB
= σB . Inequality (3.1)
is in the form of inequality (2.6) and therefore we may execute the JRS protocol with a suitable choice of
parameter t. Initially, Alice and Bob share t copies of entangled state |wi, where |wi is a purification of σB .
x
Alice gets input x with probability px . They perform the protocol for approximating state σB
from σB . The
final joint state of Alice’s input and Bob’s output is
X
x
ρ̃AB =
,
px |xihx| ⊗ σ̃B
x∈S

where
x
σ̃B



=

Therefore,
F(ρ̃AB , ρ′AB )

=

F

1 − 1 − 2−λ

X

x∈S

t 

px |xihx| ⊗
−λ t

≥

1 − (1 − 2

=

1 − (1 − 2−λ )t

≥

−λ t

1 − (1 − 2

)



x
σB
+ 1 − 2−λ

x
σ̃B
,

X

x∈S

F

X

x∈S

t

qx |xihx| ⊗

px |xihx| ⊗

X√
px qx

1
.
dim(H)

x
σB

x
σB
,

!
X

x∈S

qx |xihx| ⊗

x
σB

!

x∈S

p
)
1 − δ2 ,

where the first inequality follows from the joint concavity of fidelity. The last inequality follows from
monotonicity under quantum channels:
X√
px qx = F(ρ′A , ρA ) ≥ F(ρ′AB , ρAB ) .
x∈S

In addition, by Proposition 2.2,
F(ρ̃AB , ρAB )

≥
≥
≥

F(ρ̃AB , ρ′AB )2 + F(ρAB , ρ′AB )2 − 1
2
1 − (1 − 2−λ )t (1 − δ 2 ) + (1 − δ 2 ) − 1
p
1 − ǫ2 ,

√
where the last inequality is derived using inequalities ln(1 − x) ≤ −x and 1 − x ≤ 1 − x2 , which hold for x ∈
√
 λ

P
[0, 1), and the parameter values δ = ǫ/2 2 and t = 2 ln ǫ82 . Since F(ρ̃AB , ρAB ) = x∈S px F(σ̃x , Q(x)),
the protocol has average-case error at most ǫ.

14

The communication cost of this protocol is ⌈log(t + 1)⌉. So the communication complexity of approximate
remote state preparation with average-case error ǫ is
Q∗p (RSP(S, Q), ǫ)

≤

⌈log(t + 1)⌉

≤

λ + log2 ln

8
+2 ,
ǫ2

as required.
We have not attempted to optimize the upper bound derived above. It is possible that the parameter δ and
the ǫ-dependent additive term be improved further.

3.2

A lower bound

Next, we show that the average-case communication complexity of any protocol for approximate remote
state preparation is bounded from below by Iǫmax (A : B)ρ(p) . In order to do this, we strengthen a property of
smooth max-information due to Berta, Christandl, and Renner [9, Lemma B.12], in the case of a tripartite
state ρMAB that is classical on M .
Lemma 3.2. Let ǫ ≥ 0 and ρMAB ∈ D(M ⊗ H′ ⊗ H) be any tripartite quantum state over registers M , A
and B such that ρ is classical on M . Then
Iǫmax (A : MB)

Iǫmax (A : B) + log |M | .

≤

Proof: Fix σB ∈ D(H) and ρ̃AB ∈ Bǫ (ρAB ) such that Iǫmax (A : B) = Dmax (ρ̃AB k ρ̃A ⊗ σB ). Let λ denote this
max-relative entropy, i.e., λ is the minimum non-negative real number for which ρ̃AB ≤ 2λ ρ̃A ⊗ σB . Then
1
⊗ ρ̃AB
|M |

2λ

≤

1
⊗ ρ̃A ⊗ σB .
|M |

(3.2)

By Proposition 2.3, there exists some extension ρ′MAB of ρ̃AB such that ρ′MAB ∈ Bǫ (ρMAB ). By construction,
we have TrM (ρ′MAB ) = ρ̃AB . Consider the quantum-to-classical channel Φ : L(M) → L(M) defined by
X
hei |X|ei i|ei ihei |
Φ(X) =
i

for all X ∈ L(M), where {|ei i} is the standard orthonormal basis for the Hilbert space M. The state (Φ ⊗
1)(ρ′MAB ) is classical on M , and is an extension of ρ̃AB . Define ρ̃MAB := (Φ ⊗ 1)(ρ′MAB ). Since ρ′MAB ∈
Bǫ (ρMAB ), by monotonicity of fidelity under quantum channels and because ρMAB is classical on M , we
have ρ̃MAB ∈ Bǫ (ρMAB ). So ρ̃MAB may be written as
X
i
γi |ei ihei | ⊗ σAB
,
ρ̃MAB =
i

i
σAB

where all
are normalized and
tion (3.2), we can conclude that

P

i

γi ≤ 1. We have ρ̃MAB ≤ 1M ⊗ ρ̃AB . Combining this with Equa-

ρ̃MAB

≤

λ

2 |M |



1M
⊗ ρ̃A ⊗ σB
|M |



and consequently,

Dmax ρ̃MAB

1M
⊗ ρ̃A ⊗ σB
|M |



≤

λ + log |M | .

By the definition of smooth max-information, this implies that
Iǫmax (A : MB)

≤
15

λ + log |M | ,

as required.
Remark: The above lemma could alternatively be derived from an analogous inequality for α-Rényi mutual
information [31, Equation (2.25)]). Taking the limit as α → ∞ gives us the inequality for max-information
(i.e., for ǫ = 0). We may extend this to any ǫ ≥ 0 by smoothing arguments similar to those in the above
proof.
Using this lemma, we bound the average-case communication complexity of RSP(S, Q) from below.
Theorem 3.3. For any finite set S, function Q : S → D(H), and probability distribution p over S, let ρ(p)
be the bipartite quantum state
X
ρ(p) =
px |xihx|A ⊗ Q(x)B .
x∈S

For any ǫ ∈ [0, 1], we have

Q∗p (RSP(S, Q), ǫ)

≥

Iǫmax (A : B)ρ(p) .

Proof: In this proof we follow the notation and convention described in Section 2.2. Consider a k-round
LOCC protocol Π for RSP(S, Q) with average-case error ǫ. Suppose Bob sends the first message, and the
joint state in Alice and Bob’s registers (excluding the input register A) after the message is φ. As Bob receives
no input, the joint state φ is known to both parties. Hence, the rest of the protocol can be considered as
a new LOCC protocol, with the same output, in which the initial shared state of parties is φ, and Alice
starts the protocol. The communication cost of this new protocol is less than the communication cost of the
original one. Therefore, it suffices to show the lower bound for protocols in which Alice starts.
Let A be Alice’s input register, and Yi := Pi Vi and Zi := Qi Wi be Alice’s and Bob’s classical-quantum private
registers, respectively, after the ith round of the protocol for i ≥ 0. Initially, A and Z0 are independent, and
so
Imax (A : Z0 )

=

0 .

(3.3)

Consider the ith round of a two-way LOCC protocol. The communication in each round is either from Alice
to Bob (for odd i) or from Bob to Alice (for even i).

Odd round i: In this case, Alice measures her private qubits Vi−1 controlled by Pi−1 and A. She includes
the outcome of her measurement Mi in the register Pi (recall that Pi = Pi−1 Mi ), and sends a copy of Mi to
Bob using mi := ⌈log(|Mi | + 1)⌉ bits of communication. Then Bob includes the received message Mi in Qi
(recall that Qi = Qi−1 Mi ). Thus,
Imax (A : Zi )

≤ Imax (A : Zi−1 ) + log |Mi |

(by Lemma 3.2)

≤ Imax (A : Zi−1 ) + mi .

(3.4)

Even round i: In this case, Bob measures his private qubits Wi−1 controlled by Qi−1 . He includes the
outcome of his measurement Mi in Qi , and sends a copy of Mi to Alice using mi = ⌈log(|Mi | + 1)⌉ bits of
communication. Alice includes the received message in Pi . Thus,
Imax (A : Zi )

≤ Imax (A : Zi−1 ) .

(by Proposition 2.4)

Combining Eqs. (3.4) and (3.5) recursively, we get
Imax (A : Zk )

≤

Imax (A : Z0 ) +

X

1≤i≤k
i odd

16

mi

=

X

1≤i≤k
i odd

mi ,

(3.5)

P
after k rounds of communication. Let m := 1≤i≤k, odd mi . At the end of the protocol, Bob applies a quantum channel on his register Zk to get the output B. By monotonicity of max-information (Proposition 2.4),
we have
Imax (A : B)ρ′ (p) ≤ m ,
P
where ρ′ (p) = x px |xihx| ⊗ σx is the bipartite quantum state of registers AB, and m is the number of bits of
communication from Alice to Bob. In addition, protocol Π guarantees that ρ′ (p) is within purified distance ǫ
of ρ(p). Therefore, we conclude the theorem.

4

Worst-case communication complexity

In this section, we characterize the worst-case communication complexity of remote state preparation, denoted as Q∗ (RSP(S, Q), ǫ), in terms of smooth max-relative entropy.

4.1

An upper bound

We show that for some fixed ǫ ∈ (0, 1], the worst-case communication complexity of the approximate remote
state preparation problem is bounded from above essentially by
min max Dδmax (Q(x)kσ) ,

σ∈D(H) x∈S

where δ ∈ Θ(ǫ). As for the average case, we utilize the JRS protocol presented in Section 2.6.
Theorem 4.1. Let S be a non-empty finite set, Q : S → D(H) be a function from S to the set of density
operators in the Hilbert space H, and ǫ ∈ [0, 1]. Then
Q∗ (RSP(S, Q), ǫ)
where δ =

≤

min max Dδmax (Q(x)kσ) + log2 (1 + ǫ2 ) + log2 ln

σ∈D(H) x∈S

2
+2 ,
ǫ4

√ ǫ
.
1+ǫ2

Proof: Let α := minσ∈D(H) maxx∈S Dδmax (Q(x)kσ) and σ ′ be the quantum state for which the minimum is
achieved, i.e., α = maxx∈S Dδmax (Q(x)kσ ′ ). By definition, for all x ∈ S there exists some σx ∈ Bδ (Q(x)) such
that
σ ′ ≥ 2−α σx .

1
Since P(σx , Q(x)) ≤ δ, we have F(σx , Q(x))2 ≥ 1 − δ 2 . So, by Proposition 2.1, Tr(σx ) ≥ 1 − δ 2 = 1+ǫ
2 for
σx
:=
all x ∈ S. For each x ∈ S, define ρx
Tr(σx ) . Then for all x ∈ S, ρx is a quantum state δ-close to Q(x),
i.e., ρx ∈ Bδ (Q(x)) ∩ D(H) , and

σ′

≥

2−α Tr(σx ) ρx

≥

2−α
ρx .
1 + ǫ2

This inequality is precisely in the form of inequality (2.6). Now we run the JRS protocol to approximate Q(x),
with t = 2α (1 + ǫ2 ) ln ǫ24 . At the end of this protocol, Bob’s output is
σ̃x
where κ = α + log(1 + ǫ2 ).

:=



1 − 1 − 2−κ

t 

17

σx + (1 − 2−κ )t

1
,
dim(H)

By joint concavity of fidelity, and because σx is
F(Q(x), σ̃x )

≥

√ ǫ
-close
1+ǫ2


1 − (1 − 2−κ )t F(Q(x), σx )

to Q(x), we have
1 − (1 − 2−κ )t
√
1 + ǫ2

≥

≥

p
1 − ǫ2 .

√
Here we appealed to the inequalities ln(1 − x) ≤ −x and 1 − x ≤ 1 − x2 (for x ∈ [0, 1)), and the definition
of κ and t. Thus, the purified distance of Q(x) and σ̃x is at most ǫ, and the protocol performs remote state
preparation with worst-case error ǫ. The communication cost of this protocol is ⌈log(t + 1)⌉. Hence, we have
Q∗ (RSP(S, Q), ǫ)

≤

⌈log(t + 1)⌉

≤

α + log2 (1 + ǫ2 ) + log2 ln

2
+2 ,
ǫ4

the stated upper bound.

4.2

A lower bound

By definition, any protocol with worst-case error at most ǫ is also a protocol with average-case error at most ǫ.
As a consequence, any lower bound for average-case communication complexity is also a lower bound for
worst-case communication complexity. In particular, by Theorem 3.3, for each probability distribution p,
Iǫmax (A : B)ρ(p) is a lower bound for the worst-case communication complexity of remote state preparation.
Therefore,
max Iǫmax (A : B)ρ(p) ≤ Q∗ (RSP(S, Q), ǫ) ,
(4.1)
p

where the maximum is over all probability distributions p on the set S. In the following theorem, we give a
lower bound for Q∗ (RSP(S, Q), ǫ) in terms of max-relative entropy using Equation (4.1).
Theorem 4.2. Let S be a non-empty finite set, Q : S → D(H) be a function from S to the set of density
operators in Hilbert space H, ǫ ∈ (0, 1], and δ ∈ (0, 1 − ǫ2 ). Then
min max Dγmax (Q(x)kσ) − log

σ∈D(H) x∈S

where γ =

(1 − ǫ2 )(ǫ2 + δ)
− 3 log 3
δ3

≤

Q∗ (RSP(S, Q), ǫ) ,

p
2(ǫ2 + δ).

Proof: By definition of the smooth max-information, Eq. (4.1) implies that
max min
p

σ∈D(H)

Dǫmax (ρAB (p) k ρA (p) ⊗ σ)

≤

Q∗ (RSP(S, Q), ǫ) ,

(4.2)

whereas the upper bound shown in Theorem 4.1 is
min max Dδmax (Q(x)kσ) .

σ∈D(H) x∈S

If the minimax theorem held for the above expression, the theorem would follow. However, smooth maxrelative entropy Dǫmax is neither convex nor concave in its arguments, and the minimax theorem does not
apply directly. Instead, we appeal to Theorem 2.10, and approximate it with hypothesis testing relative
entropy Dǫh , and write it in terms of the hypothesis testing error βǫ . This measure satisfies the hypotheses of
the minimax theorem (cf. Proposition 2.9 and 2.8). We then apply the minimax theorem, and finally return
to Dǫmax to derive the lower bound.

18

By Theorem 2.10, we have
max min
p

σ∈D(H)

Dǫmax (ρAB (p) k ρA (p) ⊗ σ)

Dλh (ρAB (p) k ρA (p) ⊗ σ) − f (ǫ, δ)

− log βλ (ρAB (p) k ρA (p) ⊗ σ)

≥

max min

=

max min

=

+ log(1 − λ) − f (ǫ, δ)


− log min max βλ (ρAB (p) k ρA (p) ⊗ σ)

p

p

σ∈D(H)

σ∈D(H)

p

σ∈D(H)

+ log(1 − λ) − f (ǫ, δ) ,

2

where f (ǫ, δ) = log (1−ǫ δ)(ǫ
3

2

+δ)

+ 3 log 3 and λ = 1 − ǫ2 − δ.

Let A1 be the set of all probability distributions p over S, and A2 be the set of all quantum states σ ∈ D(H).
Viewing σ as an element of the real vector space of Hermitian operators in L(H), A1 and A2 are non-empty,
convex and compact subsets of Rn for some positive integer n. The quantity βλ (ρAB (p) k ρA (p) ⊗ σ) is a
continuous function of its arguments. Moreover, by Proposition 2.8 and Proposition 2.9, it satisfies both
conditions of the minimax theorem, Theorem 2.11. Thus, we conclude that


max min Dǫmax (ρAB (p) k ρA (p) ⊗ σ) ≥ − log max min βλ (ρAB (p) k ρA (p) ⊗ σ)
p

σ∈D(H)

σ∈D(H)

=

p

+ log(1 − λ) − f (ǫ, δ)

min max Dλh (ρAB (p) k ρA (p) ⊗ σ) − f (ǫ, δ)

σ∈D(H)

p

min max Dγmax (ρAB (p) k ρA (p) ⊗ σ) − f (ǫ, δ)

≥

σ∈D(H)

≥

σ∈D(H) x∈S

p

min max Dγmax (Q(x)kσ) − f (ǫ, δ) ,

(4.3)

p
p
where γ = 2(1 − λ) = 2(ǫ2 + δ). In the second inequality above, we use Theorem 2.10 to move between
hypothesis testing relative entropy and max-relative entropy. Combining Eqs. (4.3) and (4.2), we get the
lower bound for the worst-case communication complexity of ARSP.

5

Some observations

In earlier sections, we characterized the communication complexity of the approximate remote state preparation problem (ARSP) for both worst-case error and average-case error. We now discuss the results, especially
in light of previous work.

5.1

A comparison with previous works

In Section 4, we derived bounds on the worst-case communication complexity of ARSP. Jain [25] showed
that the worst-case communication complexity of ARSP of a sequence of quantum states (Q(x) : x ∈ S) is
bounded from above in terms of the “maximum possible information” T(Q) as:
8(4T(Q) + 7)
√
2 ,
1 − 1 − ǫ2

where ǫ is the approximation error. (See Section 2.4 for a definition of T(Q).)

19

(5.1)

We observe that for certain sets of states there is a large separation between the bound established in
Theorem 4.1, and Equation (5.1). Specifically, the upper bound in Theorem 4.1 may be asymptotically
smaller than the bound in Equation (5.1).
The separation follows from a combination of two pieces of work. The first is an information-theoretic result,
the Substate theorem due to Jain, Radhakrishnan, and Sen [30], which relates the smooth max-relative
entropy of two states to their observational divergence. The precise form of the statement below is due to
Jain and Nayak [26].
Theorem 5.1 (Substate theorem [30, 26]). Let H be a Hilbert space, and let ρ, σ ∈ D(H) be quantum states
such that supp(ρ) ⊆ supp(σ). For any ǫ ∈ (0, 1),
Dǫmax (ρkσ)

≤

Dobs (ρkσ)
1
+ log
.
2
ǫ
1 − ǫ2

The second result is due to Jain, Nayak, and Su [27], who constructed an ensemble of quantum states for
which there is a large separation between its Holevo and Divergence information. (See Section 2.4 for a
definition of these two information quantities.)
Theorem 5.2. Let n be a positive integer, and H be a Hilbert space of dimension n. For every positive real
2
number k ≥ 1 such that log2 n > 36kP
, there is a finite set S and an ensemble E = {(λx , ξx ) : x ∈ S} of
quantum states ξx ∈ D(H) with ξ := x∈S λx ξx = n1 , such that Dobs (Q(x)kξ) = Dobs (E ) = k for all x ∈ S
and χ(E ) ∈ Θ(k log log n).
Jain et al. [27] also showed that this is the best separation possible for an ensemble of quantum states with
a completely mixed ensemble average.
Putting these together, we get:
Theorem 5.3. Let δ ∈ (0, 1] and H be Hilbert space with dimension n. Then, for every positive real
number k ≥ 1 such that log2 n > 36k 2 , there is a finite set S and a function Q : S → D(H) such that T(Q) ∈
Ω(k log log n) while
k
1
min max Dδmax (Q(x)kσ) ≤
+ log
.
2
σ∈D(H) x∈S
δ
1 − δ2
Proof: Let S be the set S and E = {(λx , ξx ) : x ∈ S} the ensemble givenP
by Theorem 5.2. Let Q : S → D(H)
be the function such that Q(x) = ξx for all x ∈ S. Suppose that ξ := x∈S λx ξx is the ensemble average.
Then we have
min max Dδmax (Q(x)kσ)

σ∈ D(H) x∈S

max Dδmax (Q(x)kξ)

≤

x∈S

maxx Dobs (Q(x)kξ)
1
+ log
δ2
1 − δ2
1
k
+ log
,
=
δ2
1 − δ2
where the second inequality is derived using the Substate theorem (Theorem 5.1). Moreover, by definition of
the maximum possible information T(Q), we have T(Q) ≥ χ(E ). This gives us the existence of the required
function Q.
≤

Jain [25] also gave a lower bound of T(Q)/2 for exact remote state preparation. The above observation also
implies that allowing remote state preparation with non-zero error in approximating the state may decrease
the communication cost asymptotically. By Theorem 5.3, we get a function Q for which the worst-case
complexity with zero error Q∗ (RSP(S, Q), 0) ∈ Ω(k log log n), while for any ǫ ∈ (0, 1], the complexity with
error ǫ is
1
k
+ log
,
Q∗ (RSP(S, Q), ǫ) ≤
2
δ
1 − δ2
ǫ
where δ := 2√1+ǫ
.
2
20

5.2

Average-case error vs. worst-case error

Requiring bounded worst-case error in approximating states in remote state preparation is more demanding,
and potentially requires more communication, as compared to the average case. Here we quantify how much
more expensive it could be.
For the rest of this subsection, we let n be a positive integer, fix S = {1, 2, . . . , 2n }, H = span {|xi : x ∈ S},
and define Q : S → D(H) by Q(x) = |xihx| for all x ∈ S.
√
Proposition 5.4. For every ǫ ∈ [0, 1/ 2 ), there is a probability distribution pǫ over the set S such that
Q∗pǫ (RSP(S, Q), ǫ) = 0, while Q∗ (RSP(S, Q), ǫ) ≥ n.
Using quantum teleportation, any set of quantum states in space H can be prepared with zero error with
communication cost 2n. Thus, the above separation is maximal, up to the factor of 2.
To prove Proposition 5.4, we first analyze worst-case error protocols.
√
Lemma 5.5. For any ǫ ∈ [0, 1/ 2 ), Q∗ (RSP(S, Q), ǫ) ≥ n.
Proof: Given any ARSP protocol Π for the given set of states Q, we construct an LOCC protocol Π′ for
transmitting n bits:
Protocol Π′
1. Alice, with input x ∈ S, and Bob (with no input) simulate the protocol Π.
2. Let σx be the output of Π, obtained by Bob. Bob measures σx according to the projective measurement (|yihy| : y ∈ S).
The communication complexity of Π′ equals that of Π.
Suppose Alice is given a uniformly random input, and let X be the corresponding random variable. Let Y
be the random variable corresponding to Bob’s output in Π′ . Then, by the monotonicity of fidelity under
quantum channels, the success probability of Π′ is
1 X
F(σx , Q(x))2 ≥ 1 − ǫ2 .
Pr[Y = X] ≥
2n x
By Theorem 1.2, the communication cost of Π′ , and therefore of Π, is at least n+log(1−ǫ2 ). Since ǫ ∈ [0, √12 ),
we have log(1 − ǫ2 ) > −1. So Q∗ (RSP(S, Q), ǫ) ≥ n.
We show that the complexity of the task drops drastically, if average-case error is considered.
√
Lemma 5.6. For every ǫ ∈ [0, 1/ 2 ), There is a probability distribution pǫ over the set S such that
Q∗pǫ (RSP(S, Q), ǫ) = 0.
Proof: Fix some x0 ∈ S. Let pǫ be the probability distribution defined by
(√
1 − ǫ2 x = x0
√
pǫ,x =
1− 1−ǫ2
x 6= x0 .
2n −1
Consider the protocol Π in which Alice does not send any message to Bob, and Bob always prepares the
state Q(x0 ) = |x0 ihx0 |. The final joint state of the input-output registers in the protocol Π is
X
ρ′AB =
pǫ,x |xihx| ⊗ Q(x0 )
x∈S

21

and the communication cost is zero. Denoting by ρAB the ideal input-output state, we have
p
F(ρAB , ρ′AB ) ≥
1 − ǫ2 .

So Q∗p (RSP(S, Q), ǫ) = 0.

Thus we conclude Proposition 5.4. In fact we can construct an ensemble independent of ǫ, which exhibits a
similar disparity between worst and average-case ARSP.
√
Proposition 5.7. There is a probability distribution p over S such that for every ǫ ∈ [0, 1/ 2 ), we have
Q∗p (RSP(S, Q), ǫ)

≤


n
2 o
+2 .
log min 2n , log2 2
ǫ

Proof: Let m := 2n . Define p as the geometrically decreasing probability distribution
(
1
x ∈ {1, . . . , m − 1}
2x
px =
.
1
x=m
2m−1
Now consider the following protocol Π for ARSP. If Alice’s input x belongs to the set {1, . . . , t} with t =
min{⌈log ǫ22 ⌉, m}, then she sends x to Bob. Otherwise, she sends a random number chosen from the
set {1, . . . , t} to Bob. After receiving Alice’s message y, Bob outputs the state Q(y).
In protocol Π, the final state of Alice and Bob is of the form
ρ′AB

:=

m
X

x=1

px |xihx| ⊗ σx ,

where σx = Q(x) for x ≤ t. Consequently
F(ρAB , ρ′AB )

=

m
X

px F(Q(x), σx )

x=1

≥

t
X

x=1

px

≥

p

1 − ǫ2 .

Therefore, the average-case error is at most ǫ, and the communication is ⌈log t⌉. This implies that
Q∗p (RSP(S, Q), ǫ)
as claimed.

≤


n
2 o
log min 2n , log 2
+2 ,
ǫ

This example illustrates that the more sharply skewed the probability distribution over Q, the bigger the
gap between the worst-case and the average-case is. The example in Lemma 5.6 is a limiting case of such a
distribution.

5.3

Connection to the asymptotic case

It is worth mentioning that our bounds for the average-case communication complexity of ARSP in the
one-shot scenario also gives the optimal bounds in the asymptotic scenario established earlier by Berry and
Sanders [7]. This can be derived using the Quantum Asymptotic Equipartition Property of max-information,
i.e., Theorem 2.6. In the asymptotic scenario, Alice is given n independent and identically distributed inputs.
Using the notation from Section 3, the target joint state of Alice’s input and Bob’s output is ρ(p)⊗n , and
the goal is to prepare it approximately on Bob’s side with average error ǫ.

22

Let q∗p (RSP(S, Q), ǫ) denote the asymptotic rate of communication complexity of ARSP with average error ǫ.
This is the limit of the communication complexity of preparing ρ(p)⊗n with average-case error ǫ, divided
by n, as n → ∞. By Theorems 3.1 and 3.3, we have


8
1 δ
1 ǫ
∗
⊗n
⊗n
Imax (A : B)ρ(p) + log2 ln 2 + 2 ,
I
(A : B)ρ(p)
≤ qp (RSP(S, Q), ǫ) ≤
lim
lim
n→∞ n
n→∞ n max
ǫ
where δ =

ǫ
√
.
2 2

So by inequalities (2.1) and (2.2) in Theorem 2.6, we get the following bounds:
I(A : B)ρ(p) − 2ǫ log(|A| |B|)

6

≤

q∗p (RSP(S, Q), ǫ)

≤

I(A : B)ρ(p) .

On LOCC protocols for transmitting bits

In this section, we digress from the main theme of this article; we characterize the communication required
to convey classical bits through LOCC protocols as in Theorem 1.2. We have used this in Section 5 to
highlight a key difference between worst-case and average-case protocols for remote state preparation.
Consider the following communication task T :
Two physically separated parties, Alice and Bob, have unlimited computational power and can
communicate with each other. Alice is given a uniformly random n-bit string X unknown to
Bob, that is independent of their initial state. Alice and Bob communicate with each other so
that Bob learns X with probability at least p ∈ (0, 1].
Consider a classical communication protocol in which Alice sends exactly ⌈n − log p1 ⌉ bits of X, and Bob
chooses uniformly random bits as his guess for the remaining bits. Then the probability that Bob correctly
decodes Alice’s message is at least p. In this section, we show that even if we allow Alice and Bob to use
LOCC protocols, the classical communication complexity of the task T does not decrease. In other words, in
any (potentially two-way) LOCC protocol for this task, Alice sends at least n + log p bits in order to achieve
success probability at least p (Theorem 1.2). Nayak and Salzman [35] showed that in any two-way quantum
communication protocol with shared entanglement for the task T , Alice sends at least 12 (n + log p) qubits to
Bob. We obtain Theorem 1.2 by strengthening their proof.

6.1

Preparation

In LOCC protocols we assume that Alice and Bob each have access to an arbitrarily large but finite supply
of qubits in some fixed basis state, say |0̄i. Without loss of generality, we further assume that during a
protocol, each party performs some unitary operation followed by the measurement of a subset of qubits in
the standard basis. Note that any measurement can be implemented in this manner [37, Sec 2.2.8]. Further,
if the subset of qubits measured is of size k, we may assume that it consists of the leftmost k qubits.
We state some properties of protocols and states from Ref. [35] which are used later in this section. For
completeness we include their proofs here.
Proposition 6.1 ([35]). In any communication protocol with prior entanglement and local quantum channels,
we may assume that the initial shared quantum state is of the form
X
(1A ⊗ Λ)
|riA |riB ,
r∈{0,1}e

for some Λ :=

P

r∈{0,1}e

√
P
λr |rihr| with λr ≥ 0, r∈{0,1}e λr = 1, and for some integer e ≥ 1.
23

Proof: Without loss of generality, assume
and Bob hold eA and eB qubits of the initial state,
P that Alice
√
respectively, where eB ≥ eA . Let |φi = i∈{0,1}eA γi |ai iA |bi iB be a Schmidt decomposition of the initial
shared state.
√
P
We define a new protocol in which Alice and Bob start with the shared state |ψi := r∈{0,1}eB λr |riA |riB ,
where λ0̄s = γs for s ∈ {0, 1}eA and is zero otherwise. The state simplifies to
X √
γi |0̄, iiA |0̄, iiB .
i∈{0,1}eA

Using appropriate local unitary operators, Alice and Bob produce the state |φi (tensored with some fixed
pure state), and then run the original protocol.
Proposition 6.2 ([35]). For any linear transformation T on e qubits and any orthonormal set {|φa i : a ∈
{0, 1}e } over e′ ≥ e qubits,
X
X
T |ai ⊗ |φa i =
|ai ⊗ T̃ |φa i ,
a∈{0,1}e

a∈{0,1}e

P
where T̃ is any transformation on e′ qubits such that for all a′ ∈ {0, 1}e , T̃ |φa′ i = a∈{0,1}e ha′ |T |ai|φa i.
If T is a unitary operation, then we may take T̃ to be a unitary operation on e′ qubits.
Proof: Since the set {|ai : a ∈ {0, 1}e } is an orthonormal basis for the Hilbert space of e qubits, we have
X
XX
T |ai|φa i =
ha′ |T |ai|a′ i|φa i
a

a′

X

|a′ i

a∈{0,1}e

=

a′

=

X
a′

′

X
a

ha′ |T |ai|φa i

|a iT̃ |φa′ i ,

as claimed. The second part of the proposition is straightforward.
We also use this property in the following form in our analysis. The proof is straightforward, and is omitted.
P
Corollary 6.3. For any controlled unitary operation T :=
z∈{0,1}m |zihz| ⊗ Tz on a classical-quantum
register with m bits and e qubits, and collections of orthonormal sets {|ψza i : a ∈ {0, 1}e} over e′ qubits
m
with e′ ≥ e and z ∈ {0, 1} ,
X
X
X
X
|zai ⊗ T̃ (|zi|ψza i) ,
T |zai ⊗ |zi|ψza i =
z∈{0,1}m a∈{0,1}e

z∈{0,1}m a∈{0,1}e

where T̃ := z∈{0,1}m |zihz| ⊗ T̃z , and (T̃z ) is a sequence of unitary transformations on e′ qubits such that
P
for all z ∈ {0, 1}m and a′ ∈ {0, 1}e, T̃z |ψza′ i = a∈{0,1}e ha′ |Tz |ai|ψza i.
P

6.2

One-way LOCC protocols

As a warm-up, we prove the analogue of Theorem 1.2 for one-way LOCC protocols.
Theorem 6.4. Let Y be Bob’s output in any one-way LOCC protocol for task T when Alice receives uniformly
distributed n-bit input X. Let p := Pr[Y = X] be the probability that Bob gets the output X. Then
m

≥

n − log

1
,
p

where m is the number of classical bits Alice sends to Bob in the protocol.
24

P
Proof: Using Proposition 6.1, we assume that the initial shared entangled state is r∈{0,1}e |riΛ|ri for
√
P
P
some Λ :=
λr |rihr| with λr ≥ 0 and
r∈{0,1}e
r∈{0,1}e λr = 1, and some e ≥ 1. As explained in
Section 6.1, first Alice performs a unitary transformation on her part of the initial state depending on her
input X and measures the left-most m qubits in the standard basis. Let Ux be the unitary operation Alice
uses when she is given x as input. After the unitary operation Ux is performed, the joint state is
X
X
(Ux ⊗ 1)(1 ⊗ Λ)
|ri ⊗ |ri = (1 ⊗ Λ)(Ux ⊗ 1)
|ri ⊗ |ri
r∈{0,1}e

r∈{0,1}e

=

(1 ⊗ Λ)(1 ⊗ UxT )
X

=

r∈{0,1}e

X

r∈{0,1}e

|ri ⊗ |ri

(By Proposition 6.2)

|riΛUxT |ri .

Then Alice measures the state as described above and sends Bob the outcome of her measurement. Bob’s
state after this step is
X
ξx =
|zihz| ⊗ ΛUxT (|zihz| ⊗ 1)U x Λ∗ .
z∈{0,1}m

Note that
ξx

=



(1 ⊗ Λ) 

X

z∈{0,1}m



|zihz| ⊗ UxT (|zihz| ⊗ 1)U x  (1 ⊗ Λ∗ )

≤

(1 ⊗ ΛΛ∗ ) ,

(6.1)

where the identity operator acts on a 2m dimensional space. Finally, Bob performs a projective measurement {Py }y∈{0,1}n on his qubits, and gets as outcome the random variable Y . The success probability p of
the protocol is
X
Pr[X = x] Pr[Y = x|X = x]
Pr[X = Y ] =
x∈{0,1}n

=

X

x∈{0,1}n

≤
=
=

1
Tr (Px ξx )
2n


1 X
Tr Px (1 ⊗ ΛΛ∗ )
n
2 x

(By equation (6.1))

1
Tr(1 ⊗ ΛΛ∗ )
2n
2m
.
2n

We conclude that m ≥ n + log p.

6.3

The extension to two-way LOCC protocols

We now extend the above result to any two-way LOCC protocol. In particular we prove Theorem 1.2, which
we restate here for convenience.
Theorem 6.5. Let Y be Bob’s output in any two-way LOCC protocol for task T when Alice receives uniformly
distributed n-bit input X. Let mA be the total number of bits Alice sends to Bob, and p := Pr[Y = X] be the
probability that Bob produces output X. Then
mA

≥

n − log
25

1
.
p

To prove the theorem, we characterise the joint state of Alice and Bob at the end of a bounded round LOCC
protocol.
Lemma 6.6. Let Π be a bounded round LOCC protocol. Let e be the initial number of qubits with each of
Alice and Bob, q be the total number of bits sent by Alice to Bob, q ′ be the total number of bits sent by Bob
to Alice, and m be the total number of bits exchanged in Π (so m = q + q ′ ). Then Alice and Bob’s joint state
at the end of the protocol (before the measurement for producing the output) can be written as
X
X
|z, rihz, s|A ⊗ Λ|φz,r ihφz,s |B Λ∗ ,
z∈{0,1}m r,s∈{0,1}e−q

where
1. A and B are classical-quantum registers with m-bit classical parts that contain the transcript of the
protocol; register A is with Alice, and B with Bob,
2. Λ is a linear transformation that maps classical-quantum states with m bits and e qubits to classicalquantum states of the same form, depends only on the initial joint state and the unitary transformations
applied by Bob, and satisfies Tr(ΛΛ∗ ) = 2q ; and
3. {|φz,r i} is an orthonormal set of classical-quantum states of the form |φz,r i := |zi|ψz,r i over m-bits
and e qubits, and depends only on the initial joint state and the unitary transformations applied by
Alice.
Proof: Suppose that Π is a t-round LOCC protocol. Let ρi be the joint state of Alice and Bob after i-th
round, and mi be the total number of bits exchanged by Alice and Bob in the first i rounds, of which qi bits
are sent by Alice, for 1 ≤ i ≤ t. Let ρ0 be their initial state.
We prove the lemma by induction on t.
Base Case:
have

Suppose that Π is a zero communication LOCC protocol, i.e., t = 0. By Proposition 6.1, we
X
|rihs| ⊗ Λ|rihs|Λ∗ ,
ρ0 =
r,s∈{0,1}e

√
P
where Λ = r∈{0,1}e λr |rihr| for some λr ≥ 0 and r λr = 1. Since Tr(ΛΛ∗ ) = 1, the state ρ0 satisfies the
claimed properties.
P

Induction Hypothesis: Suppose the lemma holds for any l-round LOCC protocol, for some l ≥ 0.
Inductive Step: Suppose that Π is an (l + 1)-round protocol. By the induction hypothesis, after the first l
rounds of communication we have
X
X
|z, rihz, s| ⊗ Λl |φz,r ihφz,s |Λ∗l ,
ρl =
z∈{0,1}ml r,s∈{0,1}e−ql

where Λl and |φz,r i satisfy the properties stated in the lemma. In particular, suppose |φz,r i := |zi|ψz,r i for
each z, r. We show that at the end of the protocol ρl+1 is in the required form as well. Consider the (l + 1)-th
round of Π.
Case (1): Suppose P
that the communication in the last round is from Alice to Bob. Alice applies a unitary
transformation U := z |zihz|⊗Uz , which acts on the quantum part of her register, controlled by the classical
part of her register. She then measures the k leftmost qubits in the standard basis, appends the outcome to

26

the message transcript in her classical register, and sends the outcome a of her measurement to Bob. The
joint state after applying U is




(U ⊗ 1)(1 ⊗ Λl ) 


X

r,s∈{0,1}e−ql
z∈{0,1}ml

=

=

(1 ⊗ Λl )

"

(1 ⊗ Λl )

"

X

r,s,z

X

r,s,z



|z, rihz, s| ⊗ |φz,r ihφz,s | (1 ⊗ Λ∗l )(U ∗ ⊗ 1)

#

∗

U |z, rihz, s|U ⊗ |φz,r ihφz,s | (1 ⊗ Λ∗l )
|z, rihz, s| ⊗ Ũ |φz,r ihφz,s |Ũ

∗

#

(1 ⊗ Λ∗l ) ,

P

where Ũ :=
z |zihz| ⊗ Ũz is the unitary operation given by Corollary 6.3. After Alice performs her
measurement and sends the measurement outcome a to Bob, say he stores the message in register M . Denote
by 1M ⊗ Λl Ũ the operator Λl Ũ on the registers originally with Bob, extended to include the register M .
(The order of the operators in tensor product does not represent the order of the registers.) The joint state
then may be expressed as below.

ρl+1

=

X

r ′,s′ ∈{0,1}e−(ql +k)
a∈{0,1}k
z∈{0,1}ml

|za, r′ ihza, s′ | ⊗ (1M ⊗ Λl Ũ )(|zihz| ⊗ |aiha|M ⊗ |ψz,ar′ ihψz,as′ |)(1M ⊗ Ũ ∗ Λ∗l ) ,

where Λl Ũ acts on the classical-quantum register with Bob before the message was sent. We define Λl+1 :=
1M ⊗ Λl , and |φz′ ,r′ i := |zai ⊗ Ũz |ψz,ar′ i, where z ′ := za. Noting that ml+1 = ml + k and ql+1 = ql + k, we
have
X
ρl+1 =
|z ′ , r′ ihz ′ , s′ | ⊗ Λl+1 |φz′ ,r′ ihφz′ ,s′ |Λ∗l+1 .
r ′ ,s′ ∈{0,1}e−ql+1
z ′ ∈{0,1}ml+1

Further note that Tr(Λl+1 Λ∗l+1 ) = 2ql+1 and {|φz′ ,r′ i} is an orthonormal set of the claimed form.
Case (2): Suppose that
P the communication in the last round is from Bob to Alice. Bob applies a unitary
transformation V :=
z |zihz| ⊗ Vz to the quantum part of his register, controlled by the classical part
of his register. Then he measures the k leftmost qubits (say in sub-register L) in the standard basis, and
appends the outcome b to the message transcript, in classical register M . Finally, he sends the outcome b of
the measurement to Alice. Denote by 1M ⊗ (hb|L ⊗ 1)V Λl , the extension of the operator (hb|L ⊗ 1)V Λl to
include the register M . (Here, the order of the operators in tensor product does not represent the order of
the registers on which they act. The same applies to the operator Λl+1 defined below.) The joint state then
is as follows.
X
|zb, rihzb, s| ⊗ (1M ⊗ (hb|L ⊗ 1)V Λl )(|zbihzb| ⊗ |ψz,r ihψz,s |)(1M ⊗ Λ∗l V ∗ (|biL ⊗ 1)) .
ρl+1 =
r,s∈{0,1}e−ql
b∈{0,1}k
z∈{0,1}ml

P
Note that ql+1 = ql , and ml+1 = ml +k. Define Λl+1 := b |bihb|M ⊗(hb|L ⊗1)V Λl and |φz′ ,r′ i = |zbi⊗|ψz,br′ i,
where z ′ := zb. It is straightforward to verify that Tr(Λl+1 Λ∗l+1 ) = 2ql+1 , the set {|φz′ ,r′ i} is of the claimed
form, and
X
|z ′ , r′ ihz ′ , s′ | ⊗ Λl+1 |φz′ ,r′ ihφz′ ,s′ |Λ∗l+1 .
ρl+1 =
r ′ ,s′ ∈{0,1}e−ql+1
z ′ ∈{0,1}ml+1

27

This completes the proof.
We are ready to prove Theorem 1.2, restated in this section as Theorem 6.5.
Proof of Theorem 6.5: By Lemma 6.6, at the end of any two-way LOCC protocol, when Alice has
n
input x ∈ {0, 1} , Bob’s state before performing his final measurement to get Y is
X
Λ|φz,r (x)ihφz,r (x)|Λ∗ ,
ξx =
r∈{0,1}e−mA
z∈{0,1}m

for some linear transformation Λ with Tr(ΛΛ∗ ) = 2mA and orthonormal set {|φz,r (x)i}z,r . The transformation Λ only depends on Bob’s unitary operations and the initial state, and is therefore independent of Alice’s
input x. Note that
ξx ≤ ΛΛ∗ .
(6.2)

After Bob performs his final projective measurement {Py }y∈{0,1}n and gets the output Y , the probability of
correctly recovering an input X chosen uniformly at random is
1 X
p := Pr[Y = X] =
Tr(Px ξx )
2n
n
x∈{0,1}

≤

1 X
Tr(Px ΛΛ∗ )
2n x

1
Tr(ΛΛ∗ )
2n
Therefore, we have mA ≥ n − log p1 , as required.
=

7

=

(Equation (6.2))
2 mA
.
2n

Conclusion

In this article, we studied the communication complexity of remote state preparation in the one-shot scenario.
Our main results can be summarized as follows:
• The communication complexity of remote state preparation with bounded average-case error ǫ can be
characterized tightly in terms of the smooth max-information Bob’s output has about Alice’s input.
• The communication complexity of remote state preparation with bounded worst-case error ǫ can be
characterized in terms of a similar natural expression involving smooth max-relative entropy.
The bounds we derive for the worst-case communication complexity are provably tighter than earlier ones.
We also show out how protocols that guarantee low worst-case error necessarily use more communication
than those that require low error on average. In the process, we strengthen a lower bound on LOCC protocols
for transmitting classical bits.
In this work, we focused on the remote preparation of a possibly mixed quantum state. However, often the
quantum state to be remotely prepared is entangled with other systems (“the environment”). We can consider
the problem of preparing an approximation of the quantum state such that its entanglement with other
systems does not change significantly. This problem has been studied in asymptotic scenario [6, 7]. Berta [8]
implicitly studied this problem in the one-shot scenario by considering the quantum state merging problem,
and showed that the minimal entanglement cost needed for this problem is equal to minus the ǫ-smooth
conditional min-entropy of Alice’s register conditioned on the environment, while classical communication is
allowed for free. Note that the entanglement cost is defined as the difference between the number of bits of
pure entanglement at the beginning and at the end of the process. It would be interesting to characterize the
minimum classical communication of such “faithful” ARSP in terms of non-asymptotic information theoretic
quantities.
28

References
[1] Scott Aaronson. Guest column: NP-complete problems and physical reality. SIGACT News, 36(1):30–
52, March 2005.
[2] Shima Bab Hadiashar. Communication Complexity of Remote State Preparation. Master’s Thesis,
University of Waterloo, Waterloo, Canada, May 2014.
[3] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K.
Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70(13):1895–1899, March 1993.
[4] Charles H. Bennett, David P. DiVincenzo, Peter W. Shor, John A. Smolin, Barbara M. Terhal, and
William K. Wootters. Remote state preparation. Physical Review Letters, 87(7):077902, July 2001.
[5] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state
entanglement and quantum error correction. Physical Review A, 54:3824–3851, Nov 1996.
[6] Charles H. Bennett, Patrick Hayden, Debbie W. Leung, Peter W. Shor, and Andreas Winter. Remote
preparation of quantum states. IEEE Transactions on Information Theory, 51(1):56–74, January 2005.
[7] Dominic W. Berry and Barry C. Sanders. Optimal remote state preparation. Physical Review Letters,
90:057901, February 2003.
[8] Mario Berta. Single-Shot Quantum State Merging. Diploma thesis, ETH, Zurich, February 2008.
[9] Mario Berta, Matthias Christandl, and Renato Renner. The Quantum Reverse Shannon theorem based
on one-shot information theory. Communications in Mathematical Physics, 306(3):579–615, September
2011.
[10] Igor Bjelakovic and Rainer Siegmund-Schultze. Quantum Stein’s lemma revisited, inequalities for quantum entropies, and a concavity theorem of Lieb. Technical Report arXiv:quant-ph/0307170v2, arXiv.org,
2003.
[11] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the
real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American
Mathematical Society, 21:1–46, 1989.
[12] Fernando G. S. L. Brandão and Nilanjana Datta. One-shot rates for entanglement manipulation under
non-entangling maps. IEEE Transactions on Information Theory, 57(3):1754–1760, March 2011.
[13] Francesco Buscemi and Nilanjana Datta. The quantum capacity of channels with arbitrarily correlated
noise. IEEE Transactions on Information Theory, 56(3):1447–1460, March 2010.
[14] Eric Chitambar, Debbie Leung, Laura Mancinska, Maris Ozols, and Andreas Winter. Everything You
Always Wanted to Know About LOCC (But Were Afraid to Ask). Communications in Mathematical
Physics, 328(1):303–326, 2014.
[15] Nikola Ciganovic, Normand J. Beaudry, and Renato Renner. Smooth max-information as one-shot
generalization for mutual information. Information Theory, IEEE Transactions on, 60(3):1573–1581,
March 2014.
[16] Nilanjana Datta. Min- and max-relative entropies and a new entanglement monotone. IEEE Transactions on Information Theory, 55(6):2816–2826, June 2009.
[17] Igor Devetak and Toby Berger. Low-entanglement remote state preparation. Physical Review Letters,
87(19), October 2001.
[18] Dawei Ding and Mark M. Wilde. Strong converse exponents for the feedback-assisted classical capacity
of entanglement-breaking channels. Technical Report arXiv:1506.02228v4 [quant-ph], arXiv.org, 2017.
29

[19] Frédéric Dupuis, Lea Kraemer, Philippe Faist, Joseph M. Renes, and Renato Renner. Generalized
entropies. In Proceedings of the XVIIth International Congress on Mathematical Physics, Aalborg,
Denmark, 2012, pages 134–153, August 2012.
[20] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and
ideal quantum processes. Physical Review A, 71:062310, Jun 2005.
[21] Akihisa Hayashi, Takeji Hashimoto, and Minoru Horibe. Remote state preparation without oblivious
conditions. Physical Review A, 67:052302, May 2003.
[22] Masahito Hayashi.
Role of hypothesis testing in quantum information.
arXiv:1709.07701 [quant-ph], arXiv.org, 2017.

Technical Report

[23] Masato Hayashi and Hiroshi Nagaoka. A general formula for the classical capacity of a general quantum
channel. In Proceedings of the IEEE International Symposium on Information Theory. IEEE, 2002.
[24] Fumio Hiai and Dénes Petz. The proper formula for relative entropy and its asymptotics in quantum
probability. Communications in Mathematical Physics, 143(1):99–114, 1991.
[25] Rahul Jain. Communication complexity of remote state preparation with entanglement. Quantum
Information & Computation, 6(4):461–464, July 2006.
[26] Rahul Jain and Ashwin Nayak. Short proofs of the quantum Substate theorem. IEEE Transactions on
Information Theory, 58(6):3664–3669, June 2012.
[27] Rahul Jain, Ashwin Nayak, and Yi Su. A separation between divergence and Holevo information for
ensembles. Mathematical Structures in Computer Science, 20(5):977–993, 2010.
[28] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In Proceedings of the
43rd Annual IEEE Symposium on Foundations of Computer Science, pages 429–438, 2002.
[29] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and
privacy in quantum communication. In Proceedings of the Twentieth Annual IEEE Conference on
Computational Complexity, 2005, pages 285–296, June 2005.
[30] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A property of quantum relative entropy with an
application to privacy in quantum communication. Journal of the ACM, 56(6):33:1–33:32, September
2009.
[31] Felix Leditzky, Mark M. Wilde, and Nilanjana Datta. Strong converse theorems using Rényi entropies.
Journal of Mathematical Physics, 57(8):082202, 2016.
[32] Debbie W. Leung and Peter W. Shor. Oblivious remote state preparation. Physical Review Letters,
90(12):127905, March 2003.
[33] Hoi-Kwong Lo. Classical-communication cost in distributed quantum-information processing: A generalization of quantum-communication complexity. Physical Review A, 62(1):012313, June 2000.
[34] William Matthews and Stephanie Wehner. Finite blocklength converse bounds for quantum channels.
IEEE Transactions on Information Theory, 60(11):7317–7329, 2014.
[35] Ashwin Nayak and Julia Salzman. Limits on the ability of quantum states to convey classical messages.
Journal of the ACM, 53(1):184 – 206, January 2006.
[36] Ashwin Nayak and Peter Shor. Bit-commitment-based quantum coin flipping. Physical Review A,
67:012304, January 2003.
[37] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge
university press, 2010.
30

[38] Tomohiro Ogawa and Hiroshi Nagaoka. Strong converse and Stein’s lemma in quantum hypothesis
testing. IEEE Transactions on Information Theory, 46(7):2428–2433, 2000.
[39] Martin J. Osborne and Ariel Rubinstein. A Course in Game Theory. MIT Press, 1994.
[40] Alexey E. Rastegin. Relative error of state-dependent cloning. Physical Review A, 66(4):042304, 2002.
[41] Alexey E. Rastegin. A lower bound on the relative error of mixed-state cloning and related operations.
Journal of Optics B: Quantum and Semiclassical Optics, 5(6):S647, 2003.
[42] Alexey E. Rastegin. Sine distance for quantum states. Technical Report arxiv:quant-ph/0602112,
arXiv.org, 2006.
[43] Renato Renner. Security of Quantum Key Distribution. PHD thesis, ETH, Zurich, December 2005.
[44] Renato Renner and Stefan Wolf. Smooth Rényi entropy and applications. In IEEE International
Symposium on Information Theory, page 233, 2004.
[45] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth min- and maxentropies. IEEE Transactions on Information Theory, 56(9):4674–4681, September 2010.
[46] Marco Tomamichel and Masahito Hayashi. A hierarchy of information quantities for finite block length
analysis of quantum tasks. IEEE Transactions on Information Theory, 59(11):7693–7710, November
2013.
[47] Dave Touchette. Quantum information complexity. In Proceedings of the Forty-Seventh Annual ACM
on Symposium on Theory of Computing, pages 317–326. ACM, 2015.
[48] Ligong Wang and Renato Renner. One-shot classical-quantum capacity and hypothesis testing. Physical
Review Letters, 108:200501, May 2012.
[49] John Watrous. Theory of Quantum Information. 2016. Book draft, September 2016. Available at
https://cs.uwaterloo.ca/~watrous/TQI/ .
[50] Mark M. Wilde, Andreas Winter, and Dong Yang. Strong converse for the classical capacity of
entanglement-breaking and hadamard channels via a sandwiched Réenyi relative entropy. Communications in Mathematical Physics, 331(2):593–622, October 2014.
[51] Andrew Chi-Chih Yao. Quantum circuit complexity. In Proceedings of the 34th Annual Symposium on
Foundations of Computer Science, 1993, pages 352–361, November 1993.

A

Some properties of entropic quantities

In this section, we present the proofs of some properties of information-theoretic quantities stated in Section 2.4. For convenience, we restate the properties here.
Proposition A.1 (Proposition 2.5). Let ρAB ∈ D(H′ ⊗ H) be a bipartite quantum state that is classical
on A. For any ǫ ≥ 0, there exists ρ′AB ∈ Bǫ (ρAB ) ∩ D(H′ ⊗ H) classical on A such that
Iǫmax (A : B)ρ

=

Imax (A : B)ρ′ .

Proof: Let λ = Iǫmax (A : B)ρ , and ρ̃AB ∈ Bǫ (ρAB ) and σB ∈ D(H) be two quantum states for which
ρ̃AB

≤

2λ ρ̃A ⊗ σB .

31

Without loss of generality, we assume that ρ̃AB has trace equal to one, i.e., ρ̃AB ∈ Bǫ (ρAB ) ∩ D(H′ ⊗ H). If
not, we consider the state ωAB := Tr(ρ̃AB
ρ̃AB ) instead of ρ̃AB . Since ρ has trace 1, P(ω, ρ) ≤ P(ρ̃, ρ). Further,
λ
ωAB ≤ 2 ωA ⊗ σB .
Let ΦA : L(H) → L(H) be a quantum-to-classical channel such that:
X
hei |X|ei i|ei ihei |
ΦA (X) =
i

for all X ∈ L(H), where {|ei i} is the standard basis for L(H). Let ρ′AB = (ΦA ⊗ 1B )(ρ̃AB ). By the definition
of ρ′AB and the monotonicity of purified distance ρ′AB ∈ Bǫ (ρAB ) ∩ D(H′ ⊗ H).
By optimality of ρ̃AB , we have
Iǫmax (A : B)ρ

=

Imax (A : B)ρ̃

≤

Imax (A : B)ρ′ ,

and by Proposition 2.4, monotonicity of smooth max-information, we have
Imax (A : B)ρ′

≤

Imax (A : B)ρ̃ .

Iǫmax (A : B)ρ

=

Imax (A : B)ρ′ ,

Therefore, we conclude that
where ρ′AB ∈ Bǫ (ρAB ) ∩ D(H′ ⊗ H) and is classical on A.
Proposition A.2 (Proposition 2.8). Let ρAB (p) ∈ D(HA ⊗ HB ) be a state classical on A such that the
distribution on A is given by the probability vector p. Let ρA (p) = TrB (ρAB (p)), and σ ∈ D(HB ) be a
quantum state on Hilbert space HB . Then the function βǫ (ρAB (p) k ρA (p) ⊗ σ) is convex with respect to p.
Proof: Let p0 and p1 be two arbitrary probability distributions on the standard basis of HA . For λ ∈ [0, 1],
let q = λp0 + (1 − λ)p1 . We show that
βǫ (ρAB (q) k ρA (q) ⊗ σ)

≤

λ βǫ (ρAB (p0 ) k ρA (p0 ) ⊗ σ) + (1 − λ) βǫ (ρAB (p1 ) k ρA (p1 ) ⊗ σ) ,

which proves the claim.
Let Φ : L(HA ) → L(C2 ⊗ HA ) be the quantum channel with Kraus operators Aa,x =
0 (a)
1 (a)
a and x ∈ {0, 1}, where αa0 := λ pq(a)
and αa1 = (1 − λ) pq(a)
. Then we have
ρXAB (q)

=

(Φ ⊗ 1B )(ρAB (q))

=

√ a
αx |xi ⊗ |aiha| for all

λ |0ih0| ⊗ ρAB (p0 ) + (1 − λ) |1ih1| ⊗ ρAB (p1 ) .

Since ρXAB (q) is an extension of ρAB (q), using Proposition 2.7 twice, we get
βǫ (ρAB (q) k ρA (q) ⊗ σ)

βǫ (ρXAB (q) k ρXA (q) ⊗ σ) .

=

(A.1)

ǫ
For each x ∈ {0, 1}, let Qx be the
Pmeasurement operator that achieves β (ρAB (px ) k ρA (px ) ⊗ σ). Consider
the measurement operator Q := x∈{0,1} |xihx| ⊗ Qx . This satisfies

hQ, ρXAB (q)i

=

λ hQ0 , ρAB (p0 )i + (1 − λ) hQ1 , ρAB (p1 )i

≥

1−ǫ ,

by definition of Q0 , Q1 . By Eq. (A.1) and the definition of βǫ , we get
βǫ (ρAB (q) k ρA (q) ⊗ σ)

= βǫ (ρXAB (q) k ρXA (q) ⊗ σ)

≤ hQ, ρXA (q) ⊗ σi
= λ hQ0 , ρA (p0 ) ⊗ σi + (1 − λ) hQ1 , ρA (p1 ) ⊗ σi

= λ βǫ (ρAB (p0 ) k ρA (p0 ) ⊗ σ) + (1 − λ) βǫ (ρAB (p1 ) k ρA (p1 ) ⊗ σ) ,
as we set out to prove.
32

Proposition A.3 (Proposition 2.9). For any fixed quantum state ρ ∈ D(H), the function βǫ (ρkσ) is a
concave function with respect to σ.
Proof: For any choice of σ0 , σ1 ∈ D(H) and λ ∈ [0, 1], let Q be the measurement operator that achieves
hypothesis testing error βǫ (ρ k λσ0 + (1 − λ)σ1 ). Then
βǫ (ρ k λσ0 + (1 − λ)σ1 )

=
=
≥

hQ, λσ0 + (1 − λ)σ1 i

λ hQ, σ0 i + (1 − λ) hQ, σ1 i
λ βǫ (ρkσ0 ) + (1 − λ) βǫ (ρkσ1 ) ,

since hQ, ρi ≥ 1 − ǫ.

B

Preparing states from an infinite set

In this section, we discuss remote state preparation of states drawn from an infinite set. This scenario has
been studied by Lo [33] and in later works on the topic.
In remote state preparation, Alice’s input is supposed to provide a complete description of the state to be
prepared at Bob’s end. In any physically realistic model of computation, the description necessarily has finite
bit-length (see, e.g., Ref. [1]). For instance, if a d-dimensional quantum state is described by specifying Θ(d2 )
complex entries in the corresponding d×d matrix, the complex numbers would have to be specified with finite
precision. This implies that the input set S (following the notation in Section 2.6) is necessarily countable.
This point has not been addressed in previous works.
To meaningfully consider the preparation states drawn from an uncountable set, we may instead consider
approximations drawn from a suitable countable set. For example, instead of the set D(H) of all quantum
states over a d-dimensional space H, we may instead study the countably dense set of states whose matrix
representations only have complex entries with rational real and imaginary parts. Such states have unique
finite-length representations. (Similar approximation is also implicit in the case of RSP of a finite set of
states, when the corresponding matrices involve irrational numbers.)
Another approach, perhaps only of theoretical interest, would be to allow the local operations in an LOCC
protocol to be defined on a suitable generalization of the Real RAM model due to Blum, Shub, and Smale [11].
We do not attempt to define such a model of computation here. For our purposes, it would suffice to assume
a model which enables the implementation of quantum operations such as unitary operations controlled by
the registers holding real numbers in finite time.
We assume that we take one of the abovementioned approaches in the analysis in this section. The underlying
idea, that of approximating states from an infinite set with those from a net , probably applies in other
reasonable approaches as well.
As before, we restrict ourselves to states over a finite dimensional Hilbert space H.
Definition B.1. Let ν ∈ (0, 1] and D ⊆ D(H) be any set of quantum states. A ν-net N in D is a subset
of D such that for any state ρ ∈ D, there is a state σ ∈ N such that P(ρ, σ) < ν.
We argue that every subset of finite-dimensional states admits a finite net.
Proposition B.1. For every ν ∈ (0, 1], and every set D ⊆ D(H) of quantum states, there is a finite ν-net
in D.

33

Proof: Since D(H) is compact, it has a finite cover (Bi ) consisting of open balls of radius ν/2. This is
also a cover for any subset D of quantum states. Let N be a subset of D constructed by taking one point
from Bi ∩ D, whenever this intersection is non-empty. We claim that this is a finite ν-net in D.
Consider a state ρ ∈ D. Since (Bi ) is a cover for the set of all quantum states, ρ ∈ Bj for some j. By
construction, there is a state σ ∈ N from Bj ∩ D. Since ρ, σ both belong to the same ball Bj of radius ν/2,
we have P(ρ, σ) < ν. So N is a ν-net in D.
Suppose S is an infinite set, and Q : S → D(H) is a one-to-one function mapping each element of S to a quantum state. (We view an element x ∈ S as a description, i.e., unique encoding, of the quantum state Q(x).)
Define R := Q(S) as the image of S under Q; this is the set of quantum states under consideration. We fix
an approximation parameter ν > 0 of our choice, and a finite ν-net N in R, and let T := Q−1 (N ) be the set
of inputs corresponding to N . We bound the communication required for remote state preparation of states
from R with that for states from N . We may then appeal to Theorem 1.1 to infer bounds on RSP(S, Q).

Worst-case error. We first consider the simpler case, that of worst-case error ǫ > 0. Any protocol for
RSP(S, Q) with worst-case error ǫ is also a protocol for RSP(T, Q) as T is a subset of S. So we have
Q∗ (RSP(T, Q), ǫ)

Q∗ (RSP(S, Q), ǫ) .

≤

Now suppose Π is a protocol for RSP(T, Q) with communication cost c and worst case error ǫ. We design
a protocol Π′ for RSP(S, Q) as follows. Given an x ∈ S, Alice chooses y ∈ T such that P(Q(x), Q(y)) ≤ ν,
and prepares an approximation of Q(y) on Bob’s side using protocol Π. Suppose Bob’s output is σy . Then
P(Q(x), σy )

≤

P(Q(x), Q(y)) + P(Q(y), σy )

≤

ν +ǫ .

So Π′ is a protocol for RSP(S, Q) with communication cost c, and worst case error ǫ + ν. Therefore,
Q∗ (RSP(S, Q), ǫ + ν)

≤

Q∗ (RSP(T, Q), ǫ) .

Putting the two together, for ν, ǫ such that 0 < ν < ǫ, we get
Q∗ (RSP(T, Q), ǫ)

≤

Q∗ (RSP(S, Q), ǫ)

≤

Q∗ (RSP(T, Q), ǫ − ν) .

Average-case error. Next we consider approximate RSP with average error at most ǫ ∈ (0, 1] with respect
to a probability measure µ on the set of states R. For simplicity, we only consider the case when the open
sets in R generated by the metric P are measurable. Since Q is injective, we may equivalently consider µ as
a probability measure on S.
Let (ρi ) be an enumeration of the states in N , and (Bi ) be open balls of radius ν centred at ρi with respect
to the metric P. Since N is a ν-net in R, we have R ⊆ ∪i Bi . Define the function f : R → N as f (σ) := ρi
for all states σ ∈ (Bi ∩ R) \ (∪j<i Bj ). The function f maps each quantum state ρ ∈ R to a quantum state
in N such that P(ρ, f (ρ)) < ν. Moreover, it is measurable.
The function f induces a probability distribution p on N in the natural way:
pρi

:=

µ(f −1 (ρi ))

for ρi ∈ N . We may view the distribution p as being over the corresponding set T of inputs: for y ∈ T such
that Q(y) = ρi , we define py := pρi .
We relate protocols for RSP(S, Q) with average error ǫ with respect to µ to protocols for RSP(T, Q) with
average error “close” to ǫ with respect to p.
34

Lemma B.2. Suppose Π is a protocol for RSP(S, Q) with communication cost c and average error ǫ with
respect to µ. Then there is a protocol Π′ for RSP(T, Q) with communication cost c and average error at
most ν + ǫ with respect to p.
Proof: For y ∈ T , define Ry := f −1 (Q(y)), the set of states in R that are mapped to Q(y) ∈ N . Define Sy :=
Q−1 (Ry ), the set of inputs corresponding to the states in Ry . Note that (Ry ) is a partition of R and (Sy )
of S. Since f is measurable, Ry is a measurable set. When Ry has non-zero measure, we define a probability
measure µy on Ry as µy (W ) := µ(W )/µ(Ry ) for all measurable sets W ⊆ Ry . We also view µy as a
probability measure on Sy .
We now construct the protocol Π′ for RSP(T, Q) as follows. Given y ∈ T , Alice selects an input x ∈ Sy
randomly with respect to the probability measure µy and runs the protocol Π on this input.
The communication in Π′ is also c. Suppose σx is the output of the protocol Π when the input is x. Then
the average error of the protocol Π′ is
X Z
X Z
P(Q(y), σx ) dµy (x) =
py
P(Q(y), σx ) dµ(x)
y∈T

x∈Sy

y∈T

≤

x∈Sy

X Z

y∈T

+

X Z

y∈T

≤

P(Q(y), Q(x)) dµ(x)

x∈Sy

P(Q(x), σx ) dµ(x)

x∈Sy

ν +ǫ ,

as claimed.
Conversely, we can also derive a protocol for RSP(S, Q) from one for RSP(T, Q).
Lemma B.3. Suppose Π is a protocol for RSP(T, Q) with communication cost c and average error ǫ with
respect to the distribution p. There exists a protocol Π′ for RSP(S, Q) with communication cost c and average
error at most ǫ + ν with respect to µ.
Proof: In the protocol Π′ , given input x ∈ S, Alice runs the protocol Π on input y defined as y :=
Q−1 (f (Q(x))). This is the input corresponding to the state in the ν-net to which f maps Q(x). The
communication cost of Π′ is also c.
Suppose the output of Π′ on input x is σx . Note that f maps all states Q(x) for x ∈ Sy to the same
value Q(y), and therefore the outputs σx for all inputs x ∈ Sy are equal to σy .
The average error of the protocol with respect to µ is
Z
Z
Z
P(f (Q(x)), σx ) dµ(x)
P(Q(x), f (Q(x))) dµ(x) +
P(Q(x), σx ) dµ(x) ≤
x∈S
x∈S
x∈S
X Z
≤ ν+
P(f (Q(x)), σx ) dµ(x)
x∈Sy

y∈T

=

ν+

X Z

y∈T

=

ν+

X

P(Q(y), σy ) dµ(x)
x∈Sy

py P(Q(y), σy )

y∈T

≤

ν+ǫ ,

35

where in the third step we have used the abovementioned property that f is constant on Sy .
For ν, ǫ such that ν < ǫ, the above two lemmata imply that
Q∗p (RSP(T, Q), ǫ + ν)

≤

Q∗µ (RSP(S, Q), ǫ)

36

≤

Q∗p (RSP(T, Q), ǫ − ν) .

