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