Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Entangled vectors and the three explicit random purification maps

Definition
RandomDimReduction_Channel_Supplement_Purification

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationrepresentation-theory

For a finite orthonormal basis AAA, let ∣ΓA⟩=∑i∣i,i⟩|\Gamma_A\rangle=\sum_i|i,i\rangle∣ΓA​⟩=∑i​∣i,i⟩, without normalization. A purification ϕ\phiϕ of ρ\rhoρ is a unit vector on A⊗BA\otimes BA⊗B whose partial trace over BBB is ρ\rhoρ. The canonical regrouping sends ((at,bt))t=1n((a_t,b_t))_{t=1}^n((at​,bt​))t=1n​ to ((at)t,(bt)t)((a_t)_t,(b_t)_t)((at​)t​,(bt​)t​), and reindexes tensor operators accordingly.

For an operator map NNN, its reference-first Choi matrix has blocks N(∣i⟩⟨j∣)N(|i\rangle\langle j|)N(∣i⟩⟨j∣). With the published reduction map RRR, not RTPR^{TP}RTP, put

JR=(id⊗R)(∣Γ⟩⟨Γ∣),P(X)=JR(X⊗I).J_R=(\mathrm{id}\otimes R)(|\Gamma\rangle\langle\Gamma|),\qquad P(X)=J_R(X\otimes I).JR​=(id⊗R)(∣Γ⟩⟨Γ∣),P(X)=JR​(X⊗I).

Let TSn(X)=1n!∑πFπXFπ†T_{S_n}(X)=\frac1{n!}\sum_\pi F_\pi XF_\pi^\daggerTSn​​(X)=n!1​∑π​Fπ​XFπ†​. The other two explicit maps are

PCP(X)=P(TSn(X)),PCPTP(X)=PCP(X)+tr⁡(QX)kndnI,P^{CP}(X)=P(T_{S_n}(X)),\qquad P^{CPTP}(X)=P^{CP}(X)+\frac{\operatorname{tr}(QX)}{k^nd^n}I,PCP(X)=P(TSn​​(X)),PCPTP(X)=PCP(X)+kndntr(QX)​I,

where QQQ is the published kernel projector. No positivity, normalization or purification guarantee is imposed by these definitions. The target average independently conjugates a fixed purification by I⊗VI\otimes VI⊗V, takes its nnn-fold tensor power and regroups the registers, then integrates over normalized Haar V∈U(k)V\in U(k)V∈U(k).

These definitions implement Eqs. (4)–(6) literally and supply the registers for Lemma 2.1 and Theorem 3.1.

Definition code
import Definitions.Def_RandomDimReduction_Channel_Moment

set_option autoImplicit false
noncomputable section
open Matrix MeasureTheory
open scoped Kronecker Matrix ComplexConjugate Matrix.Norms.Elementwise

namespace RandomDimReduction.Channel.Supplement
attribute [local instance] Classical.propDecidable Classical.decEq

/-- Unnormalized maximally entangled vector, §2.1, p.5. -/
def gamma (a : Type) [DecidableEq a] : a × a → ℂ :=
  fun ij => if ij.1 = ij.2 then 1 else 0

/-- The canonical regrouping (A ⊗ B)^n ≃ A^n ⊗ B^n. -/
def regroup {a b : Type} (n : ℕ) :
    (Fin n → a × b) ≃ ((Fin n → a) × (Fin n → b)) where
  toFun x := (fun t => (x t).1, fun t => (x t).2)
  invFun x := fun t => (x.1 t, x.2 t)
  left_inv _ := rfl
  right_inv _ := rfl

/-- Reindex an operator into the grouped tensor registers. -/
def groupOperator {a b : Type} (n : ℕ) (X : Op (Fin n → a × b)) :
    Op ((Fin n → a) × (Fin n → b)) :=
  fun i j => X ((regroup n).symm i) ((regroup n).symm j)

/-- Unnormalized reference-first Choi operator; §2.1, p.6. -/
def choi {a b : Type} [DecidableEq a] (N : Op a → Op b) : Op (a × b) :=
  fun i j => N (Matrix.single i.1 j.1 1) i.2 j.2

/-- Eq.(4): ordinary left multiplication, with neither transpose nor sandwich. -/
def purification (n k d : ℕ) (X : Op (Word n d)) : Op (Word n d × Word n k) :=
  choi (reduction n k d) * (X ⊗ₖ (1 : Op (Word n k)))

/-- The permutation twirl of §3.1, p.8. -/
def permutationTwirl (n d : ℕ) (X : Op (Word n d)) : Op (Word n d) :=
  ((Nat.factorial n : ℂ)⁻¹) • ∑ p : Equiv.Perm (Fin n),
    MixedCloning.Optimal.permMatrix n p * X * (MixedCloning.Optimal.permMatrix n p)ᴴ

/-- P^CP = P ∘ T_Sn, defined on the full operator algebra. -/
def purificationCP (n k d : ℕ) (X : Op (Word n d)) : Op (Word n d × Word n k) :=
  purification n k d (permutationTwirl n d X)

/-- Eq.(5), with the full output dimension k^n d^n in the denominator. -/
def purificationCPTP (n k d : ℕ) (X : Op (Word n d)) : Op (Word n d × Word n k) :=
  purificationCP n k d X +
    ((kernelProjector n k d * X).trace / ((k ^ n * d ^ n : ℕ) : ℂ)) • 1

/-- A unit vector with the specified data marginal, without selecting a purification. -/
def IsPurification {d k : ℕ} (rho : Op (Fin d))
    (phi : EuclideanSpace ℂ (Fin d × Fin k)) : Prop :=
  ‖phi‖ = 1 ∧ WildeQIT.partialTraceRight (MixedCloning.Optimal.pure phi) = rho

/-- One Haar unitary on the purifying register, shared across all n copies; Eq.(6). -/
def randomPurificationAverage {d k : ℕ} (n : ℕ)
    (phi : EuclideanSpace ℂ (Fin d × Fin k)) : Op (Word n d × Word n k) :=
  ∫ V : Matrix.unitaryGroup (Fin k) ℂ,
    groupOperator n (tensor n
      (((1 : Op (Fin d)) ⊗ₖ (V : Op (Fin k))) *
        MixedCloning.Optimal.pure phi *
        (((1 : Op (Fin d)) ⊗ₖ (V : Op (Fin k))))ᴴ))
    ∂MixedCloning.Optimal.haar k

end RandomDimReduction.Channel.Supplement
Source
Angus Lowe, Xinyu Tan, Random dimension reduction and learning symmetric properties of quantum states, STOC 2027 submission #994 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/994.pdf, §2.1, pp.5–6; §3.1, pp.8–10, Eqs. (4)–(6)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me