On the Entanglement Cost of One-Shot Compression
Shima Bab Hadiashar and Ashwin Nayak
Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo,
200 University Ave. W., Waterloo, ON, N2L 3G1, Canada.
We revisit the task of visible compression of an ensemble of quantum states
with entanglement assistance in the one-shot setting. The protocols achieving
the best compression use many more qubits of shared entanglement than the
number of qubits in the states in the ensemble. Other compression protocols,
with potentially larger communication cost, have entanglement cost bounded
by the number of qubits in the given states. This motivates the question as to
whether entanglement is truly necessary for compression, and if so, how much
of it is needed.
Motivated by questions in communication complexity, we lift certain restric-
tions that are placed on compression protocols in tasks such as state-splitting
and channel simulation. We show that an ensemble of the form designed by
Jain, Radhakrishnan, and Sen (ICALP’03) saturates the known bounds on the
sum of communication and entanglement costs, even with the relaxed compres-
sion protocols we study.
The ensemble and the associated one-way communication protocol have
several remarkable properties. The ensemble is incompressible by more than a
constant number of qubits without shared entanglement, even when constant
error is allowed. Moreover, in the presence of shared entanglement, the commu-
nication cost of compression can be arbitrarily smaller than the entanglement
cost. The quantum information cost of the protocol can thus be arbitrarily
smaller than the cost of compression without shared entanglement. The en-
semble can also be used to show the impossibility of reducing, via compression,
the shared entanglement used in two-party protocols for computing Boolean
functions.
1 Introduction
1.1 Visible compression
Compression of quantum states is a fundamental task in information processing. In the
simplest setting, we have two spatially separated parties, commonly called Alice and Bob,
Shima Bab Hadiashar: sbabhadi@uwaterloo.ca
Ashwin Nayak: ashwin.nayak@uwaterloo.ca
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 1
arXiv:1905.02110v3 [quant-ph] 19 Jun 2020
who can communicate with each other by exchanging quantum states. They have in mind
an ensemble of m-dimensional quantum states
((p
x
, ρ
x
) : x ∈ S, ρ
x
∈ D(C
m
)) , (1.1)
where S is some non-empty finite set, and p is a probability distribution over S. Alice
gets an input x ∈ S with probability p
x
, and would like to send a message, i.e., a quantum
state σ
x
∈ D(C
d
) to Bob so that he can recover the state ρ
x
, or even an approximation to
it. Since the input x completely specifies the corresponding state ρ
x
, this variant of the
task is called visible compression. The communication cost of the protocol is log d, the
length of the message in qubits. Their goal is to accomplish this with as short a message
as possible, i.e., to minimize the dimension d. A central question in quantum information
theory is whether there is a simple characterization of the optimal communication cost in
terms of the “information content” of the ensemble.
An additional resource that Alice and Bob may use in compression is a shared entangled
state. In other words, the two parties may start with their qubits initialized to a fixed pure
quantum state independent of the input received by Alice. The local quantum operations
performed for compression and decompression then also involve the respective parts of the
shared state. This is depicted in Figure 1, and the protocol (or channel) is said to be with
shared entanglement or entanglement assisted. As we may expect, the communication cost
may decrease due to the availability of this additional resource. The entanglement cost of
a protocol is the minimal dimension of the support of either party’s share of the initial
state (measured in qubits) required to achieve some communication cost. (We discuss the
notion of entanglement cost in detail in Section 4.) We would also like to characterize the
entanglement cost in this setting, in addition to the communication cost.
|x
<latexit sha1_base64="Kjn82NshDbErSur1Q2qfY5QZjsY=">AAAB5nicbVDLSgMxFL1TX219Vd0IboJFcFVm6sIui25cVrAPaUvJpGkbmskMyR2x1oJf4EbEjYLf4Ff4C4IfY/rYtPXAhcM555J74kdSGHTdHyexsrq2vpFMpTe3tnd2M3v7FRPGmvEyC2Woaz41XArFyyhQ8lqkOQ18yat+/3LsV++4NiJUNziIeDOgXSU6glG00u3jfUNT1ZW8lcm6OXcCsky8GckWDx9+U09fF6VW5rvRDlkccIVMUmPqnhthc0g1Cib5KN2IDY8o69MuH07OHJETK7VJJ9R2FJKJOpejgTGDwLfJgGLPLHpj8T+vHmOn0BwKFcXIFZs+1IklwZCMO5O20JyhHFhCmRb2QsJ6VFOG9mfStrq3WHSZVPI57yyXv/ayxQJMkYQjOIZT8OAcinAFJSgDgwBe4B0+nJ7z7Lw6b9NowpntHMAcnM8/GAGPag==</latexit>
|x
<latexit sha1_base64="Kjn82NshDbErSur1Q2qfY5QZjsY=">AAAB5nicbVDLSgMxFL1TX219Vd0IboJFcFVm6sIui25cVrAPaUvJpGkbmskMyR2x1oJf4EbEjYLf4Ff4C4IfY/rYtPXAhcM555J74kdSGHTdHyexsrq2vpFMpTe3tnd2M3v7FRPGmvEyC2Woaz41XArFyyhQ8lqkOQ18yat+/3LsV++4NiJUNziIeDOgXSU6glG00u3jfUNT1ZW8lcm6OXcCsky8GckWDx9+U09fF6VW5rvRDlkccIVMUmPqnhthc0g1Cib5KN2IDY8o69MuH07OHJETK7VJJ9R2FJKJOpejgTGDwLfJgGLPLHpj8T+vHmOn0BwKFcXIFZs+1IklwZCMO5O20JyhHFhCmRb2QsJ6VFOG9mfStrq3WHSZVPI57yyXv/ayxQJMkYQjOIZT8OAcinAFJSgDgwBe4B0+nJ7z7Lw6b9NowpntHMAcnM8/GAGPag==</latexit>
U
<latexit sha1_base64="WpbDVNFLu2kgMGufoa4z4RgwjdA=">AAAB3nicbVBNS0JBFL3Pvsy+rJZBDEnQSt7TRe4S2rRU6KmgYvPG+3Rw3gcz8wIRl7WJaFPQT3HVur/Qb+hPNH5s1A5cOJxzLnPPeLHgStv2j5Xa2Nza3knvZvb2Dw6PsscnNRUlkqHLIhHJhkcVCh6iq7kW2Igl0sATWPcGt1O//ohS8Si818MY2wHthdznjGojVd1ONmfn7RnIOnEWJHfzNan+Pp1PKp3sd6sbsSTAUDNBlWo6dqzbIyo1ZwLHmVaiMKZsQHs4mp03JpdG6hI/kmZCTWbqUo4GSg0DzyQDqvtq1ZuK/3nNRPul9oiHcaIxZPOH/EQQHZFpV9LlEpkWQ0Mok9xcSFifSsq0+ZGMqe6sFl0ntULeKeYLVSdXLsEcaTiDC7gCB66hDHdQARcYILzAO3xYD9az9Wq9zaMpa7FzCkuwPv8AQoKMxw==</latexit>
V
<latexit sha1_base64="53u3biTACZG1ED1tQtmUQuW5bV0=">AAAB3nicbVC7SkNBFDzrM8ZX1FKQxSBYhXtjYToDNpYJmAckIe7d7E2W7H2we64QQkptRGwU/JRU1v6C3+BPuHk0SRw4MMzMYc+sFytp0HF+yNr6xubWdmonvbu3f3CYOTqumijRXFR4pCJd95gRSoaighKVqMdasMBToub1byd+7VFoI6PwHgexaAWsG0pfcoZWKlfbmayTc6agq8Sdk+zN17j8+3Q2LrUz381OxJNAhMgVM6bhOjG2hkyj5EqM0s3EiJjxPuuK4fS8Eb2wUof6kbYTIp2qCzkWGDMIPJsMGPbMsjcR//MaCfqF1lCGcYIi5LOH/ERRjOikK+1ILTiqgSWMa2kvpLzHNONofyRtq7vLRVdJNZ9zr3L5spstFmCGFJzCOVyCC9dQhDsoQQU4CHiBd/ggD+SZvJK3WXSNzHdOYAHk8w9D/IzI</latexit>
|
<latexit sha1_base64="yZzoUMAFcvdEmaleQRzLli6veEE=">AAAB6XicbVDLSgMxFL1TX219Vd0IboJFcFVm6sIui25cVnDaQqeUTJppQzOZkGSEWgv+ghsRNwr+gV/hLwh+jOlj09YDFw7nnEvuSSg508Z1f5zM2vrG5lY2l9/e2d3bLxwc1nWSKkJ9kvBENUOsKWeC+oYZTptSURyHnDbCwfXEb9xTpVki7sxQ0naMe4JFjGBjpeAxkH0WKCx6nHYKRbfkToFWiTcnxerxw2/u6euq1il8B92EpDEVhnCsdctzpWmPsDKMcDrOB6mmEpMB7tHR9NIxOrNSF0WJsiMMmqoLORxrPYxDm4yx6etlbyL+57VSE1XaIyZkaqggs4eilCOToElt1GWKEsOHlmCimL0QkT5WmBj7OXlb3Vsuukrq5ZJ3USrfesVqBWbIwgmcwjl4cAlVuIEa+EBAwgu8w4czcJ6dV+dtFs04850jWIDz+QdDWJCt</latexit>
Alice
Bob
A
in
<latexit sha1_base64="Q31/2tHi4snRqoI3kUyheTcJZcg=">AAAAAHicbVDLSgMxFM34rPXRUcGNm2ARXJWZIuiy1o3LFuwD2mHIpJk2NMkMSUaow3yJGxeKuHDjN/gF7tz4LWbaLrT1QOBwzr3k3BPEjCrtOF/Wyura+sZmYau4vbO7V7L3D9oqSiQmLRyxSHYDpAijgrQ01Yx0Y0kQDxjpBOPr3O/cEaloJG71JCYeR0NBQ4qRNpJvl678tM+RHkmeUpFlvl12Ks4UcJm4c1KuHTW/6Vv9o+Hbn/1BhBNOhMYMKdVznVh7KZKaYkayYj9RJEZ4jIakZ6hAnCgvnQbP4KlRBjCMpHlCw6n6eyNFXKkJD8xknlEtern4n9dLdHjpmYPiRBOBZx+FCYM6gnkLcEAlwZpNDEFYUpMV4hGSCGvTVdGU4C6evEza1Yp7Xqk23XKtDmYogGNwAs6ACy5ADdyABmgBDBLwAJ7As3VvPVov1utsdMWa7xyCP7DefwBDQ5cw</latexit>
A
out
<latexit sha1_base64="N7Qkz3aHHdGhuuJGOBeyglQghOk=">AAAAAHicbVDLSgMxFM3UV62vUcGNm2ARXJWZIuiy1o3LFuwD2mHIpJk2NJkMSaZQhvkTNy4UEVz5C36BOzd+i5m2C209EDiccy/35AQxo0o7zpdVWFvf2Nwqbpd2dvf2D+zDo7YSicSkhQUTshsgRRiNSEtTzUg3lgTxgJFOML7N/c6ESEVFdK+nMfE4GkY0pBhpI/m2feOnfY70SPJUJDrLfLvsVJwZ4CpxF6RcO2l+07f6R8O3P/sDgRNOIo0ZUqrnOrH2UiQ1xYxkpX6iSIzwGA1Jz9AIcaK8dJY8g+dGGcBQSPMiDWfq740UcaWmPDCTeUi17OXif14v0eG1l9IoTjSJ8PxQmDCoBcxrgAMqCdZsagjCkpqsEI+QRFibskqmBHf5y6ukXa24l5Vq0y3X6mCOIjgFZ+ACuOAK1MAdaIAWwGACHsATeLZS69F6sV7nowVrsXMM/sB6/wEyXJe7</latexit>
M
<latexit sha1_base64="QRa0BeN8pMF5pYUkDA8FwbemFgI=">AAAAAHicbVDLSgNBEOyNrxhfUY9eBoPgKeyGgB6DXrwICZgHJEuYnfQmY2Znl5lZIYR8gRcPinj1k7z5N06SPWhiQUNR1U13V5AIro3rfju5jc2t7Z38bmFv/+DwqHh80tJxqhg2WSxi1QmoRsElNg03AjuJQhoFAtvB+Hbut59QaR7LBzNJ0I/oUPKQM2qs1LjvF0tu2V2ArBMvIyXIUO8Xv3qDmKURSsME1brruYnxp1QZzgTOCr1UY0LZmA6xa6mkEWp/ujh0Ri6sMiBhrGxJQxbq74kpjbSeRIHtjKgZ6VVvLv7ndVMTXvtTLpPUoGTLRWEqiInJ/Gsy4AqZERNLKFPc3krYiCrKjM2mYEPwVl9eJ61K2auWK41qqXaTxZGHMziHS/DgCmpwB3VoAgOEZ3iFN+fReXHenY9la87JZk7hD5zPH6avjNY=</latexit>
E
A
<latexit sha1_base64="dRboNTlmw86S8PRMM9oopeBs1wg=">AAAAAHicbVDLSgMxFL1TX7W+qoIbN4NFcFVmiqDLWhFctmAf0I4lk2ba0CQzJBmlDP0PNy4UcSf+hF/gzo3fYqbtQlsPBA7n3Ms9OX7EqNKO82VllpZXVtey67mNza3tnfzuXkOFscSkjkMWypaPFGFUkLqmmpFWJAniPiNNf3iZ+s07IhUNxY0eRcTjqC9oQDHSRrq96iYdjvRA8uRiPO7mC07RmcBeJO6MFMoHtW/6VvmodvOfnV6IY06Exgwp1XadSHsJkppiRsa5TqxIhPAQ9UnbUIE4UV4yST22j43Ss4NQmie0PVF/bySIKzXivplMI6p5LxX/89qxDs69hIoo1kTg6aEgZrYO7bQCu0clwZqNDEFYUpPVxgMkEdamqJwpwZ3/8iJplIruabFUcwvlCkyRhUM4ghNw4QzKcA1VqAMGCQ/wBM/WvfVovViv09GMNdvZhz+w3n8Aw06WYw==</latexit>
E
B
<latexit sha1_base64="Cpyqr1s2i2MeGJQ4QGs8m7cn1e8=">AAAAAHicbVDLSgMxFL3js9ZX1aWbYBFclZlS0GWpCC4r2Ae0Y8mkmTY0yQxJRinD/IcbF4q49V/c+Tem7Sy09UDgcM693JMTxJxp47rfztr6xubWdmGnuLu3f3BYOjpu6yhRhLZIxCPVDbCmnEnaMsxw2o0VxSLgtBNMrmd+55EqzSJ5b6Yx9QUeSRYygo2VHm4GaV9gM1YibWTZoFR2K+4caJV4OSlDjuag9NUfRiQRVBrCsdY9z42Nn2JlGOE0K/YTTWNMJnhEe5ZKLKj203nqDJ1bZYjCSNknDZqrvzdSLLSeisBOziLqZW8m/uf1EhNe+SmTcWKoJItDYcKRidCsAjRkihLDp5ZgopjNisgYK0yMLapoS/CWv7xK2tWKV6tU72rleiOvowCncAYX4MEl1OEWmtACAgqe4RXenCfnxXl3Phaja06+cwJ/4Hz+AOXcksY=</latexit>
B
out
<latexit sha1_base64="jtZk7+SeBS1CR32lQkpPF26xkkA=">AAAAAHicbVDLSsNAFJ3UV62vqEs3g0VwVZJS0GWpG5cVbCu0IUymk3boPMLMpFBC/sSNC0Xc+ifu/BsnbRbaemDgcM693DMnShjVxvO+ncrW9s7uXnW/dnB4dHzinp71tUwVJj0smVRPEdKEUUF6hhpGnhJFEI8YGUSzu8IfzInSVIpHs0hIwNFE0JhiZKwUum4nzEYcmanimUxNnodu3Wt4S8BN4pekDkp0Q/drNJY45UQYzJDWQ99LTJAhZShmJK+NUk0ShGdoQoaWCsSJDrJl8hxeWWUMY6nsEwYu1d8bGeJaL3hkJ4uQet0rxP+8YWri2yCjIkkNEXh1KE4ZNBIWNcAxVQQbtrAEYUVtVoinSCFsbFk1W4K//uVN0m82/Faj+dCqtztlHVVwAS7BNfDBDWiDe9AFPYDBHDyDV/DmZM6L8+58rEYrTrlzDv7A+fwBVPeUHg==</latexit>
A
1
<latexit sha1_base64="oXBl/cNtkQP47D0Zv2NLv7a0V8o=">AAAAAHicbVBNS8NAEJ3Ur1q/qh69LBbBU0lKwR4rXjxWtLXQhrLZTtqlm03Y3Qgl9Cd48aCIV3+RN/+N2zYHbX0w8Hhvhpl5QSK4Nq777RQ2Nre2d4q7pb39g8Oj8vFJR8epYthmsYhVN6AaBZfYNtwI7CYKaRQIfAwmN3P/8QmV5rF8MNME/YiOJA85o8ZK99cDb1CuuFV3AbJOvJxUIEdrUP7qD2OWRigNE1Trnucmxs+oMpwJnJX6qcaEsgkdYc9SSSPUfrY4dUYurDIkYaxsSUMW6u+JjEZaT6PAdkbUjPWqNxf/83qpCRt+xmWSGpRsuShMBTExmf9NhlwhM2JqCWWK21sJG1NFmbHplGwI3urL66RTq3r1au2uXmk28jiKcAbncAkeXEETbqEFbWAwgmd4hTdHOC/Ou/OxbC04+cwp/IHz+QO2d41k</latexit>
B
1
<latexit sha1_base64="j/RHpYpwpOcqB4i4pSCy0Pc+Ah8=">AAAAAHicbZDLSgMxFIbPeK2j1apLN8FScFUmRbDLoiAuK9oLtEPJpJk2NJMZkoxQhj6CGxeKuBUfxEdw59uYXhba+kPg4//PIeecIBFcG8/7dtbWNza3tnM77u5efv+gcHjU1HGqKGvQWMSqHRDNBJesYbgRrJ0oRqJAsFYwuprmrQemNI/lvRknzI/IQPKQU2KsdXfZw71C0St7M6FVwAso1vKfaena/aj3Cl/dfkzTiElDBdG6g73E+BlRhlPBJm431SwhdEQGrGNRkohpP5uNOkEl6/RRGCv7pEEz93dHRiKtx1FgKyNihno5m5r/ZZ3UhFU/4zJJDZN0/lGYCmRiNN0b9bli1IixBUIVt7MiOiSKUGOv49oj4OWVV6FZKePzcuUWF2tVmCsHJ3AKZ4DhAmpwA3VoAIUBPMIzvDjCeXJenbd56Zqz6DmGP3LefwA9xZAB</latexit>
Figure 1: A one-message protocol for compression of quantum states, with shared entanglement. The
register A
in
holds the input given to Alice, and E
A
contains Alice’s workspace and her part of the
initial shared state (the shared entanglement). The register E
B
contains Bob’s workspace and his part
of the initial shared state. The compression is implemented by the isometry U, and the register M
contains the compressed state and is sent as the message. The decompression is implemented by the
isometry V . Bob’s output is contained in the register B
out
.
Compression problems similar to the one above have been studied extensively in quantum
information theory, both in the one-shot setting (the one we described above), and in the
asymptotic setting (where the sender’s input consists of multiple samples picked indepen-
dently from the same distribution). The problem has been studied in early works such
as Ref. [5] in the setting of quantum communication without shared entanglement. It is
known as remote state preparation when allowed one-way communication over a classical
channel with shared entanglement. We refer the reader to Ref. [4, Table I] for a summary
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 2
of the work on remote state preparation; we describe the most relevant results—in the
one-shot setting—below.
Other tasks in the literature that come close to the one above are state splitting (see, e.g.,
Ref. [7]), and that of channel simulation in the context of the Quantum Reverse Shannon
Theorem [6, 7]. State splitting is the time reversal [9] of state merging [15, 16], and was
called the “fully quantum reverse Shannon protocol” in Ref. [9]. We explain the connection
to state splitting in detail in Section 2.3.
In both state splitting and channel simulation, the protocol is required to be “coherent” in
specific ways. In particular, in compressing an ensemble of states as in Eq. (1.1), at the
end of the protocol, Bob would be required to hold an approximation to the state ρ
x
and
Alice a purification of this state. In contrast to these tasks, we do not require that the
compression protocol maintain such coherence. More precisely, the registers containing
a purification of the output state may be shared by Alice and Bob. Such compression
protocols are more relevant in the context of two-party communication protocols studied
in complexity theory, especially in the context of direct sum and direct product results (see
e.g., Refs. [17, 19, 28] and the references therein). In communication complexity, a typical
goal is to compute a bivariate Boolean function when the inputs are distributed between
two parties. The parties communicate with each other, alternating messages with local
computation, and at the end, one party produces the output of the protocol from the part
of the final state in her possession. As a result, the output of the protocol does not depend
on the part of the state held by the other party (i.e., on the purification of her part of the
final joint state). A compression scheme for the final state then need only focus on the
part being measured for the output.
1.2 Entanglement cost of compression
Jain, Radhakrishnan, and Sen [18, 19] gave a one-shot protocol for compressing an en-
semble of states as in Eq. (1.1), and bounded its communication cost by O(I(A : B)
τ
/
3
),
where I(A : B)
τ
is the mutual information between registers A and B in the state τ
AB
:
=
1
n
P
x∈[n]
|xihx|
A
⊗ ρ
B
x
, and is the average approximation error (cf. Section 2.3 for a pre-
cise definition of average error). Using a more refined application of their technique, Bab
Hadiashar, Nayak, and Renner [4] tightly characterized the communication cost of the
task in terms of the smooth max-information, a one-shot entropic analogue of mutual in-
formation. Their results are stated for entanglement-assisted classical channels and use
purified distance to quantify the approximation, but translate immediately to the setting
here through the use of superdense coding [29, Section 6.3.1] and the Fuchs and van de
Graaf Inequalities (Proposition 2.4). The upper bound so obtained is
1
2
I
/
√
2
max
(A : B)
τ
+ O(log log(1/)) .
This is slightly better than that derived from protocols for state splitting in terms of the
approximation error; it has an additive term of O(log log
1
) for average error versus the
additive term of O(log
1
) in Ref. [1, Corollary 5]. However, both these protocols use shared
entanglement that may be much longer than the message itself, namely O(k(log
1
) log m)
qubits and O((1+ 1/
2
) log
2
(m/)) qubits, respectively, where log
2
k = I(A : B)
τ
, and m is
the dimension of the states in the ensemble. On the other hand, earlier protocols for state
splitting [7, Lemma 3.5], with potentially larger communication cost, have entanglement
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 3
cost bounded by log m. Since sharing entanglement also entails some communication, in
addition to the preparation and storage of a potentially delicate high dimensional state,
this motivates the question as to whether shared entanglement is truly necessary for com-
pression, and if so, how much of it is needed.
For the more restrictive task of state splitting, it follows from the proof of the converse
bound for one-shot entanglement consumption due to Berta, Christandl, and Touchette [8,
Proposition 10] that the sum of the communication and entanglement costs is at least the
min-entropy S
min
(ρ) of the ensemble average state ρ
:
=
P
x
p
x
ρ
x
. (Although the proof
is written assuming that the shared state consists of EPR pairs and some ancilla and an
auxiliary error parameter, it may be modified to give a bound when an arbitrary state is
shared and the auxiliary error is 0.) In this article, we show that there are ensembles for
which the min-entropy bound equals the number of qubits in the states, and the bound
holds up to an additive constant even with the more general compression protocols we
allow.
Theorem 1.1. There exist universal constants c
1
, c
2
> 0 such that for any ∈ (0, 1), and
any k, m ∈ N with k ≥ 6/(1 − ) and m ≥ c
1
(ln k)/(1 − )
2
such that k divides m, there
exists an ensemble
1
n
, ρ
x
: x ∈ [n], ρ
x
∈ D(C
m
)
, where n depends on k, m, and , such
that
(i) I(A : B)
τ
= I
max
(A : B)
τ
= log
2
k, where τ
:
=
1
n
P
x∈[n]
|xihx|
A
⊗ ρ
B
x
;
(ii) there is a one-way protocol with shared entanglement for the visible compression of
the ensemble with average error /2 and with communication cost
1
2
log k+O(log log
1
);
and
(iii) the sum of communication and entanglement costs of any one-way protocol with
shared entanglement for visible compression of the ensemble, with average-error at
most /2, is at least
log m − 3 log
1
1 −
− c
2
.
In particular, the theorem implies that in the absence of shared entanglement, the ensemble
may only be compressed by a constant number of qubits (independent of m), even if
constant average error
2
< 1/2 is allowed. Note also that the straightforward protocol that
prepares and sends the state ρ
x
on input x has sum of entanglement and communication
costs equal to log m. So the lower bound in the theorem is optimal up to an additive
universal constant term for constant ∈ (0, 1).
Proposition 3.4 and Corollary 3.5 in Section 3 contain more precise statements of the
results stated in the theorem. As we explain in that section, I(A : B)
τ
may be interpreted
as the “information content” of the ensemble; it is the quantum information cost [28] of
the protocol in which Alice simply prepares the state ρ
x
on input x and sends the state to
Bob.
The compression task we study is a relaxation of oblivious (or blind) compression, in which
the input to Alice is the state ρ
x
, rather than x. It is also a relaxation of state-splitting
(more generally, of state re-distribution [10, 23, 30]), and channel simulation. So the lower
bound in Theorem 1.1(ii) holds for these tasks as well.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 4
The ensemble mentioned in Theorem 1.1 is obtained via the probabilistic method, and is of
a form devised by Jain, Radhakrishnan, and Sen [17]. They showed the incompressibility
of such an ensemble when the decompression operation is unitary (i.e., via protocols as in
Figure 1 in which the register B
1
is trivial). We adapt their proof method to protocols which
allow a general quantum channel for decompression. A key step here is a technical lemma
(Lemma 3.2 in Section 3) which allows us to reason about general quantum channels, and
also yields a tighter lower bound on the sum of communication and entanglement costs.
1.3 Implications and related work
Jain et al. [18, 19], also used the same kind of ensemble as in Theorem 1.1 to design
a two-party one-way communication protocol with shared entanglement for the Equality
function. They showed that the initial shared state in the protocol cannot be replaced
by one with polynomially smaller dimension in a “black-box fashion” (i.e., when the local
operations of the two parties are not modified). Theorem 1.1 implies a similar impossibility
result for protocols in which the sender and receiver can deviate from the original protocol
arbitrarily, but they try to approximate the receiver’s state in the original protocol after
the message is sent. The impossibility holds even when the dimension of the initial shared
entangled state is reduced only by a constant factor.
A remarkable property of the ensemble posited by Theorem 1.1 is that the communication
cost of compression (with shared entanglement) may be arbitrarily smaller than the en-
tanglement cost. For constant error the communication cost is within an additive constant
of the quantum information cost [28] of the protocol that simply prepares and sends the
state. As a consequence, we infer that the quantum information cost of a protocol may
be arbitrarily smaller than the communication cost of any protocol without shared entan-
glement for compressing its messages. Anshu, Touchette, Yao, and Yu [3] had previously
proven a similar separation when the compression protocol is allowed to use shared entan-
glement. However, their separation is exponential: they exhibited an interactive protocol
for a Boolean function with quantum information cost that is exponentially smaller than
the communication cost of any interactive quantum protocol that computes the function.
(Observe that a protocol for compressing the final state of the original protocol may also
be used to compute the function.) In contrast to that protocol, the one we present is
compressible to its quantum information cost, but requires an arbitrarily larger amount of
shared entanglement to do so.
In another related work, Liu, Perry, Zhu, Koh, and Aaronson [22] show that one-way
protocols cannot be compressed to their quantum information cost without using shared
entanglement. They consider a certain one-way protocol in which Alice gets an n-bit
input, Bob gets an m-bit input, with m ∈ o(n). The protocol has quantum informa-
tion cost O(nm
−2
log m). They show that the protocol cannot be compressed by a one-
way protocol without shared entanglement into a message of length o(log n) with error at
most (n + 1)
−m
. Thus the separation is limited, and only holds for exponentially small
error (in the length of the inputs).
It is believed that the communication in any interactive quantum protocol which has a
constant number of rounds and computes a function of classical inputs may be compressed,
with constant error, to an amount proportional to the quantum information cost of the
protocol. For one-way protocols such a result was shown by Jain, Radhakrishnan, and
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 5
Sen [18, 19]. This was later re-proven by Anshu, Jain, Mukhopadhyay, Shayeghi, and
Yao [2] using different techniques. A similar result for protocols with a larger constant
number of rounds of communication was claimed by Touchette [28], but the proof has
an error. The compression protocols achieving quantum information cost all rely on the
presence of shared entanglement. Theorem 1.1 shows that even for the simplest protocols,
such compression is not possible in the absence of shared entanglement. Moreover, it shows
that the entanglement cost may be necessarily within an additive constant of the length
of the message to be compressed, even when the quantum information cost is arbitrarily
smaller than the message length.
In a recent independent work, Khanian and Winter [20] analyse the communication and
entanglement costs of a variant of compression in the asymptotic setting. They study pure
state ensembles with quantum side information in the form of pure states. In the case of vis-
ible compression with shared entanglement, they show that the asymptotic (per-instance)
communication cost is at least
1
2
S(ρ), i.e., half the entropy of the ensemble average state ρ.
So this cost may be at most a factor of 1/2 smaller than that of compression without shared
entanglement. Moreover, the asymptotic sum of communication and entanglement costs
is at least the entropy S(ρ). Thus the kind of separation we show does not hold for pure
states even in the asymptotic setting.
Organization. The rest of this article is organized as follows. In Section 2, we review
basic concepts and notation from quantum information and communication. In section 3,
we prove the main result and discuss its implications.
Acknowledgements. We thank Milán Mosonyi for extensive, thoughtful feedback on
earlier versions of this article. This research is supported in part by NSERC Canada. SBH
is also supported by an Ontario Graduate Scholarship.
2 Preliminaries
2.1 Mathematical notation and background
We refer the reader to the book Watrous [29] for a thorough introduction to basics of
quantum information. We briefly review the notation and some results that we use in the
article.
For the sake of brevity, we denote the set {1, 2, . . . , k} by [k]. We denote physical quantum
systems (“registers”) with capital letters, like X, Y and Z. The state space corresponding
to a register is a finite-dimensional Hilbert space. We denote (finite dimensional) Hilbert
spaces either by capital script letters like H and K, or as C
m
where m is the dimension. We
denote the the dimension of a Hilbert space corresponding to a register X as |X|. We use
the Dirac notation, i.e., “ket” and “bra”, for unit vectors and their adjoints, respectively.
We denote the set of all unit vectors in a Hilbert space H by Sphere(H). For a Hilbert
space H
:
= C
S
for some non-empty finite set S, we call {|xi : x ∈ S} its canonical basis.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 6
A subset N of Sphere(H) is called -dense if for every vector |ui ∈ Sphere(H), there exists
a vector in the set N at Euclidean distance at most from |vi. Such a set is also called
an “-net” in the literature. The following proposition states that every finite dimensional
Hilbert space has a relatively small -dense set.
Proposition 2.1 ([24], Lemma 13.1.1, Chapter 13). Let ∈ (0, 1], and m be a positive
integer. The Hilbert space C
m
has an -dense set N of size |N| ≤
4
2m
.
A slightly better bound
1 +
2
2m
on the size of an -dense set is given in Ref. [26, Lemma
2.6].
We denote the set of all linear operators on Hilbert space H by L(H), the set of all positive
semi-definite operators by Pos(H), the set of all unitary operators by U(H), and the set of
all quantum states (or “density operators”) over H by D(H). The identity operator on H is
denoted by 1
H
. We denote quantum states or sub-normalized states (positive semi-definite
operators with trace at most 1) by lowercase Greek letters like ρ, σ. We use notation such
as ρ
X
to indicate that register X is in state ρ, and may omit the superscript when the
register is clear from the context. An operator M ∈ Pos(H) is called a measurement
operator if M ≤ 1. We usually denote quantum channels, i.e., completely positive trace-
preserving linear maps from the space of linear operators on a Hilbert space to another
such space, by capital Greek letters like Ψ. The partial trace over a Hilbert space K is
denoted as Tr
K
.
We denote the operator norm (Schatten ∞ norm) of an operator M ∈ L(H) by kMk,
the Frobenius norm (Schatten 2 norm) by kMk
F
, and the trace norm (Schatten 1 norm)
by kMk
tr
. Recall that kMk
tr
:
= Tr
√
M
∗
M is the sum of the singular values of M , kMk
is the largest singular value, and kMk
F
:
=
p
Tr(M
∗
M) is the `
2
-norm of the singular
values with multiplicity. All of these norms are invariant under composition with a unitary
operator.
We consider random unitary operators chosen according to the Haar measure η on U(H),
where H is a finite dimensional Hilbert space. The Haar measure is the unique unitarily
invariant probability measure over U(H).
Let f : U(H) → R be a continuous function. Suppose f is κ-Lipschitz, i.e., for all U, V ∈
U(H), we have
|f(U) − f (V )| ≤ κ kU − V k
F
,
for some κ ≥ 0. If κ is small enough as compared to the dimension of H, with high
probability, the random variable f(U ) is close to its expectation, where U ∈ U(H) is a
Haar-random unitary operator. This concentration of measure property is formalized by
the following theorem, which is a special case of Theorem 5.17 in Ref. [25].
Theorem 2.2 ([25], Theorem 5.17, page 159). Let η be the Haar measure on U(H),
where H is a Hilbert space with finite dimension m, and let U ∈ U(H) be a random unitary
operator chosen according to η. For every function f : U(H) → R that is κ-Lipschitz with
respect to the Frobenius norm (with κ > 0), and every positive real number t, we have
η
{U ∈ U(H) : f(U) − E [f(U )] ≥ t}
≤ exp
−
(m − 2)t
2
24κ
2
!
.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 7
The fidelity between two sub-normalized states ρ and σ is defined as
F(ρ, σ)
:
= Tr
q
√
ρ σ
√
ρ +
q
(1 − Tr(ρ))(1 − Tr(σ)) .
Fidelity can be used to define a useful metric called the purified distance [12, 27] between
sub-normalized states:
P(ρ, σ)
:
=
q
1 − F(ρ, σ)
2
.
For a quantum state ρ ∈ D(H) and ∈ [0, 1], we define
B
(ρ)
:
= {
e
ρ ∈ Pos (H) : P(ρ,
e
ρ) ≤ , Tr
e
ρ ≤ 1}
as the ball of sub-normalized states that are within purified distance of ρ.
The trace distance between quantum states is induced by the trace norm. The following
property is well known (see, e.g., Ref. [29, Theorem 3.4, page 128]).
Proposition 2.3 (Holevo-Helstrom Theorem [13, 14]). For any pair of quantum states ρ, σ ∈
D(H),
kρ − σk
tr
= 2 max { |Tr(Mρ) − Tr(Mσ)| : M is a measurement operator on H} .
Purified distance and trace distance are related to each other as follows (see, e.g., Ref. [29,
Theorem 3.33, page 161]):
Proposition 2.4 (Fuchs and van de Graaf Inequalities [11]). For any pair of quantum
states ρ, σ ∈ D(H),
1 −
q
1 − P(ρ, σ)
2
≤
1
2
kρ − σk
tr
≤ P(ρ, σ) .
Unless specified, we take the base of the logarithm function to be 2.
Let H, K, and M be the state spaces corresponding to registers X, Y , and M, respectively.
For a register X in quantum state ρ ∈ D(H), the von Neumann entropy of X is defined as
S(ρ)
:
= −Tr (ρ log ρ) .
This coincides with the Shannon entropy of the spectrum of ρ. The relative entropy of two
quantum states ρ, σ ∈ D(H) is defined as
S(ρkσ)
:
= Tr (ρ log ρ − ρ log σ) ,
when supp(ρ) ⊆ supp(σ), and is ∞ otherwise. The max-relative entropy of ρ with respect
to σ is defined as
S
max
(ρkσ)
:
= min{λ : ρ ≤ 2
λ
σ} ,
when supp(ρ) ⊆ supp(σ), and is ∞ otherwise. The min-entropy of ρ is defined as
S
min
(ρ)
:
= −log kρk .
Suppose that the registers X, Y are in joint state ρ
XY
∈ D(H⊗K). The mutual information
of X and Y is defined as
I(X : Y )
ρ
:
= S
ρ
XY
kρ
X
⊗ ρ
Y
.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 8
When the state is clear from the context, the subscript ρ may be omitted from the nota-
tion. When ρ is a classical-quantum state, i.e., ρ
XY
=
P
x
p
x
|xihx|
X
⊗ ρ
Y
x
with p being a
probability distribution, {|xi} the canonical orthonormal basis for H, and ρ
x
∈ D(K), we
have
I(X : Y ) =
X
x
p
x
S(ρ
x
kρ) ,
where ρ =
P
x
p
x
ρ
x
. Suppose the registers X, Y, M are in joint (tripartite) state ρ
XYM
∈
D(H ⊗ K ⊗ M). The conditional mutual information of X and M given Y is defined as
I(X : M |Y )
:
= I(XY : M ) − I(Y : M) .
When ρ
XYM
is a tensor product of the states ρ
XM
and ρ
Y
, we have
I(X : M |Y ) = I(XY : M ) = I(X : M ) .
For any state ρ
XY
∈ D(H ⊗ K), the max-information register Y has about register X [7]
is defined as
I
max
(X : Y )
ρ
:
= min
σ∈D(K)
S
max
ρ
XY
kρ
X
⊗ σ
Y
.
For a parameter ∈ [0, 1], the smooth max-information register Y has about register X is
defined as
I
max
(X : Y )
ρ
:
= min
eρ∈B
(ρ)
I
max
(X : Y )
eρ
.
2.2 Quantum communication protocols
We first describe a two-party quantum communication protocol informally and then give a
formal definition for the special case of interest to us. We refer the reader to, e.g., Ref. [28]
for a formal definition of the general case.
In a two-party quantum communication protocol, there are two parties, Alice and Bob,
each of whom may get some input in registers designated for this purpose. Alice and Bob’s
inputs may be entangled with each other, and also with a “reference” system, which purifies
it. Alice and Bob’s goal is to accomplish an information processing task by communicating
with each other.
Each party possesses some “work” (or “private”) qubits (or registers) in addition to the
input registers. The work qubits are initialized to a fixed pure state in tensor product with
the input state. This fixed state may be entangled across the work registers of Alice and
Bob, and may be used as a computational resource. In this case, we say the protocol or
the channel is with shared entanglement or with entanglement assistance. If the fixed state
is a tensor product state across Alice and Bob’s registers, we say it is a protocol or channel
without shared entanglement or simply unassisted.
The protocol proceeds in some number of “rounds”. In each round, the sender applies an
isometry to the qubits in her possession, and sends a sub-register (the message) to the
other party. The length of the message (in qubits) is the base 2 logarithm of the dimension
of the message register. After the last round, the recipient of the last message applies an
isometry to his registers. The output of the protocol is the state of a pair of designated
registers of the two parties at the end.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 9
We are often interested in minimizing the total length of the messages over all the rounds,
i.e., the communication cost (or complexity) of the protocol. The idea is to accomplish
the task at hand with minimum communication. In protocols with shared entanglement,
we are also interested in the amount of shared entanglement needed in the protocol, i.e.,
the minimum dimension of the support of the initial state of either party’s work space.
This latter quantity, measured in number of qubits, is called the entanglement cost of the
protocol.
In this article, we study only one-way protocols, i.e., protocols with one round, and there-
fore one message, (say) from Alice to Bob. We describe these more formally here. Alice
and Bob initially hold registers A
in
E
A
and B
in
E
B
, respectively. The input registers A
in
B
in
are initialized to some state ρ
A
in
B
in
whose purification is held in register R with a third
party, the referee. Alice and Bob’s work registers E
A
and E
B
are initialized to a pure
state |φi
E
A
E
B
, which may be entangled across the partition E
A
E
B
. The local opera-
tions in the protocol are specified by two isometries U and V . The isometry U acts on
registers A
in
E
A
and maps them to registers A
out
A
1
M. The isometry V acts on regis-
ters B
in
E
B
M and maps them to registers B
1
B
out
. First, Alice applies U to the regis-
ters A
in
and E
A
and sends the register M to Bob. Then, Bob applies V on his initial
registers B
in
E
B
and the message M. The output of the protocol is the state of Alice
and Bob’s registers A
out
B
out
. The communication cost of this protocol is log |M| and the
entanglement cost is the logarithm of the Schmidt rank of the state |φi across the parti-
tion E
A
E
B
. We say it is a protocol with shared entanglement if the Schmidt rank of |φi is
more than 1, and say that it is without shared entanglement otherwise. Such protocols are
also called entanglement-assisted and unassisted, respectively, in the literature.
We say that the input is “classical” when there are non-empty finite sets S
A
, S
B
(the
sets of classical inputs) such that the Hilbert spaces corresponding to the input registers
are C
S
A
, C
S
B
, respectively, and the initial joint quantum state in the input registers A
in
B
in
is diagonal in the canonical basis {|xi|yi : x ∈ S
A
, y ∈ S
B
}. In the case that the inputs to
Alice and Bob are classical, we assume without loss of generality that the input registers A
in
and B
in
are “read-only”, i.e., the isometries U and V are of the form
P
x∈S
A
|xihx|
A
in
⊗U
E
A
x
and
P
y∈S
B
|yihy|
B
in
⊗V
ME
B
y
, where S
A
, S
B
are sets as above. A one-way protocol in which
Alice gets a classical input and Bob does not have any input is depicted in Figure 1.
Let Π be a one-way quantum protocol (with or without shared entanglement) with a
single message from Alice to Bob, in which Alice gets a classical input and Bob does not
have any input. The register R with the referee purifies Alice’s input so that |ρi
RA
in
:
=
P
x∈S
A
√
p
x
|xxi
RA
in
, where p
x
is a probability distribution over the input set S
A
. Let M
be the quantum register corresponding to the message in Π. The quantum information
cost (or quantum information complexity) of the protocol Π is defined as
QIC(Π)
:
=
1
2
I(R : M |E
B
) ,
where the registers are in the state immediately after Alice sends the message register M
to Bob. This expression simplifies to I(R : ME
B
) as the registers R, E
B
are in a tensor
product state at this point. It is intended to measure the information Bob gains about
Alice’s input from the message. This notion requires a nuanced definition for protocols
with more general inputs and with multiple rounds of communication. As it is not central
to our work, we refer the reader to Ref. [28] for the definition for general protocols.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 10
2.3 Compression of quantum states
We study one-way protocols for non-oblivious or visible compression of quantum states,
which is typical for tasks of this nature (see, e.g., Ref. [1]). The protocol may be with
or without shared entanglement. Suppose we wish to compress states chosen from an
ensemble ((p
x
, ρ
x
) : x ∈ S) for some finite set S, where p is a probability distribution
over S and ρ
x
∈ D(H). The ensemble is known to both parties. The sender, say Alice, is
given a classical input x ∈ S chosen according to the distribution p. Alice and Bob execute
a one-way protocol with a message from Alice to Bob in order to prepare an approximation
of ρ
x
on Bob’s side. Following the notation from Section 2.2, we interpret the state of the
message register M of this protocol as a compression of ρ
x
. Suppose the state of the output
register B
out
is
e
ρ
x
. We say that the average error of the compression protocol is ∈ [0, 2]
if the output state
e
ρ
x
is -close in trace distance to the ideal state ρ
x
on average over the
inputs x:
X
x
p
x
kρ
x
−
e
ρ
x
k
tr
≤ .
It is sometimes desirable to express the error in terms of the purified distance. For simplic-
ity, we state error bounds in terms of trace distance; we may express the bounds in terms
of purified distance via Proposition 2.4.
Note that a protocol for visible compression without shared entanglement may be charac-
terized by a sequence of quantum states (σ
x
: x ∈ S) and a quantum channel Ψ. We let σ
x
be the state of the message register M sent by Alice to Bob on input x. We define Ψ as the
channel resulting from the application of the isometry V followed by the tracing out of the
register B
1
. The average error of the protocol is then
P
x
p
x
kρ
x
− Ψ(σ
x
)k
tr
. Conversely,
any choice of states (σ
x
: x ∈ S, σ
x
∈ D(K)) and quantum channel Ψ : L(K) → L(H) for
some Hilbert space K defines a valid visible compression protocol.
An essentially equivalent formulation of the task of visible compression is the following
(with the notation from Section 2.2). Consider the state τ over the registers RXA
1
C:
τ
:
=
X
x∈S
√
p
x
|xi
R
|xi
X
|φ
x
i
A
1
C
,
where |φ
x
i
A
1
C
is a purification of ρ
x
, register R is held by the referee, and registers XA
1
C
together constitute Alice’s input register A
in
. Alice and Bob both know the full description
of τ. Their goal is to run a one-way quantum communication protocol with a message from
Alice to Bob, with or without shared entanglement, such that at the end, the state
e
τ of
registers RB
out
is close to τ
RC
:
e
τ
RB
out
− τ
RC
tr
≤ .
The difference from state-splitting is that for a fixed state |xi of register R, the purification
of the state in register B
out
may be shared arbitrarily between Alice and Bob (while in
state splitting, it is required to be held by Alice, in register A
1
). A protocol for state-
splitting can thus be used for this task, and conversely lower bounds on communication or
entanglement costs derived for the above task applies to state-splitting as well.
3 The main result
In this section, we prove the main result of this article.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 11
3.1 Two useful lemmas
We begin with two lemmas that we need for the result. The first allows us to focus
on a finite number of subspaces of a finite dimensional Hilbert space, in the context of
measurements. For an operator M ∈ L(H), and a subspace A of H, define the semi-norm
kMk
A
:
= max
|wi ∈ Sphere(A)
|hw|M|wi| .
Lemma 3.1 ([17], Lemma 6). Let d and q be positive integers with q ≥ d, δ > 0 be a real
number, and H be an q-dimensional Hilbert space. There exists a set T of subspaces of H
of dimension at most d such that
1. |T| ≤
8
√
d
δ
2qd
, and
2. for every d-dimensional subspace A ⊆ H, there is a subspace B ∈ T such that for
every measurement operator M ∈ Pos(H),
kMk
A
− kMk
B
≤ δ .
The set T in the lemma is obtained as follows. We fix an -dense subset S of Sphere(H) for
a suitably small value of , as given by Proposition 2.1. For any d-dimensional subspace A,
we consider an orthonormal basis, and the d vectors in S closest to the respective elements
in the basis. We include in T the subspace B spanned by the d vectors from S so obtained.
By a uniformly random subspace of dimension ` of an m-dimensional Hilbert space H,
with ` ≤ m, we mean the image of a fixed `-dimensional subspace under a Haar-random
unitary operator on H. The next lemma is similar to Lemma 7 from Ref. [17], and is
stronger in several respects. It enables the generalization of the incompressibility result in
Ref. [17] that we prove, and helps us derive tighter bounds for compression. Informally,
the lemma states that every state in a “small enough” subspace of a bi-partite space has,
with high probability, a small projection onto a “small enough” random subspace of one
part.
Lemma 3.2. Let m, d, `, and p be positive integers such that ` ≤ m. Let W be a
fixed d-dimensional subspace of C
m
⊗ C
p
. Let Z be a uniformly random subspace of C
m
of dimension `, and M be the orthogonal projection operator onto Z . Then for any real
number α > 2, there is a real number α
1
> 0 that depends only on α such that
Pr
kM ⊗ 1
C
p
k
W
≥
α`
m
≤ exp
−
α
1
`
2
(m − 2)
m
2
!
,
provided
(α − 2)
2
`
2
(m − 2) ≥ (4 × 384)dm
2
ln
8m
α`
.
We may take α
1
:
=
(α−2)
2
768
in the above statement.
Proof: The subspace W is isomorphic to C
d
as it is d-dimensional. By Proposition 2.1,
there is a set N with |N| ≤
8m
α`
2d
that is a
α`
2m
-dense set of Sphere(W).
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 12
Note that for any two vectors |ui, |vi ∈ Sphere(C
m
⊗ C
p
), we have
|hu|(M ⊗ 1)|ui − hv|(M ⊗ 1)|vi| = |Tr (M |uihu| − M |vihv|)|
≤
1
2
k|uihu| − |vihv|k
tr
(by Proposition 2.3)
≤
1
2
k(|ui − |vi)hv|k
tr
+
1
2
k|ui(hu| − hv|)k
tr
= k|uikk|ui − |vik = k|ui − |vik .
This implies that if kM ⊗ 1
C
p
k
W
≥
α`
m
, there is a vector |vi ∈ N such that hv|(M ⊗1)|vi ≥
α`
2m
. By the Union Bound, we get
Pr
kM ⊗ 1
C
p
k
W
≥
α`
m
≤ |N| × max
|vi∈N
Pr
hv|(M ⊗ 1)|vi ≥
α`
2m
. (3.1)
Consider any fixed vector |vi ∈ N and let P ∈ Pos(C
m
) be a fixed orthogonal projection
of rank `. Consider the function f : U(C
m
) → R defined as
f(U)
:
= hv|(UP U
∗
⊗ 1
C
p
) |vi .
For any U, W ∈ U(C
m
), we have
|f(U) − f (W )| =
Tr
((UP U
∗
− W P W
∗
) ⊗ 1) |vihv|
≤ kUP U
∗
− W P W
∗
k
≤ kUP U
∗
− W P U
∗
k + kW P U
∗
− W P W
∗
k
≤ kU − W k + kU
∗
− W
∗
k
≤ 2 kU − W k
F
.
So f is 2-Lipschitz.
Let U ∈ U(C
m
) be a Haar-random unitary operation. The expectation of f(U ) is:
E[f(U )] = hv|
E[U P U
∗
] ⊗ 1
|vi
= hv|
`
1
m
⊗ 1
|vi
=
`
m
.
Since UP U
∗
and M have the same distribution, by Theorem 2.2 we get
Pr
hv|(M ⊗ 1) |vi ≥
α`
2m
= Pr
hv|(UP U
∗
⊗ 1) |vi ≥
α`
2m
≤ exp
−
(m − 2)(α − 2)
2
`
2
384m
2
!
.
By Eq. (3.1), we get
Pr
kM ⊗ 1
C
p
k
W
≥
α`
m
≤
8m
α`
2d
exp
−
(m − 2)(α − 2)
2
`
2
384m
2
!
≤ exp
−
(m − 2)(α − 2)
2
`
2
768m
2
!
,
provided the m, `, d, α satisfy the stated condition.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 13
3.2 The ensemble and its compressibility
We study an ensemble of the same form as in Ref. [17]. For positive integers n, m, k such
that k divides m and n, let B
i
= (|b
i1
i, |b
i2
i, . . . , |b
im
i) be a suitably chosen orthonormal
basis for C
m
, for each i ∈
n
k
. Let (B
ij
: j ∈ [k]) be a partition of B
i
into k equal size
sets. Define ρ
ij
:
=
k
m
P
|vi∈B
ij
|vihv|. We show that there is a choice of bases such that the
ensemble
1
n
, ρ
ij
: i ∈
n
k
, j ∈ [k]
(3.2)
cannot be compressed significantly in the absence of shared entanglement. The following
theorem, which we prove along the same lines as Theorem 5 in Ref. [17], contains the crux
of the argument.
Theorem 3.3. Let β ∈ (0, 1), ∈ (0, 2), and ν ∈ (0, 1 − /2). Let k, m, n, d be positive
integers such that k divides m and n. There exists an ensemble of n quantum states (ρ
ij
) of
the form in Eq. (3.2) such that for any sequence of quantum states
σ
ij
: σ
ij
∈ D(C
d
), i ∈
n
k
, j ∈ [k]
, and for all quantum channels Ψ : L(C
d
) → L(C
m
), we have
(i, j) : kρ
ij
− Ψ(σ
ij
)k
tr
>
> βn ,
when
k ≥
4
1 − /2 − ν
,
m > max
3
γ
ln
e
1 − β
,
3
γ
ln k, 2 +
d
γ
ln
16
1 − /2 − ν
, and
n >
6kd
2
m
γ(1 − β)
ln
8
√
d
ν
!
,
where γ
:
=
(1−/2−ν)
2
8×768
.
Proof: We use the Probabilistic Method to show the existence of an ensemble with the
claimed property. We first derive a simpler property that suffices.
For i ∈
n
k
and j ∈ [k], let τ
ij
∈ D(C
m
) be m-dimensional quantum states and M
ij
be the
orthogonal projection onto the support of τ
ij
. By Proposition 2.3, the condition
Tr (M
ij
τ
ij
) − Tr (M
ij
Ψ(σ
ij
))
>
2
(3.3)
implies that kτ
ij
− Ψ(σ
ij
)k
tr
> . Since Tr(M
ij
τ
ij
) = 1, Eq. (3.3) is equivalent to
Tr (M
ij
Ψ(σ
ij
)) < 1 −
2
. (3.4)
Consider the following Stinespring representation [29, Corollary 2.27, Sec. 2.2] of the quan-
tum channel Ψ : L(C
d
) → L(C
m
) in terms of a unitary operation U ∈ U(A ⊗ B ⊗C) and a
fixed pure state |
¯
0i ∈ B ⊗ C, with A = C
d
, B = C = C
m
:
Ψ(ω) = Tr
A⊗B
h
U(ω ⊗ |
¯
0ih
¯
0|)U
∗
i
∀ω ∈ L(C
d
) .
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 14
So we have
Tr (M
ij
Ψ(σ
ij
)) = Tr
M
ij
Tr
A⊗B
U(σ
ij
⊗ |
¯
0ih
¯
0|)U
∗
= Tr
(M
ij
⊗ 1
A⊗B
) U(σ
ij
⊗ |
¯
0ih
¯
0|)U
∗
,
and Eq. (3.4) is equivalent to
Tr
(M
ij
⊗ 1
A⊗B
) U(σ
ij
⊗ |
¯
0ih
¯
0|)U
∗
< 1 −
2
. (3.5)
For a fixed unitary operator U, for any i, j, the state U(σ
ij
⊗ |
¯
0ih
¯
0|)U
∗
belongs to D(X)
where X
:
= U(A⊗|
¯
0i) is a fixed d-dimensional subspace of A⊗B⊗C. Thus, the expression
on the left in Eq. (3.5) is bounded by kM
ij
⊗ 1
A⊗B
k
X
for every i, j. So it suffices to exhibit
an ensemble such that for all d-dimensional subspaces W ⊆ A ⊗ B ⊗ C,
(i, j) : kM
ij
⊗ 1
A⊗B
k
W
< 1 −
2
> βn .
By Lemma 3.1, for any ν > 0, there is a collection T of subspaces of A⊗B⊗C of dimension
at most d, such that size |T| ≤ (8
√
d/ν)
2d
2
m
2
, and for all subspaces W as above, there is
a subspace Y ∈ T such that for all i, j,
kM
ij
⊗ 1
A⊗B
k
W
− kM
ij
⊗ 1
A⊗B
k
Y
≤ ν .
Taking ν < 1 −
2
, it suffices to produce an ensemble such that for all subspaces Y ∈ T,
(i, j) : kM
ij
⊗ 1
A⊗B
k
Y
< 1 −
2
− ν
> βn . (3.6)
We pick bases B
i
independently and uniformly at random, i.e., for each i, independently
pick a Haar-random unitary operator on C
m
, and let B
i
be the basis defined by its columns.
Partition B
i
into k sets (B
ij
: j ∈ [k]) of equal size. We then define an ensemble of the
form in Eq. (3.2) with ρ
ij
:
=
k
m
P
|vi∈B
ij
|vihv|, and the corresponding projection opera-
tors M
ij
:
=
P
|vi∈B
ij
|vihv|. We show that with non-zero probability, the operators M
ij
satisfy Eq. (3.6) for all Y ∈ T, by bounding the probability of the complementary event.
Suppose the operators M
ij
do not satisfy Eq. (3.6) for some subspace Y ∈ T. Then
(i, j) : kM
ij
⊗ 1
A⊗B
k
Y
< 1 −
2
− ν
≤ βn . (3.7)
Equivalently, there are at least (1 − β)n pairs i, j such that kM
ij
⊗ 1k
Y
≥ 1 −/2 −ν. In
particular, there are at least (1 − β)n/k indices i such that there is at least one j ∈ [k]
with kM
ij
⊗ 1k
Y
≥ 1 −/2 −ν. For convenience, by E
i
(Y) we denote the event that there
is some j ∈ [k] with kM
ij
⊗ 1k
Y
≥ 1 − /2 − ν, and by I(Y), we denote the subset of
indices i ∈
n
k
such that E
i
(Y) occurs.
Let q
:
= d(1 − β)
n
k
e. By the above reasoning, it suffices to bound the probability that for
some subspace Y ∈ T, the subset I(Y) has at least q indices.
By Lemma 3.2, for a fixed subspace Y and pair i, j,
Pr
h
kM
ij
⊗ 1k
Y
≥ 1 − /2 − ν
i
≤ exp
−
((1 − /2 − ν)k − 2)
2
(m − 2)
768k
2
!
≤ exp(−γm) ,
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 15
with γ
:
=
(1−/2−ν)
2
8×768
, when (1 − /2 − ν)k ≥ 4 and
m − 2 ≥
(16 × 384)d
(1 − /2 − ν)
2
ln
8
1 − /2 − ν
.
So by the Union Bound
Pr
h
E
i
(Y)
i
≤ k exp(−γm) ,
and by the Union Bound and the independence of M
ij
for distinct indices i,
Pr
h
|I(Y)| ≥ q
i
≤
n
k
q
!
× (k exp(−γm))
q
.
Finally, we get
Pr
h
∃Y ∈ T : Eq. (3.7) holds
i
≤ |T| × max
Y∈T
Pr
h
|I(Y)| ≥ q
i
≤
8
√
d
ν
!
2d
2
m
2
n
k
q
!
(k exp(−γm))
q
< 1 ,
when m > max
n
3
γ
ln
e
1−β
,
3
γ
ln k
o
, and
γ(1 − β)n > 6kd
2
m ln
8
√
d
ν
!
.
This proves the theorem.
Note that the above proof considers an arbitrary choice of states σ
ij
and quantum channel Ψ
after the ensemble is chosen randomly. Together, the sequence (σ
ij
) and the channel Ψ
constitute a compression protocol. The proof shows that no matter how (σ
ij
) and Ψ are
chosen, the error due to the corresponding compression protocol is large if the dimension d
is much smaller than m (provided n is chosen properly).
3.3 Application to entanglement cost
Consider a one-way protocol Π in which with probability 1/n, Alice gets input (i, j), pre-
pares state ρ
ij
as in an ensemble given by Theorem 3.3, and sends it to Bob. The ensemble
average ρ is the completely mixed state
1
m
over C
m
. By construction, we have S(ρ
ij
kρ) =
log k, and therefore QIC(Π) =
1
2
log k. In fact, we have S
max
(ρ
ij
kρ) = log k. Theo-
rem I.1(1) of Ref. [4] gives us a protocol for the visible compression of any such ensemble
of states using classical communication and shared entanglement, with error . The com-
munication cost of this protocol is
I
/
√
2
max
(A : B)
τ
+ O(log log(1/)) ,
where τ
AB
:
=
1
n
P
ij
|ijihij|
A
⊗ ρ
B
ij
and we have used Proposition 2.4 to translate between
purified and trace distance. This expression is bounded from above by log k + O(log log
1
),
since S
max
(ρ
ij
kρ) (and therefore I
max
(A : B)
τ
) equals log k. Using superdense coding [29,
Section 6.3.1], we get a bound on the quantum communication cost of compressing the
ensemble with entanglement assistance.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 16
Proposition 3.4. For any positive integers k, m, n such that k divides m and n, and
error parameter > 0, any ensemble of n equally likely quantum states in D(C
m
) of the
form in Eq. (3.2) there is a one-shot one-way protocol with shared entanglement for
compressing the states with quantum communication at most
1
2
log k + O(log log
1
) ,
with average error at most in trace distance.
This bound is an additive term of O(log log
1
) more than QIC(Π). Theorem I.1(1) in
Ref. [4] also gives a lower bound of (1/2) I
√
max
(A : B)
τ
on the communication cost, which is
at least (1/2) log k−2 for ≤ 1/81 (see Proposition A.1 in the appendix). So for constant ,
the upper bound in Proposition 3.4 is close to optimal as a function of k. It is slightly better
than those obtained from protocols for state splitting (see, e.g., Ref. [1, Corollary 5]), which
have an additive term of order log
1
. However, the protocol from Ref. [4] has entanglement
cost of order k(log
1
) log m, which is exponential in the communication cost, while the
protocol for state splitting with the least known communication cost [1, Corollary 5] has
entanglement cost of order (1 + 1/
2
) log(m/).
Next we consider how small the entanglement cost of the visible compression of an ensem-
ble (ρ
ij
) given by Theorem 3.3 may be. By choosing the parameters in the statement of
Theorem 3.3 appropriately, we get the following lower bound on the sum of communication
and entanglement costs of any compression protocol.
Corollary 3.5. There exist universal constants c
1
, c
2
, c
3
> 0 such that for any ∈ (0, 1)
and any positive integers k, m, n with m and n divisible by k, there is an ensemble of n
equally likely quantum states in D(C
m
) of the form in Eq. (3.2) for which any (one-shot)
one-way protocol for compressing the states with average error at most
2
, the sum of the
communication and entanglement costs is at least
log m − 2 log
1
1 −
− log ln
16
1 −
− c
2
, (3.8)
when k ≥ 6/(1 − ), m ≥ c
1
(ln k)/(1 − )
2
, and
n ≥
c
3
(1 − )
2
km
3
ln
16
√
m
.
In particular, the entanglement cost of any such protocol with optimal communication
cost is at least
log m −
1
2
log k −O
log
1
1 −
− O(1) ,
and the communication cost of any such protocol without entanglement is at least the
bound given in Eq. (3.8).
We defer the proof of this corollary to the appendix.
Note that the parameter m may be chosen arbitrarily larger than k, provided the number
of states n in the ensemble is chosen large enough. Thus, we see that there are ensembles
with m-dimensional states for which communication-optimal compression protocols with
shared entanglement and with constant average error, say 1/4, have entanglement cost
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 17
almost as large as log m. In particular, the number of qubits of shared entanglement needed
may be arbitrarily larger than the quantum information cost of the original protocol.
We also see that in the absence of shared entanglement, there are ensembles with m-
dimensional states that cannot be compressed to states with dimension smaller than cm
with average error less than 1/4, where c is a universal positive constant. In particular,
the optimally compressed message may be arbitrarily longer than the quantum information
cost of the protocol Π.
Corollary 3.5 shows that the number of qubits of shared entanglement used by protocol
with the smallest known communication cost, due to Anshu and Jain [1, Corollary 5], is
optimal up to a constant multiplicative factor and an additive log k term (for constant
error in compression). The lower bound on entanglement cost given in the corollary may
be achieved by protocols derived from those for state splitting, up to an additive term
of
1
2
log k + O(1), again for constant error (see, e.g., Ref. [7, Lemma 3.3]). However, the
communication cost of these protocols may not be optimal.
The probabilistic construction in the results above gives us ensembles with a number
of states n that is polynomial in m and k. Note that in the compression protocol Π
0
,
Alice may send the input (i, j) as her message, in which case the message register has
dimension n. Similarly, she may send the state ρ
ij
itself, and this has dimension m.
So in order to study how much compression is truly possible (i.e., how much smaller the
dimension of the message register may be as compared with m), we have to study ensembles
with n ≥ m states, and compression protocols with message registers with dimension at
most m. Further, consider any protocol Γ (similar to Π) in which Alice receives a random
input x out of n possibilities according to some distribution, prepares a state ω
x
and sends
it to Bob. The quantum information cost of such a protocol Γ is at most
1
2
log n. So
the polynomial dependence of n on the dimension of the states in the ensemble (m in the
construction above) and the exponential dependence of n on the quantum information cost
of the corresponding protocol (
1
2
log k in the construction) is inevitable.
4 Concluding remarks
In this article, we revisited one-shot compression of an ensemble of quantum states. We
proved that there are ensembles which cannot be compressed by more than a few qubits
in the absence of shared entanglement, when allowed constant error. In the presence of
shared entanglement, the ensemble can be compressed to many fewer qubits. However,
the entanglement cost may not be smaller than the number of qubits being compressed by
more than a constant, for constant error. Since we study compression protocols that are
allowed to make some error, the bounds we establish are robust to perturbations to the
shared entangled state that are sufficiently small relative to the error.
Entanglement and quantum communication are distinct resources in the context of in-
formation processing. Sharing entanglement involves the generation, distribution, and
storage of a state that is independent of the input for the task at hand. Communication
also involves the same steps, but may be dynamic, i.e., may depend on the input and the
prior history of the communication protocol. Consequently, any physical implementation
of these resources is likely to incur different costs for these steps. In this work, we focused
on the cost of distributing quantum states, and as a first stab, assumed that the cost of
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 18
distribution for shared entanglement or for communication is proportional to the number of
qubits involved. Formally, this corresponds to the notion of smooth 0-Rényi entropy. The
motivation for this focus comes largely from the area of communication complexity [21], in
which the interaction between multiple processors takes centre stage, but shared entangle-
ment is often taken for granted. Our result shows that entanglement plays a crucial role in
important communication tasks and highlights the need for considering entanglement cost
in addition to communication cost.
A question of interest, from a theoretical perspective, is the degree or strength of entan-
glement required for different information processing tasks. Several different measures of
entanglement have been studied in the literature, depending on the context. Smooth 0-
Rényi entropy is a very coarse measure in this respect, as it may be the same for states
that are regarded as having widely different degrees of entanglement. A natural question
is whether results such as the ones we derived also hold for other definitions of entangle-
ment cost that capture the degree of entanglement more satisfactorily. We conjecture that
analogous results hold also for other measures, and leave this to future work.
Many other questions surrounding compression remain open. For instance, we do not have
tight characterizations for the communication and entanglement costs of one-shot state
re-distribution. Even lesser is known for the one-shot compression of interactive quantum
protocols. Progress on these questions might hold the key to resolving important questions
in communication complexity as well.
References
[1] Anurag Anshu and Rahul Jain. Efficient methods for one-shot quan-
tum communication. Technical Report arXiv:1809.07056 [quant-ph], arXiv.org,
https://arxiv.org/abs/1809.07056, September 2018.
[2] Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui
Yao. New one shot quantum protocols with application to communication com-
plexity. IEEE Transactions on Information Theory, 62(12):7566–7577, 2016. DOI:
10.1109/TIT.2016.2616125.
[3] Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential sep-
aration of quantum communication and classical information. In Proceedings of
the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017,
pages 277–288, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4528-6. DOI:
10.1145/3055399.3055401.
[4] Shima Bab Hadiashar, Ashwin Nayak, and Renato Renner. Communication complex-
ity of one-shot remote state preparation. IEEE Transactions on Information Theory,
64(7):4709–4728, July 2018. DOI: 10.1109/TIT.2018.2811509.
[5] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Ben-
jamin Schumacher. On quantum coding for ensembles of mixed states. Journal
of Physics A: Mathematical and General, 34(35):6767–6785, August 2001. DOI:
10.1088/0305-4470/34/35/304.
[6] Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, and Andreas
Winter. The quantum reverse Shannon theorem and resource tradeoffs for simulating
quantum channels. IEEE Transactions on Information Theory, 60(5):2926–2959, May
2014. ISSN 0018-9448. DOI: 10.1109/TIT.2014.2309968.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 19
[7] 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, August 2011. ISSN 1432-0916. DOI: 10.1007/s00220-011-
1309-7.
[8] Mario Berta, Matthias Christandl, and Dave Touchette. Smooth entropy bounds on
one-shot quantum state redistribution. IEEE Transactions on Information Theory,
62(3):1425–1439, March 2016. DOI: 10.1109/TIT.2016.2516006.
[9] Igor Devetak. Triangle of dualities between quantum communication protocols. Phys-
ical Review Letters, 97:140503, Oct 2006. DOI: 10.1103/PhysRevLett.97.140503.
[10] Igor Devetak and Jon Yard. Exact cost of redistributing multipartite quantum
states. Physical Review Letters, 100(230501), June 2008. DOI: 10.1103/Phys-
RevLett.100.230501.
[11] Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability
measures for quantum-mechanical states. IEEE Transactions on Information Theory,
45(4):1216–1227, May 1999. ISSN 1557-9654. DOI: 10.1109/18.761271.
[12] 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.
DOI: 10.1103/PhysRevA.71.062310.
[13] Carl W. Helstrom. Detection theory and quantum mechanics. Information and Con-
trol, 10(3):254–291, 1967. DOI: 10.1016/S0019-9958(67)90302-6.
[14] Alexander S. Holevo. An analogue of statistical decision theory and noncommutative
probability theory. Trudy Moskovskogo Matematicheskogo Obshchestva, 26:133–149,
1972.
[15] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Partial quantum in-
formation. Nature, 436(7051):673–676, August 2005. DOI: 10.1038/nature03909.
[16] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Quantum state merg-
ing and negative information. Communications in Mathematical Physics, 269(1):107–
136, January 2007. DOI: 10.1007/s00220-006-0118-x.
[17] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in
communication complexity via message compression. In Jos C. M. Baeten, Jan Karel
Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages
and Programming, volume 2719 of Lecture Notes in Computer Science, pages 300–315,
Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45061-0. DOI:
10.1007/3-540-45061-0_26.
[18] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message
compression and privacy in quantum communication. In Proceedings of the 20th An-
nual IEEE Conference on Computational Complexity, pages 285–296. IEEE Computer
Society, 2005. DOI: 10.1109/CCC.2005.24.
[19] Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and pri-
vacy trade-off results for quantum and classical communication complexity. Technical
Report arXiv:0807.1267v1 [cs.DC], arXiv.org, https://arxiv.org/abs/0807.1267,
July 2008.
[20] Zahra B. Khanian and Andreas Winter. Entanglement-assisted quantum data com-
pression. In 2019 IEEE International Symposium on Information Theory (ISIT),
pages 1147–1151, 2019. DOI: 10.1109/ISIT.2019.8849352.
[21] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Founda-
tions and Trends in Theoretical Computer Science, 3(4):263–399, 2009. ISSN 1551-
305X. DOI: 10.1561/0400000040.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 20
[22] Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, and Scott Aaronson.
Doubly infinite separation of quantum information and communication. Phys. Rev.
A, 93:012347, Jan 2016. DOI: 10.1103/PhysRevA.93.012347.
[23] Zhicheng Luo and Igor Devetak. Channel simulation with quantum side information.
IEEE Transactions on Information Theory, 55(3):1331–1342, March 2009. ISSN 0018-
9448. DOI: 10.1109/TIT.2008.2011424.
[24] Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in
Mathematics. Springer-Verlag New York, 1st edition, 2002. ISBN 978-0-387-95373-1.
DOI: 10.1007/978-1-4613-0039-7.
[25] Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups,
volume 218 of Cambridge Tracts in Mathematics. Cambridge University Press, July
2019. DOI: 10.1017/9781108303453.
[26] Vitali D. Milman and Gideon Schechtman. Asymptotic Theory of Finite Dimensional
Normed Spaces, volume 1200 of Lecture notes in mathematics. Springer-Verlag Berlin
Heidelberg, 1986. DOI: 10.1007/978-3-540-38822-7.
[27] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth
min- and max-entropies. IEEE Transactions on Information Theory, 56(9):4674–4681,
September 2010. ISSN 0018-9448, 1557-9654. DOI: 10.1109/TIT.2010.2054130.
[28] Dave Touchette. Quantum information complexity. In Proceedings of the Forty-
seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages
317–326, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3536-2. DOI:
10.1145/2746539.2746613.
[29] John Watrous. The Theory of Quantum Information. Cambridge University Press,
May 2018. DOI: 10.1017/9781316848142.
[30] Jon T. Yard and Igor Devetak. Optimal quantum source coding with quantum side
information at the encoder and decoder. IEEE Transactions on Information Theory,
55(11):5339–5351, November 2009. ISSN 0018-9448. DOI: 10.1109/TIT.2009.2030494.
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 21
A Proofs of some claims
In this section, we include the proofs of some statements from the main body of the article.
Proof of Corollary 3.5: We invoke Theorem 3.3 with ∈ (0, 1), ν = /2, β = 1/2
and k, m, n satisfying the conditions stated in the corollary. Then γ as in Theorem 3.3
equals (1 − )
2
/(8 ×768). We take c
1
:
= (24 ×768) + 1, so that m > (3/γ) ln k. Since k ≥
6/(1 − ), we have k > 6 > 2e = e/(1 − β), and m > (3/γ) ln(e/(1 − β)). We take c
3
:
=
(6 × 2 × 8 × 768) + 1 so that n > (6km
3
/γ(1 − β)) ln(8
√
m/ν).
Now we consider an ensemble (ρ
ij
) given by Theorem 3.3. Let Π
0
be any one-way proto-
col, possibly with shared entanglement, for the visible compression of the ensemble (ρ
ij
)
with average error at most /2. Following the notation from Section 2.2, suppose that
Bob holds registers M E
B
just after he receives the message M from Alice in Π
0
. If the
entanglement cost of Π
0
is e, we may assume that the register E
B
may be partitioned
into sub-registers E
1B
E
2B
with |E
1B
| = e, and that the state of register E
B
is of the
form ω ⊗ |0ih0|, where E
1B
is in state ω and E
2B
in state |0ih0|, and |0i is a pure state.
(We may achieve this by applying a suitable isometry to register E
B
.)
Let d
:
= |M E
1B
|, so that the sum of the communication and entanglement costs of Π
0
is log d, and let σ
ij
be the state of the registers ME
1B
with Bob when Alice is given
input (i, j). If d ≥ m, the bound in Eq. (3.8) holds, so consider the case when d < m.
Then the choice of n above implies that n > (6kd
2
m/γ(1 − β)) ln(8
√
d/ν).
Since the average error of Π
0
is at most /2, by the Markov Inequality we have
(i, j) : kρ
ij
− Ψ(σ
ij
)k
tr
>
<
n
2
= βn ,
where Ψ is the quantum channel corresponding to Bob’s decompression operation in Π
0
.
Theorem 3.3 then implies that
2 +
d
γ
ln
16
1 − /2 − ν
≥ m .
Since m −2 ≥ m/2, this gives us the bound stated in Eq. (3.8) with c
2
:
= log(16 ×768).
Proposition A.1. Let (ρ
ij
) be an ensemble of the form in Eq. (3.2), and let the state τ
AB
be defined as
1
n
P
ij
|ijihij|
A
⊗ ρ
B
ij
. For any ζ ∈ [0, 1/8), we have
I
ζ
max
(A : B)
τ
≥ log k − log
3 − 12ζ
1 − 8ζ
.
Proof: As shown in Ref. [4, Proposition II.5], there is a classical-quantum state τ
0
within
purified distance ζ of τ such that I
ζ
max
(A : B)
τ
= I
max
(A : B)
τ
0
. Let τ
0
:
=
P
ij
q
ij
|ijihij| ⊗
e
ρ
ij
.
By Proposition 2.4, we have
τ − τ
0
tr
≤ 2ζ . (A.1)
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 22
Let ξ
:
= 2ζ. By monotonicity of trace distance under measurements [29, Proposition 3.5],
we further get
X
ij
|q
ij
− p
ij
| ≤ ξ .
If q
ij
> 3/2n or q
ij
< 1/2n, we have |q
ij
− p
ij
| > 1/2n. So for at least (1−2ξ)n pairs (i, j),
we have 1/2n ≤ q
ij
≤ 3/2n, and we call such pairs (i, j) typical.
Eq. (A.1) may be written as
X
ij
kq
ij
e
ρ
ij
− p
ij
ρ
ij
k
tr
≤ ξ ,
so, by monotonicity of trace distance,
X
ij
X
|vi∈B
ij
q
ij
hv|
e
ρ
ij
|vi−
k
nm
≤ ξ ,
where B
ij
is as in the definition of the ensemble (ρ
ij
). In particular,
X
typical ij
X
|vi∈B
ij
q
ij
hv|
e
ρ
ij
|vi−
k
nm
≤ ξ . (A.2)
There are at least (1 − 2ξ)n/k indices i ∈ [n/k] such that there is a typical pair (i, j) for
some j ∈ [k]. Let S be the set of such indices i. Let η ∈ (0, 1). If for all indices i ∈ S,
there are less than (1 − η)m pairs (j, v) with (i, j) typical, |vi ∈ B
ij
, and
k
2nm
≤ q
ij
hv|
e
ρ
ij
|vi ≤
3k
2nm
, (A.3)
then we would have
X
typical ij
X
|vi∈B
ij
q
ij
hv|
e
ρ
ij
|vi−
k
nm
> (1 − 2ξ)
n
k
× ηm ×
k
2nm
= (1 − 2ξ)
η
2
.
Taking η
:
= 2ξ/(1 − 2ξ), we see that this is in contradiction with Eq. (A.2). So there is
an index i ∈ S such that there are at least (1 − η)m pairs (j, v) with j ∈ [k] and |vi ∈ B
ij
such that (i, j) is typical, and (i, j, v) satisfy Eq. (A.3). Denote such an index i by i
0
, and
let
T
:
=
n
(j, v) : j ∈ [k], |vi ∈ B
i
0
j
, (i
0
, j) typical , (i, j, v) satisfy Eq. (A.3)
o
.
We have that for all the pairs (j, v) ∈ T ,
k
2nm
≤ q
i
0
j
hv|
e
ρ
i
0
j
|vi ≤
3
2n
hv|
e
ρ
i
0
j
|vi ,
so that
k
3m
≤ hv|
e
ρ
i
0
j
|vi . (A.4)
Let σ ∈ D(C
m
) be a state that achieves I
max
(A : B)
τ
0
, and let λ denote this max-
information. For typical pairs (i, j), since q
ij
> 0, we have
e
ρ
ij
≤ 2
λ
σ. By Eq. (A.4), we
also have k/3m ≤ 2
λ
hv|σ|vi for all pairs (j, v) ∈ T . Summing up over all pairs (j, v) ∈ T ,
we get (1 −η)k/3 ≤ 2
λ
, as the sets B
i
0
j
are a partition of an orthonormal basis, and σ has
trace at most 1. So λ ≥ log k −log(3/(1 − η)).
Accepted in Quantum 2020-06-10, click title to verify. Published under CC-BY 4.0. 23