Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

A Tight Lower Bound on the Classical Communication Cost of Entanglement Dilution

Aram W. Harrow, Hoi‐Kwong Lo

Published Feb 1, 2004• 49 citations
Publisher

Abstract

Suppose two distant observers, Alice and Bob, share some form of entanglement - quantum correlations - in some bipartite pure quantum states. They may apply local operations and classical communication to convert one form of entanglement to another. Since entanglement is regarded as a resource in quantum information processing, it is an important question to ask how much classical communication, which is also a resource, is needed in the inter-conversion process of entanglement. In this paper, we address this important question in the many-copy case. The inter-conversion process of entanglement is usually divided into two types: concentrating the entanglement from many partially entangled states into a smaller number of maximally entangled states (i.e., singlets) and the reverse process of diluting singlets into partially entangled states. It is known that entanglement concentration requires no classical communication, but the best prior art result for diluting to N copies of a partially entangled state requires an amount of communication on the order of /spl radic/N. Our main result is to prove that this prior art result is optimal up to a constant factor; any procedure for approximately creating N partially entangled states from singlets requires /spl Omega/(/spl radic/N) bits of classical communication. Previously not even a constant bound was known for approximate entanglement transformations. We also prove a lower bound on the inefficiency of the process: to dilute singlets to N copies of a partially entangled state, the entropy of entanglement must decrease by /spl Omega/(/spl radic/N). Moreover, we introduce two new tools - /spl delta/-significant subspaces and the standard form protocol reduction in entanglement manipulations. We hope that these two new tools will be useful in other work in quantum information theory.

DOI
10.1109/tit.2003.822597

Related papers

A tight lower bound on the classical communication cost of entanglement dilution

Aram W. Harrow, Hoi‐Kwong Lo

Entanglement concentration requires no classical communication, but the best prior art result for diluting to N copies of a partially entangled state requires an amount of communication on the order of sqrt(N) bits. Our main result is to prove this prior art result optimal up to a constant factor; any procedure for creating N partially entangled states from singlets requires Omega(sqrt(N)) bits of classical communication. Previously not even a constant bound was known for approximate entanglement transforms. We also prove a lower bound on the inefficiency of the process: to dilute singlets to N copies of a partially entangled state, the entropy of entanglement must decrease by Omega(sqrt(N)).

arXiv:quant-ph/0204096•Apr 17, 2002•0 citations

Communication cost of entanglement transformations

Patrick M. Hayden, Andreas Winter

We study the amount of communication needed for two parties to transform some given joint pure state into another one, either exactly or with some fidelity. Specifically, we present a method to lower bound this communication cost even when the amount of entanglement does not increase. Moreover, the bound applies even if the initial state is supplemented with unlimited entanglement in the form of EPR (Einstein-Podolsky-Rosen) pairs and the communication is allowed to be quantum mechanical. We then apply the method to the determination of the communication cost of asymptotic entanglement concentration and dilution. While concentration is known to require no communication whatsoever, the best known protocol for dilution, discovered by H.-K. Lo and S. Popescu [Phys. Rev. Lett. 83, 1459 (1999)], requires exchange of a number of bits that is of the order of the square root of the number of EPR pairs. Here we prove a matching lower bound of the same asymptotic order, demonstrating the optimality of the Lo-Popescu protocol up to a constant factor and establishing the existence of a fundamental asymmetry between the concentration and dilution tasks. We also discuss states for which the minimal communication cost is proportional to their entanglement, such as the states recently introduced in the context of ``embezzling entanglement'' (W. van Dam and P. Hayden, e-print quant-ph/0201041).

arXiv:quant-ph/0204092•Physical Review A•Jan 31, 2003•73 citations

Inefficiency and classical communication bounds for conversion between partially entangled pure bipartite states

Ben Fortescue, Hoi‐Kwong Lo

