Majorization
a tool developed to study disorder
References
/-- r reachable from s by randomly permuting components then averaging over permutations -/
def majorizes (s r : ℝᵈ) :=
∃ (set of d-dim permutation matrices P) (p : rnd_var),
r = ∑ j, (p j) * (P j) * s
notation r `≺` s := majorizes s r
/-- uniform distribution on d elements is at least as disordered as any other prob dist over d elements -/
example (s : rnd_var) : (1/d,...,1/d) ≺ s
-- the uniform distribution (1/d, ..., 1/d) reachable by averaging over permutations Pπs of s,
-- where π is chosen uniformly at random from the symmetric group on d elements.
/-- vector whose components are the eigenvalues of R, arranged in decreasing order -/
def eigenvalues_descending (R : d-dim Hermitian op) := sorry
notation `λ` := eigenvalues_descending
def majorize (S R : d-dim Hermitian op) :=
λ(R) ≺ λ(S)
notation R `≺` S := majorizes S R
lemma Horns (r s : vectors) :
r ≺ s ↔ ∃ (complex_unitary u), rᵢ = ∑ j, |uᵢⱼ|² sⱼ
theorem Uhlmanns (R S : Hermitian_op) :
R ≺ S ↔ ∃ (unitary U) [rnd_var p], R = ∑ j, pⱼ Uⱼ S Uⱼ†
unitarity is fundamental in quantum mechanics. so Horn’s lemma and Uhlmann’s theorem arise frequently.
can Convert quantum state ψ into φ by LOCC?
iff ρAψ ≺ ρAφ.
where does this condition come from?
Any LOCC on pure states can implemented by single local measurement on one part of bipartite system
followed by an outcome-dependent unitary op on the other part.
In addition, local unitary ops are known to be irrelevant as far as the entanglement properties of the final state are concerned.
We are therefore left with a single local measurement as the only element potentially responsible for the condition.
So it is natural to investigate the role of majorization in quantum measurements.
why not just use Shannon entropy and Quantum entropy?
entropies are weaker than majorization.
Shannon entropy and Quantum entropy quantify order in some limiting conditions: when many copies of a system are considered.
can be derived from majorization in the law of large numbers limit/asymptotic/many copies converted to many copies.
Majorization gives more information than any Schur-convex function.
theorem majorizes_iff_reachable_by_doubly_stochastic_matrix :
∃ [doubly_stochastic D], r ≺ s ↔ r = Ds
Birkhoff’s theorem: the set of dxd doubly stochastic matrices is a convex set whose extreme points are the permutation matrices.
the notion of majorization can be extended to hermitian ops by focussing on the eigenvalues of R and S.
R ≺ S means that λ R ≺ λ S. Then Uhlmann’s theorem says
theorem Uhlmann :
A ≺ B ↔ ∃ (unitaries Uᵢ) (rnd_var pᵢ), A = ∑ i, pᵢ Uᵢ B Uᵢ†
this theorem illustrates the idea A is more random than B:
A is reachable by unitary mixing: independently applying unitary operations {Uᵢ} and mixing the resulting ops Uᵢ B Uᵢ† according to probs pᵢ.
/-- the sum of the k largest eigenvalues of A is the maximum value of tr(A P),
where the maximum is taken over all k-dim projectors P -/
theorem Ky_Fan (Hermitian A) :
∑ j, λⱼ(A) = max_P tr(A P)
-- elementary consequence of Horn's lemma
-- from Ky_Fan
example (A B : Hermitian) :
λ(A + B) ≺ λ(A) + λ(B)
begin
-- choose k-dim projector P
-- s.t. ∑ j, λⱼ(A + B) = tr((A + B)P) = tr(AP) + tr(BP) ≤ ∑ j, λⱼ(A) + ∑ j, λⱼ(B).
end
/- if one rnd_var is more disordered in the sense of majorization, then also according to Shannon entropy -/
lemma Shannon_entropy_gt_of_majorizes (x y : ι → ℝ) [rnd_var x] [rnd_var y] :
x ≺ y → - Shannon_entropy x < - Shannon_entropy y
More generally:
def F (f : ℝ → ℝ) (x : ι → ℝ) := ∑ i, f(x i)
theorem _of_majorizes (x y : ι → ℝ) [rnd_var x] [rnd_var y] {f : ℝ → ℝ} [convex f] :
x ≺ y → F(x) < F(y)
theorem _of_majorizes_op [ρ σ : Hermitian op]
ρ ≺ σ → F(λ(ρ)) ≤ F(λ(σ))
begin
-- ∃ (unitaries Uᵢ) (rnd_var pᵢ), ρ = ∑ i, pᵢ Uᵢ σ Uᵢ†
-- And F is a sum of convex functions and thus convex,
-- so F(ρ) ≤ ∑ i, pᵢ F(Uᵢ σ Uᵢ†).
-- But F is manifestly unitarily invariant, so F(Uᵢ σ Uᵢ†) = F(σ), and thus F(ρ) ≤ ∑ i, pᵢ F(σ) = F(σ).
end
lemma quantum_entropy_eq_Shannon_entropy_of_eigenvalues :
quantum_entropy ρ = Shannon_entropy λ(ρ)
/- if one density op is more disordered in the sense of majorization, then also according to vN entropy -/
theorem quantum_entropy_gt_of_majorizes :
ρ ≺ σ → - quantum_entropy ρ < - quantum_entropy σ
-- there are many other functions that also preserve the majorization relation.
-- Schur-convex function.
The mixing problem in quantum mechanics: given ρ, for what pⱼ and ρⱼ does ρ = ∑ j, pⱼ ρⱼ?
efficient measurement: all information about outcomes is kept.
such a measurement is characterized a single set of ops {Fᵢ} satisfying ∑ i, Fᵢ† Fᵢ = 1.
takes ρ to ρ'ᵢ := (Fᵢ† ρ Fᵢ)/pᵢ with prob pᵢ := tr Fᵢ† Fᵢ ρ.
example : λ(ρ) ≺ ∑ j, pⱼ λ(ρ'ᵢ)
begin
-- suppose the measurement is done on part A of bipartite system in a pure state |ψ⟩ s.t. ρ = ρA := trB |ψ⟩⟨ψ|.
-- The resulting states are |ψᵢ⟩ := Fᵢ ⊗ 1B |ψ⟩ / √{pᵢ} with ρ'ᵢ = trB |ψᵢ⟩⟨ψᵢ|. Define ρBᵢ := trA |ψᵢ⟩⟨ψᵢ|.
-- if no faster that light signaling from A to B then
-- ρB = trA |ψ⟩⟨ψ| = trA(∑ i, Fᵢ†Fᵢ ⊗ 1B |ψ⟩⟨ψ|) = ∑ i, pᵢ ρBᵢ
-- from the theorm on mixing λ(ρB) ≺ ∑ i, pᵢ λ(ρBᵢ)
-- equaivalent to the theorem above b/c for any bipartite pure state, the reduced density matrice ρA and ρB have equivalent spectra λ(ρA) = λ(ρB);
end
-- a quantum measurement acquires rather than loses information about the measured system.
-- the eigenvalues of the initial system are more disordered than the average eigenvalues of the post-measurement state.
“majorization describes ability of quantum measurements to acquire information about quantum system.”
the entanglement of a bipartite state is related to how mixed the corresponding reduced density matrices are. In order to modify their spectra we need to make effcient local measurements.
Do the constraints regulating information acquisition in effcient measurements rule bipartite pure state entanglement manipulation?
theorem theorem13 : suppose ρ is a density matrix with vector of eigenvalues λ. and σᵢ are density matrices with vectors of eigenvalues λᵢ. suppose pᵢ are probs s.t. λ ≺ ∑ i, pᵢ λᵢ.
then exists matrices {Eᵢⱼ} and prob dist pᵢⱼ s.t. ∑ ij, Eᵢⱼ† Eᵢⱼ = 1, Eᵢⱼ† ρ Eᵢⱼ = pᵢⱼ σᵢ, ∑ j, pᵢⱼ = pᵢ.
begin
-- by Birkhoff theorem, λ ≺ ∑ i, pᵢ λᵢ implies that exists permutation matrices Pⱼ and probs qⱼ s.t. λ = ∑ i j, pᵢ qⱼ Pⱼ λᵢ.
-- wlog we assume that ρ and σᵢ are all diagonal in the same basis, with nonincreasing diagonal entries,
-- since if this is not the case then we can append unitary matrices to the measurement matrices to obtain the correct transformation.
-- With this convention, we define matrices Eᵢⱼ by
-- Eᵢⱼ √ρ := √{pᵢqⱼ} √{σᵢ} Pⱼ†
-- For simplicity we assume ρ is invertible.
-- Then √ρ Eᵢⱼ Eᵢⱼ √ρ = ∑ i j, pᵢ qⱼ Pⱼ σᵢ Pⱼ†
-- comparing with prev eq we see that RHS is just ρ and thus √ρ (∑ i j, Eᵢⱼ† Eᵢⱼ) √ρ = ρ.
-- From this we deduce that Eᵢⱼ† ρ Eᵢⱼ = pᵢ qⱼ σᵢ
-- so after a measurement {Eᵢⱼ} the result (i,j) has prob pᵢⱼ pᵢ qⱼ, ∑ j, pᵢⱼ = pᵢ and the post measurement state is σᵢ.
end
-- Schur-Horn theorem: for any d×d Hermitian matrix its vector of eigenvalues λ majorizes the vector of diagonal elements in every orthonormal basis.
-- Conversely, every vector that is majorized by λ may be obtained as the diagonal elements in a suitable orthonormal basis.
-- In particular if p and p' denote the ordered vectors of eigenvalues of two density matrices ρ and ρ', respectively, then ρ ≽ ρ' iff p ≽ p'.
variables [quantum_state ρ ρ']
notation ρ `≽` ρ' := majorizes ρ ρ'
/-- Lemma 4 in https://arxiv.org/abs/2012.05573 -/
lemma typicality_and_majorization [H(ρ) < H(ρ')] {ε > 0} :
∃ (n : ℕ) [quantum_state ρ'εn],
ρ^⊗n ≽ ρ'εn ∧ D(ρ'^⊗n, ρ'εn) ≤ ε
Pure-state transformations under local operations and classical communication
characterization of the states Alice and Bob can take the system into, starting from a given pure state and by means of LOCC.
Let λ(ψ) = λ(ρAψ) denote the vector of decreasingly ordered eigenvalues λi of the reduced density matrix ρAψ, or equivalently, of the Schmidt coefficients of ψ, |ψ⟩ = ∑ i..d, √λᵢ |iA⟩|iB⟩ , a state of two d-level systems.
/-- Theorem 14 -/
theorem convert_pure :
(ψ convertable to φ by LOCCs) ↔ λ ψ ≺ λ φ := sorry
/-- Theorem 15 -/
theorem convert_pure_prob :
(ψ convertable to φ by LOCCs with prob p) ↔ λ ψ ≺ʷ p * λ φ := sorry
/-- Theorem 16 -/
theorem convert_to_ensemble :
ψ convertable to {pj, ψ j} by LOCCs) ↔ λ ψ ≺ ∑ j, pⱼ λ ψⱼ := sorry
remarkable: feasibility of pure-state transformation under LOCC depends only on d inequalities.
Notice: the set of protocols based on LOCC is of very difficult characterization. a local protocol may consist of arbitrarily many rounds of communication and local operations.
the most general LOCC protocol involving only pure states can be replaced with a simple protocol: efficient measurement on A and local unitaries on B.
can do transformation with LOCC?
iff exists efficient measurement on A that transforms the Schmidt coefficients λ ψ of the initial state ψ into those of the final states ψⱼ (recall that a local unitary operation on B cannot modify the Schmidt coefficients of the final states).
iff a measurement can transform the mixed state ρAψ, with spectrum λ ψ, into the ensemble {pⱼ, ρAψⱼ}, with corresponding spectra λ ψⱼ.
Then theorem 12 implies that condition (32) must be fulfilled for such a measurement on A to exists. And theorem 13, ensures that when condition (32) is fulfilled, then the wished measurement exists.
The degree of entanglement of a bipartite pure state is directly related to the degree of disorder of the corresponding reduced density matrix ρAψ.
A pure state transformation through LOCC of a bipartite system AB is possible iff implies an increase in the order of part A (equivalently, of part B).
/-- exists pure states whose entanglement is incomparable -/
theorem incomparable_entanglement :
∃ pure states ψ and φ,
(transformation ψ → φ cannot be accomplished by LOCC) ∧ (transformation φ → ψ cannot be accomplished by LOCC) := sorry
example : ψ and φ with Schmidt coefficients λ ψ = (0.5, 0.25, 0.25) and λ φ = (0.4, 0.4, 0.2).
theorem entanglement_catalysis :
∃ [pure states ψ and φ] [transformation ψ → φ cannot be accomplished],
∃ catalyzing state τ, ψ⊗τ → φ⊗τ can be accomplished := sorry
the proof of theorem 13 gives an explicit measurement on part A and outcome-dependent unitaries on part B to readily obtain a local protocol for the transformation ψ → {pj, ψⱼ}
proof of theorem 13 gives a protocol to transform bipartite pure states.
This first construction:
If a deterministic conversion ψ → φ is possible by means of LOCC, then λ ψ ≺ λ φ. theorem 1 implies λ ψ = D λ φ for some doubly stochastic matrix D.
In turn, Birkho theorem says that D decomposes into n random permutations, D = Pj pj Pj, and Caratheodory’s theorem ensures that a decomposition exists with n = d^2 - 2d + 2.
The measurement operators {Fj}, given by Fⱼ := qⱼ^{1/2} (ρAφ)^{1/2} Pⱼ†(ρAψ)^{-1/2} , define then an outcome measurement for Alice that, when supplemented with extra, outcome-dependent local unitary operations, deterministically transforms ψ into φ.
This protocol requires sending about 2 log2 d bits from Bob to Alice, corresponding to communicating which of the n measurement outcomes Alice has obtained.
theorem asymptotic_transformations :
in the limit of large N, ψ^⊗N can be converted into φ^⊗M with arbitrarily high fidelity ↔ N * S(ρAψ) ≥ M * S(ρAφ) := sorry
-- all inequalities in theorem 14 collapse into a single inequality
/-
Expand ψ^⊗N and φ^⊗M in their Schmidt decompositions.
For large N and M most of the majorization inequalities of Eqs. (6) become very sensitive to perturbations of the Schmidt coefficients of φ^⊗M.
A "small" modication of the latter is sufficient for the inequalities to be fulfilled, even if they were not fulfilled initially.
Only those inequalities setting conditions similar to Eq. (42) turn out to be robust against such modifications.
So only condition (42) matters for large N, where (asymptotically perfect) approximations to φ^⊗M are accepted as the output of the transformation.
-/