Simple Algorithm
Quantum Computing · Rydberg State · 30 min

LOCC Transformations & Majorization

Nielsen's theorem: when one entangled state can become another.

When can one entangled pure state be turned into another by LOCC, with certainty? Nielsen's 1999 answer is a statement from the classical theory of inequalities: majorization. The picture it paints is rich. Some pairs of states are incomparable, a borrowed catalyst can unlock a forbidden conversion and be returned untouched, and in the many-copy limit everything collapses to a single number.

What you’ll learn

  • Use the equivalent characterizations of majorization: partial sums, doubly stochastic matrices, convex functions and unitary mixing.
  • State and prove Nielsen's theorem: ∣ψ⟩→∣ϕ⟩\ket\psi\to\ket\phi by LOCC iff λψ≺λϕ\lambda_\psi\prec\lambda_\phi.
  • Compute optimal conversion probabilities with Vidal's formula and recognize incomparable pairs.
  • Explain entanglement catalysis and embezzlement, and how the single-copy rules relate to the asymptotic rate E(ψ)/E(ϕ)E(\psi)/E(\phi).

The majorization toolkit

Two consequences do most of the work below. First, Schur-concave functions such as the Shannon and Rényi entropies are monotone: x≺y⇒H(x)≥H(y)x\prec y\Rightarrow H(x)\ge H(y). Second, Ky Fan's principle: the sum of the kk largest eigenvalues of a Hermitian AA equals max⁡Tr⁡(PA)\max\Tr(PA) over rank-kk projectors PP, so it is a convex function of AA.

Nielsen's theorem

Two reductions make the proof short. (i) Lo–Popescu: for pure bipartite states, any LOCC protocol, however many rounds it uses, can be replaced by a one-way protocol in which Alice measures with Kraus operators MjM_j and Bob applies a unitary UjU_j depending on her outcome. Bob's measurements can be traded for Alice's because of the symmetry of the Schmidt form. (ii) Bob's unitary does not change Alice's reduced state.

Derivation(⇒) A conversion protocol implies majorization
  1. (Mj⊗Uj)∣ψ⟩=pj ∣ϕ⟩for every outcome j(M_j\otimes U_j)\ket\psi=\sqrt{p_j}\,\ket\phi\qquad\text{for every outcome } j

    Every branch must end in ∣ϕ⟩\ket\phi.

  2. Mj ρψ Mj†=pj ρϕM_j\,\rho_\psi\,M_j^\dagger=p_j\,\rho_\phi

    Trace out Bob; his unitary drops out.

  3. Mjρψ=pj ρϕ  Vj(Vj unitary)M_j\sqrt{\rho_\psi}=\sqrt{p_j\,\rho_\phi}\;V_j\qquad(V_j\ \text{unitary})

    Polar decomposition: Xj=MjρψX_j=M_j\sqrt{\rho_\psi} satisfies XjXj†=pjρϕX_jX_j^\dagger=p_j\rho_\phi, so Xj=XjXj† VjX_j=\sqrt{X_jX_j^\dagger}\,V_j.

  4. ρψ=ρψ(∑jMj†Mj)ρψ=∑jXj†Xj=∑jpj Vj† ρϕ Vj\rho_\psi=\sqrt{\rho_\psi}\Big(\sum_jM_j^\dagger M_j\Big)\sqrt{\rho_\psi}=\sum_jX_j^\dagger X_j=\sum_jp_j\,V_j^\dagger\,\rho_\phi\,V_j

    Use completeness, ∑jMj†Mj=I\sum_jM_j^\dagger M_j=\id, then the previous line.

  5. ∑i≤kλi↓(ρψ)≤∑jpj∑i≤kλi↓(Vj†ρϕVj)=∑i≤kλi↓(ρϕ)\sum_{i\le k}\lambda_i^\downarrow(\rho_\psi)\le\sum_jp_j\sum_{i\le k}\lambda_i^\downarrow\big(V_j^\dagger\rho_\phi V_j\big)=\sum_{i\le k}\lambda_i^\downarrow(\rho_\phi)

    Ky Fan: the top-kk eigenvalue sum is convex, and unitary conjugation preserves spectra. Hence λψ≺λϕ\lambda_\psi\prec\lambda_\phi.