We derive lower limits on the inefficiency and classical communication costs of dilution between two-term bipartite pure states that are partially entangled. We first calculate explicit relations between the allowable error and classical communication costs of entanglement dilution using a previously described protocol, then consider a two-stage dilution from singlets with this protocol followed by some unknown protocol for conversion between partially entangled states. Applying overall lower bounds on classical communication and inefficiency to this two-stage protocol, we derive bounds for the unknown protocol. In addition we derive analogous (but looser) bounds for general pure states.

arXiv:quant-ph/0411200•Physical Review A•Sep 28, 2005•4 citations

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion

Matthew Coudron, Aram W. Harrow

Entanglement assistance is known to reduce the quantum communication complexity of evaluating functions with distributed inputs. But does the type of entanglement matter, or are EPR pairs always sufficient? This is a natural question because in several other settings maximally entangled states are known to be less useful as a resource than some partially entangled state. These include non-local games, tasks with quantum communication between players and referee, and simulating bipartite unitaries or communication channels. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using $Q$ qubits of communication and arbitrary shared entanglement can be $ε$-approximated by a protocol using $O(Q/ε+\log(1/ε)/ε)$ qubits of communication and only EPR pairs as shared entanglement. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We show that the communication cost of converting between two bipartite quantum states is upper bounded, up to a constant multiplicative factor, by a natural and efficiently computable quantity which we call the $\ell_{\infty}$-Earth Mover's Distance (EMD) between those two states. Furthermore, we prove a complementary lower bound on the cost of state conversion by the $ε$-smoothed $\ell_{\infty}$-EMD, which is a natural smoothing of the $\ell_{\infty}$-EMD that we will define via a connection with optimal transport theory.

arXiv:1902.07699•Leibniz international proceedings in informatics•Jan 1, 2019•1 citation

Inefficiency and classical communication bounds for conversion between partially entangled pure bipartite quantum states

Ben Fortescue, Hoi‐Kwong Lo

We present explicit bounds on the classical communication cost and inefficiency of entanglement dilution via the Lo-Popescu protocol, for the case of two-term (single-qubit) entangled states. By considering a two-stage dilution, we consequently use prior results to obtain meaningful bounds on the classical communication cost and inefficiency of dilution between two-term partially entangled states.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•0 citations

Classical Communication Cost of Entanglement Manipulation: Is Entanglement an Interconvertible Resource?

Hoi‐Kwong Lo, Sandu Popescu

Entanglement bits or ``ebits'' have been proposed as a quantitative measure of a fundamental resource in quantum information processing. It is, thus, important to show that the same number of ebits in different forms are interconvertible in the asymptotic limit. Here we draw attention to a very important but hitherto unnoticed aspect of entanglement manipulation---the classical communication cost. We construct an explicit procedure which demonstrates that for bipartite pure states, in the asymptotic limit, entanglement can be concentrated or diluted with vanishing classical communication cost. Entanglement of bipartite pure states is thus established as a truly interconvertible resource.

