Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2: postselecting symmetric densities

Open
QAlgorithms.Papers.Independent.Support50.P22.symmetricPostselection

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let d=dim⁡H≥1d=\dim H\ge1d=dimH≥1, K≅HK\cong HK≅H, and n≥0n\ge0n≥0. Let τHnKn\tau_{H^nK^n}τHnKn​ be the Haar average of σHK⊗n\sigma_{HK}^{\otimes n}σHK⊗n​ over normalized pure states on H⊗KH\otimes KH⊗K, with paired copies regrouped into Hn⊗KnH^n\otimes K^nHn⊗Kn. Fix a normalized purification ψHnKnN\psi_{H^nK^nN}ψHnKnN​ of this average. For every density matrix ρ\rhoρ whose range lies in Sym⁡n(H⊗K)\operatorname{Sym}^n(H\otimes K)Symn(H⊗K), there exists an effect 0⪯M⪯IN0\preceq M\preceq I_N0⪯M⪯IN​ such that, writing TM(X)=Tr⁡(XM)T_M(X)=\operatorname{Tr}(XM)TM​(X)=Tr(XM),

ρ=(n+d2−1n) (id⁡HnKn⊗TM)(∣ψ⟩⟨ψ∣).\rho=\binom{n+d^2-1}{n}\,(\operatorname{id}_{H^nK^n}\otimes T_M)(|\psi\rangle\langle\psi|).ρ=(nn+d2−1​)(idHnKn​⊗TM​)(∣ψ⟩⟨ψ∣).

Here TMT_MTM​ is a complex-linear completely positive, trace-nonincreasing functional with scalar codomain C\mathbb CC. The effect may depend on ρ\rhoρ, whereas the reference purification is fixed beforehand. This is the postselection interface for all densities supported on the symmetric vector subspace.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P22
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.L2Operator

open MeasureTheory

namespace QAlgorithms.Papers.Independent.Support50.P22

attribute [local instance] Classical.decEq Classical.propDecidable

open QAlgorithms.Papers.Independent.Gap48.P20 (Copies)

open QAlgorithms.Papers.Independent.Information100.P69 (diamond)

open QAlgorithms.Papers.Independent.Dependency50.P18 (ClassicalOutput)

attribute [local instance] QAlgorithms.Papers.Independent.Support50.P22.postselectionMatrixMeasurableSpace

attribute [local instance] QAlgorithms.Papers.Independent.Support50.P22.postselectionMatrixBorelSpace

/-- Lemma 2, PDF p.2. The purification is fixed before the target density.
An existential effect gives the source's complex-linear trace-nonincreasing
scalar CP operation T(X)=Tr(XM); the target equality is a conclusion. -/
theorem symmetricPostselection (n d : ℕ) (hd : 0 < d)
    {N : Type*} [Fintype N] [DecidableEq N] [Nonempty N]
    (psi : EuclideanSpace ℂ ((Copies (Fin d) n × Copies (Fin d) n) × N))
    (hpsi : FinitePurification psi (tauPair n d hd))
    (rho : Matrix (Copies (Fin d) n × Copies (Fin d) n) (Copies (Fin d) n × Copies (Fin d) n) ℂ)
    (hrho : IsDensityMatrix rho) (hsupp : RangeSupported rho (pairedSymmetricSpace n d)) :
    ∃ M : Matrix N N ℂ, IsEffect M ∧
      rho = (factor n d : ℂ) • postselect M (pureDensity psi) := by sorry

end QAlgorithms.Papers.Independent.Support50.P22

end
Source
Post-selection technique for quantum channels with applications to quantum cryptography, arXiv:0809.3019v1, PDF p. 2, Lemma 2: postselecting a symmetric density operator
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every n,d∈Nn,d\in\mathbb Nn,d∈N with d>0d>0d>0, put H={0,…,d−1}nH=\{0,\ldots,d-1\}^nH={0,…,d−1}n and let NNN be a finite nonempty type with decidable equality. Define τ\tauτ on H×HH\times HH×H by averaging the matrices with entries ∏ivxi,yivxi′,yi′‾\prod_i v_{x_i,y_i}\overline{v_{x'_i,y'_i}}∏i​vxi​,yi​​vxi′​,yi′​​​, where vvv is the reshaping, using the standard finite-index bijection, of Ue0Ue_0Ue0​ for a Haar-distributed unitary UUU in dimension d2d^2d2. Suppose ψ∈C(H×H)×N\psi\in\mathbb C^{(H\times H)\times N}ψ∈C(H×H)×N has norm 111 and satisfies ∑u∈Nψa,uψb,u‾=τa,b\sum_{u\in N}\psi_{a,u}\overline{\psi_{b,u}}=\tau_{a,b}∑u∈N​ψa,u​ψb,u​​=τa,b​. Let ρ\rhoρ be a positive semidefinite matrix on H×HH\times HH×H with trace 111, and suppose ρw\rho wρw belongs, for every vector www, to the subspace fixed by every simultaneous permutation of the positions in the two copies of HHH; explicitly, these permutation matrices have entries 111 exactly when x=x′∘π−1x=x'\circ\pi^{-1}x=x′∘π−1 and y=y′∘π−1y=y'\circ\pi^{-1}y=y′∘π−1, and 000 otherwise. Then there exists a matrix MMM on NNN such that both MMM and I−MI-MI−M are positive semidefinite and, writing g=(n+d2−1n)g=\binom{n+d^2-1}{n}g=(nn+d2−1​),

ρa,b=g∑u∈N∑v∈Nψa,uψb,v‾Mv,u(a,b∈H×H).\rho_{a,b} = g\sum_{u\in N}\sum_{v\in N} \psi_{a,u}\overline{\psi_{b,v}}M_{v,u} \qquad(a,b\in H\times H).ρa,b​=gu∈N∑​v∈N∑​ψa,u​ψb,v​​Mv,u​(a,b∈H×H).

The statement includes n=0n=0n=0 and d=1d=1d=1, when HHH is a singleton and g=1g=1g=1.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 2026

    Confirmed by the mission captain (proposal self-audit).

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