Derivation(⇐) Majorization gives a protocol
  1. λψ≺λϕ ⇒ ρψ=∑jpj Uj ρϕ Uj†\lambda_\psi\prec\lambda_\phi\ \Rightarrow\ \rho_\psi=\sum_jp_j\,U_j\,\rho_\phi\,U_j^\dagger

    The matrix form of majorization (in a common eigenbasis, permutation matrices suffice, by Birkhoff–von Neumann).

  2. Mj=pj ρϕ  Uj† ρψ−1/2M_j=\sqrt{p_j\,\rho_\phi}\;U_j^\dagger\,\rho_\psi^{-1/2}

    Define Alice's measurement on the support of ρψ\rho_\psi.

  3. ∑jMj†Mj=ρψ−1/2(∑jpj UjρϕUj†)ρψ−1/2=I\sum_jM_j^\dagger M_j=\rho_\psi^{-1/2}\Big(\sum_jp_j\,U_j\rho_\phi U_j^\dagger\Big)\rho_\psi^{-1/2}=\id

    It is a valid measurement.

  4. Mj ρψ Mj†=pj ρϕM_j\,\rho_\psi\,M_j^\dagger=p_j\,\rho_\phi

    Outcome jj occurs with probability pjp_j and leaves Alice's reduced state exactly equal to ρϕ\rho_\phi.

  5. The post-measurement state is pure and has the same reduced state on Alice's side as ∣ϕ⟩\ket\phi, so the two differ only by a unitary on Bob's side. Alice announces jj and Bob applies it. ■\blacksquare

Check your understanding

ψ\psi has Schmidt coefficients (0.4,0.4,0.2)(0.4,0.4,0.2) and ϕ\phi has (0.5,0.25,0.25)(0.5,0.25,0.25). Their entanglement entropies are H(ψ)≈1.52H(\psi)\approx1.52 and H(ϕ)=1.5H(\phi)=1.5. Which statement is true?

  1. ψ→ϕ\psi\to\phi deterministically, since the entropy decreases
  2. ϕ→ψ\phi\to\psi deterministically
  3. Neither direction is possible with certainty: the states are incomparable
  4. Both directions are possible
Show the answer

C. Neither direction is possible with certainty: the states are incomparable

Partial sums: ψ\psi gives 0.4, 0.80.4,\,0.8 and ϕ\phi gives 0.5, 0.750.5,\,0.75. The condition ψ≺ϕ\psi\prec\phi holds at k=1k=1 but fails at k=2k=2 (0.8>0.750.8>0.75); ϕ≺ψ\phi\prec\psi fails at k=1k=1 (0.5>0.40.5>0.4). A decrease of entropy is necessary, but far from sufficient.

Probabilistic conversions

The term l=1l=1 always equals 11. Since the total is fixed, λψ≺λϕ\lambda_\psi\prec\lambda_\phi is equivalent to El(ψ)≥El(ϕ)E_l(\psi)\ge E_l(\phi) for all ll, so P=1P=1 is exactly Nielsen's condition. Otherwise the bottleneck is the tail that ψ\psi cannot fill. The optimum is reached by a one-way protocol: Alice measures, Bob corrects.

Predict before you look

ψ\psi has Schmidt coefficients (0.6,0.3,0.1)(0.6,0.3,0.1). What is the maximal probability of converting it into the maximally entangled two-qutrit state (13,13,13)(\tfrac13,\tfrac13,\tfrac13)?

Show the answer

30 %

Tails of ψ\psi: 1, 0.4, 0.11,\,0.4,\,0.1; tails of the target: 1, 23, 131,\,\tfrac23,\,\tfrac13. The ratios are 1, 0.6, 0.31,\,0.6,\,0.3, so P=0.3P=0.3. The smallest Schmidt coefficient is the bottleneck.

SLOCC. If any nonzero success probability is acceptable (stochastic LOCC), ψ→ϕ\psi\to\phi is possible iff rank⁡(ψ)≥rank⁡(ϕ)\operatorname{rank}(\psi)\ge\operatorname{rank}(\phi) for the Schmidt ranks; Vidal's formula is positive exactly then. So bipartite pure states fall into SLOCC classes labelled by the Schmidt rank alone. Three qubits already behave differently: there are two inequivalent classes of genuinely tripartite entanglement, GHZ and W (Dür, Vidal & Cirac, 2000); see Multipartite Entanglement.