arXiv:quant-ph/9902045•Physical Review Letters•Aug 16, 1999•92 citations
Suppose two distant observers, Alice and Bob, share some form of entanglement - quantum correlations - in some bipartite pure quantum states. They may apply local operations and classical communication to convert one form of entanglement to another. Since entanglement is regarded as a resource in quantum information processing, it is an important question to ask how much classical communication, which is also a resource, is needed in the inter-conversion process of entanglement. In this paper, we address this important question in the many-copy case. The inter-conversion process of entanglement is usually divided into two types: concentrating the entanglement from many partially entangled states into a smaller number of maximally entangled states (i.e., singlets) and the reverse process of diluting singlets into partially entangled states. It is known that entanglement concentration requires no classical communication, but the best prior art result for diluting to N copies of a partially entangled state requires an amount of communication on the order of /spl radic/N. Our main result is to prove that this prior art result is optimal up to a constant factor; any procedure for approximately creating N partially entangled states from singlets requires /spl Omega/(/spl radic/N) bits of classical communication. Previously not even a constant bound was known for approximate entanglement transformations. We also prove a lower bound on the inefficiency of the process: to dilute singlets to N copies of a partially entangled state, the entropy of entanglement must decrease by /spl Omega/(/spl radic/N). Moreover, we introduce two new tools - /spl delta/-significant subspaces and the standard form protocol reduction in entanglement manipulations. We hope that these two new tools will be useful in other work in quantum information theory.
Entanglement concentration requires no classical communication, but the best prior art result for diluting to N copies of a partially entangled state requires an amount of communication on the order of sqrt(N) bits. Our main result is to prove this prior art result optimal up to a constant factor; any procedure for creating N partially entangled states from singlets requires Omega(sqrt(N)) bits of classical communication. Previously not even a constant bound was known for approximate entanglement transforms. We also prove a lower bound on the inefficiency of the process: to dilute singlets to N copies of a partially entangled state, the entropy of entanglement must decrease by Omega(sqrt(N)).
We study the amount of communication needed for two parties to transform some given joint pure state into another one, either exactly or with some fidelity. Specifically, we present a method to lower bound this communication cost even when the amount of entanglement does not increase. Moreover, the bound applies even if the initial state is supplemented with unlimited entanglement in the form of EPR (Einstein-Podolsky-Rosen) pairs and the communication is allowed to be quantum mechanical. We then apply the method to the determination of the communication cost of asymptotic entanglement concentration and dilution. While concentration is known to require no communication whatsoever, the best known protocol for dilution, discovered by H.-K. Lo and S. Popescu [Phys. Rev. Lett. 83, 1459 (1999)], requires exchange of a number of bits that is of the order of the square root of the number of EPR pairs. Here we prove a matching lower bound of the same asymptotic order, demonstrating the optimality of the Lo-Popescu protocol up to a constant factor and establishing the existence of a fundamental asymmetry between the concentration and dilution tasks. We also discuss states for which the minimal communication cost is proportional to their entanglement, such as the states recently introduced in the context of ``embezzling entanglement'' (W. van Dam and P. Hayden, e-print quant-ph/0201041).
We derive lower limits on the inefficiency and classical communication costs of dilution between two-term bipartite pure states that are partially entangled. We first calculate explicit relations between the allowable error and classical communication costs of entanglement dilution using a previously described protocol, then consider a two-stage dilution from singlets with this protocol followed by some unknown protocol for conversion between partially entangled states. Applying overall lower bounds on classical communication and inefficiency to this two-stage protocol, we derive bounds for the unknown protocol. In addition we derive analogous (but looser) bounds for general pure states.
Entanglement assistance is known to reduce the quantum communication complexity of evaluating functions with distributed inputs. But does the type of entanglement matter, or are EPR pairs always sufficient? This is a natural question because in several other settings maximally entangled states are known to be less useful as a resource than some partially entangled state. These include non-local games, tasks with quantum communication between players and referee, and simulating bipartite unitaries or communication channels. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using QQQ qubits of communication and arbitrary shared entanglement can be εεε-approximated by a protocol using O(Q/ε+log⁡(1/ε)/ε)O(Q/ε+\log(1/ε)/ε)O(Q/ε+log(1/ε)/ε) qubits of communication and only EPR pairs as shared entanglement. Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We show that the communication cost of converting between two bipartite quantum states is upper bounded, up to a constant multiplicative factor, by a natural and efficiently computable quantity which we call the ℓ∞\ell_{\infty}ℓ∞​-Earth Mover's Distance (EMD) between those two states. Furthermore, we prove a complementary lower bound on the cost of state conversion by the εεε-smoothed ℓ∞\ell_{\infty}ℓ∞​-EMD, which is a natural smoothing of the ℓ∞\ell_{\infty}ℓ∞​-EMD that we will define via a connection with optimal transport theory.
Entanglement bits or ``ebits'' have been proposed as a quantitative measure of a fundamental resource in quantum information processing. It is, thus, important to show that the same number of ebits in different forms are interconvertible in the asymptotic limit. Here we draw attention to a very important but hitherto unnoticed aspect of entanglement manipulation---the classical communication cost. We construct an explicit procedure which demonstrates that for bipartite pure states, in the asymptotic limit, entanglement can be concentrated or diluted with vanishing classical communication cost. Entanglement of bipartite pure states is thus established as a truly interconvertible resource.