A tight lower bound on the classical

communication cost of entanglement

dilution

Aram Harrow, MIT Hoi-Kwong Lo, U. Toronto quant-ph/0204096

(See also quant-ph/0204092 for an independent derivation of the same result by P. Hayden and A. Winter.)

March 26, 2004

Entanglement as a Resource

• Alice and Bob act on their joint state using LOCC (local operations and classical communication).

• A pure state |ψ⟩ = ∑_{x} √p_{x}|x⟩_{A} ⊗ |x⟩_{B} can be transformed to |φ⟩ = ∑_{x} √q_{x}|x⟩_{A} ⊗ |x⟩_{B} by LOCC with certainty if and only if p ≺ q (i.e. q majorizes p, so for any k, p_{1} + ⋯ + p_{k} ≤ q_{1} + ⋯ + q_{k}).

• Asymptotically, the only measure of entanglement for pure states is the entropy of entanglement:

E(ψ) = S(tr_{A}|ψ⟩⟨ψ|) = − _{x}^{∑} p_{x} log p_{x}

Entanglement concentration and dilution

• Define |Φ⟩ = \frac{|00⟩+|11⟩}{√2} , Φ = |Φ⟩⟨Φ|, fix |ψ⟩_{AB}, ψ = |ψ⟩⟨ψ| and let E = E(ψ).

• Concentration: There exist LOCC operations {C_{n}} such that ∥C_{n}(ψ^{⊗n}) − Φ^{⊗n(E−δ_{n})}∥_{1} < ϵ_{n}.

• Dilution: There exist LOCC operations {D_{n}} such that ∥D(Φ^{⊗n(E+δ_{n})} ) − ψ^{⊗n}∥_{1} < ϵ_{n}

• Asymptotic reversibility: As n → ∞, ϵ_{n} → 0 and δ_{n} → 0.

Error and inefficiency of concentration and dilution

inefficiency (nδ_{n})  error (ϵ_{n})  CC cost
concentration  O(k√n)  exp (−k^{2}) exact  0
dilution  O(k√n)  exp (−k^{2})  O(k√n)

BBPS (quant-ph/9511030) gave constructions for all but the O(k√n) dilution CC cost, which is due to LP (quant-ph/9902045).

The concentration lower bounds were proven by LP in quantph/9707038.

We will prove the lower bounds for entanglement dilution.

Proof sketch

• Two lemmas – Describe the Schmidt coefficients of ψ^{⊗n}.

– Reduce any protocol to a standard form.

• Two plausible ideas – Reducing local entropy requires communication.

– It doesn’t help to make the state mixed by discarding ancilla systems.

Lemma: Significant subspaces

Let ρ = tr_{A}ψ. The eigenvalues of − log ρ^{⊗n} are distributed approximately according to a Gaussian with mean nE = −n Tr ρ log ρ and variance nα^{2} = n Tr ρ(log ρ + E)^{2}.

Lemma: Any projector Π with Tr Πρ^{⊗n} > 1 − ϵ must have Tr Π ≥ C2^{nE+α√n} for ϵ < 0.05, C < 0.01, n > 10^{7} Tr ρ| log ρ + E|^{3}.

Corollary: Since Schmidt number never increases under LOCC, the entanglement dilution must have inefficiency of at least α√n in order to achieve fidelity 1 − ϵ.

In contrast, variable yield entanglement concentration obtains nE − O(log n) ± O(√n) singlets.

This argument works for any ϵ < 1/2.

Lemma: protocol reduction

Any LOCC protocol that begins with a bipartite pure state may be reduced to a protocol involving only one round of communication from Alice to Bob with no increase in the total amount of communication.

In quant-ph/9707038, a similar protocol reduction was proved without controlling the amount of classical communication.

Idea: Reducing local entropy requires communication

Start with a D-dimensional maximally entangled state. Choose a successful measurement outcome M. It occurs with probability p = Tr MM^{†}/D. Alice’s post-measurement state is X = MM^{†}/ Tr MM^{†}. Pretend she doesn’t discard any ancilla, so X ≈ ρ^{⊗n}.

2^{nE+α√n} ≤ rank X ≤ D
2^{−nE+α√n} ≤ ∥X∥_{∞} = \frac{∥MM^{†}∥_{∞}}{Tr MM^{†}} ≤ \frac{1}{Tr MM^{†}} = \frac{1}{pD}

Thus p ≤ 2^{−2α√n}.

Result: Communication lower bound

Each successful measurement outcome has probability ≤ 2^{−2α√n}. The protocol communicates c bits, so there are ≤ 2^{c} successful measurement outcomes. Let the total probability of success be 2^{−s}. Then c + s ≥ 2α√n.

Idea: Discarding ancilla doesn’t matter

After discarding ancilla, Alice and Bob have a nearly pure state, so their ancilla must have been nearly disentangled before being discarded.

Improvements and future directions

For a general asymptotic transformation |ψ⟩^{⊗m} → |φ⟩^{⊗n}, how much communication is necessary?

Find the optimal error exponenet for entanglement dilution, and a univeral protocol achieving it. (HM in quant-ph/0209030 did this for concentration.)

Find polynomial-time quantum algorithms for these transformations. (I have a dilution algorithm using O(√n) communication, but its error exponent is not optimal.)

Find an application for which partially entangled states are more useful than maximally entangled states. (Remote state preparation of entangled states, perhaps?)