Catalysis, embezzlement and many copies

Incomparable pairs can sometimes be converted with help: a catalyst ∣χ⟩\ket\chi, borrowed and returned in exactly the same state.

Which conversions does exact catalysis allow ("trumping")? Turgut and Klimesh (2007) characterized it by an infinite family of inequalities between Rényi-type entropies, so the entanglement entropy alone still does not decide single-copy catalytic conversions. Two variations change the picture:

  • Embezzlement (van Dam & Hayden, 2003): the states ∣μn⟩∝∑j=1n1j∣j⟩∣j⟩\ket{\mu_n}\propto\sum_{j=1}^{n}\tfrac{1}{\sqrt j}\ket j\ket j satisfy ∣μn⟩→∣μn⟩⊗∣ϕ⟩\ket{\mu_n}\to\ket{\mu_n}\otimes\ket\phi by local unitaries alone, for any fixed ∣ϕ⟩\ket\phi, with error vanishing as n→∞n\to\infty. If a catalyst may be returned only approximately, any entangled state can be produced from nothing, so exactness is essential.
  • Correlated catalysis: if the catalyst may end up correlated with the system while its own state is returned exactly, recent work shows that the entanglement entropy alone decides approximate convertibility of pure states (Kondra, Datta & Streltsov, 2021).
DerivationMany copies: entanglement concentration in one picture
  1. (λ1∣00⟩+λ2∣11⟩)⊗n=∑k=0nλ1 n−kλ2 k∑∣s∣=k∣s⟩A∣s⟩B\big(\sqrt{\lambda_1}\ket{00}+\sqrt{\lambda_2}\ket{11}\big)^{\otimes n}=\sum_{k=0}^{n}\sqrt{\lambda_1^{\,n-k}\lambda_2^{\,k}}\sum_{\abs{s}=k}\ket{s}_A\ket{s}_B

    Expand and group the bit strings ss by their Hamming weight k=∣s∣k=\abs{s}.

  2. Alice measures k ⇒ (nk)−1/2∑∣s∣=k∣s⟩A∣s⟩B\text{Alice measures } k\ \Rightarrow\ \binom{n}{k}^{-1/2}\sum_{\abs{s}=k}\ket{s}_A\ket{s}_B

    Projecting onto weight kk is local. Each outcome leaves a maximally entangled state of Schmidt rank (nk)\binom nk, with probability (nk)λ1n−kλ2k\binom nk\lambda_1^{n-k}\lambda_2^{k}.

  3. log⁡2(nk)≈n h ⁣(kn)≈n h(λ2)=n E(ψ)\log_2\binom{n}{k}\approx n\,h\!\left(\tfrac kn\right)\approx n\,h(\lambda_2)=n\,E(\psi)

    With high probability k≈nλ2k\approx n\lambda_2, and Stirling's formula gives about nE(ψ)nE(\psi) ebits. A uniform state of rank RR converts into ⌊log⁡2R⌋\lfloor\log_2R\rfloor Bell pairs deterministically (Nielsen), losing less than one ebit.

  4. Dilution reverses the process with about nE(ψ)nE(\psi) Bell pairs and only O(n)\order{\sqrt n} bits of communication (Lo & Popescu). So asymptotically ψ⊗n→ϕ⊗m\psi^{\otimes n}\to\phi^{\otimes m} is possible iff m/n≤E(ψ)/E(ϕ)m/n\le E(\psi)/E(\phi): the d−1d-1 majorization inequalities collapse to a single entropy.

Key takeaways

  • Majorization has equivalent forms (partial sums, doubly stochastic maps, convex functions, unitary mixing); entropies are Schur-concave.
  • Nielsen: ∣ψ⟩→∣ϕ⟩\ket\psi\to\ket\phi deterministically by LOCC iff λψ≺λϕ\lambda_\psi\prec\lambda_\phi, proved via the Lo–Popescu one-way reduction, polar decomposition and Ky Fan.
  • Vidal: Pmax⁡(ψ→ϕ)=min⁡lEl(ψ)/El(ϕ)P_{\max}(\psi\to\phi)=\min_lE_l(\psi)/E_l(\phi) with tail sums ElE_l; SLOCC convertibility is decided by the Schmidt rank.
  • Incomparable states exist; exact catalysts can unlock conversions, while embezzlement shows that inexact catalysis trivializes the theory.
  • Asymptotically the d−1d-1 inequalities collapse to one: the conversion rate is E(ψ)/E(ϕ)E(\psi)/E(\phi).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

λψ=(0.5,0.3,0.2)\lambda_\psi=(0.5,0.3,0.2) and λϕ=(0.6,0.2,0.2)\lambda_\phi=(0.6,0.2,0.2). Which deterministic LOCC conversions are possible?

  1. ψ→ϕ\psi\to\phi only
  2. ϕ→ψ\phi\to\psi only
  3. Both
  4. Neither
Show the answer

A. ψ→ϕ\psi\to\phi only

Partial sums 0.5≤0.60.5\le0.6 and 0.8≤0.80.8\le0.8 give λψ≺λϕ\lambda_\psi\prec\lambda_\phi, so ψ→ϕ\psi\to\phi. The reverse fails at k=1k=1 (0.6>0.50.6>0.5).

Question 2

What is the maximal probability of converting 0.7 ∣00⟩+0.3 ∣11⟩\sqrt{0.7}\,\ket{00}+\sqrt{0.3}\,\ket{11} into ∣Φ+⟩\ket{\Phi^+}?

  1. 0.30.3
  2. 0.60.6
  3. 0.70.7
  4. 0.880.88
Show the answer

B. 0.60.6

Vidal: min⁡(1,0.30.5)=0.6\min\big(1,\tfrac{0.3}{0.5}\big)=0.6. Equivalently, Alice's filter reduces the ∣00⟩\ket{00} amplitude to match the ∣11⟩\ket{11} amplitude, succeeding with probability 2×0.32\times0.3.

Question 3

What does the Jonathan–Plenio example demonstrate?

  1. Entanglement entropy decides single-copy conversions
  2. Catalysts must be maximally entangled
  3. With a catalyst, LOCC can increase the Schmidt rank
  4. A borrowed entangled state, returned exactly, can enable a deterministic conversion that is otherwise impossible
Show the answer

D. A borrowed entangled state, returned exactly, can enable a deterministic conversion that is otherwise impossible

ψ⊀ϕ\psi\not\prec\phi, yet ψ⊗χ≺ϕ⊗χ\psi\otimes\chi\prec\phi\otimes\chi with χ=(0.6,0.4)\chi=(0.6,0.4). The catalyst is not consumed.

Question 4

In the proof of (⇒), which fact turns ρψ=∑jpjVj†ρϕVj\rho_\psi=\sum_jp_jV_j^\dagger\rho_\phi V_j into λψ≺λϕ\lambda_\psi\prec\lambda_\phi?

  1. The Cauchy–Schwarz inequality
  2. Hölder's inequality for Schatten norms
  3. Ky Fan's principle: the sum of the kk largest eigenvalues is convex
  4. The Holevo bound
Show the answer

C. Ky Fan's principle: the sum of the kk largest eigenvalues is convex

Applying Ky Fan to the convex combination bounds each top-kk eigenvalue sum of ρψ\rho_\psi by the average of those of the unitary conjugates of ρϕ\rho_\phi, all equal to that of ρϕ\rho_\phi.

Further reading

  • M. A. Nielsen, "Conditions for a class of entanglement transformations", Phys. Rev. Lett. 83, 436 (1999).
  • G. Vidal, "Entanglement of pure states for a single copy", Phys. Rev. Lett. 83, 1046 (1999).
  • D. Jonathan & M. B. Plenio, "Entanglement-assisted local manipulation of pure quantum states", Phys. Rev. Lett. 83, 3566 (1999).
  • H.-K. Lo & S. Popescu, "Concentrating entanglement by local actions: Beyond mean values", Phys. Rev. A 63, 022301 (2001).
  • M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §12.5 (Cambridge, 10th anniv. ed., 2010).