Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: postselection bound

Open
QAlgorithms.Papers.Independent.Support50.P22.postselection

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

prove2quantum

Let HHH have positive dimension ddd, let n≥0n\ge0n≥0, and set

gn,d=(n+d2−1n).g_{n,d}=\binom{n+d^2-1}{n}.gn,d​=(nn+d2−1​).

Let τHn=∫σH⊗n dμ(σH)\tau_{H^n}=\int\sigma_H^{\otimes n}\,d\mu(\sigma_H)τHn​=∫σH⊗n​dμ(σH​), where μ\muμ is the Hilbert–Schmidt induced probability law obtained by reducing a Haar pure state on H⊗KH\otimes KH⊗K, with K≅HK\cong HK≅H. Fix any normalized purification ψHnR\psi_{H^nR}ψHnR​ of this state before choosing the map. Let Δ:End⁡(H⊗n)→End⁡(B)\Delta:\operatorname{End}(H^{\otimes n})\to\operatorname{End}(B)Δ:End(H⊗n)→End(B) be complex-linear, with arbitrary finite nonzero output space BBB. Suppose that for every tensor-factor permutation π\piπ there is a CPTP output map KπK_\piKπ​ such that Δ∘Ad⁡(Pπ)=Kπ∘Δ\Delta\circ\operatorname{Ad}(P_\pi)=K_\pi\circ\DeltaΔ∘Ad(Pπ​)=Kπ​∘Δ. Then

∥Δ∥⋄≤gn,d ∥(Δ⊗id⁡R)(∣ψ⟩⟨ψ∣)∥1,gn,d≤(n+1)d2−1.\|\Delta\|_\diamond\le g_{n,d}\,\|(\Delta\otimes\operatorname{id}_R)(|\psi\rangle\langle\psi|)\|_1, \qquad g_{n,d}\le(n+1)^{d^2-1}.∥Δ∥⋄​≤gn,d​∥(Δ⊗idR​)(∣ψ⟩⟨ψ∣)∥1​,gn,d​≤(n+1)d2−1.

The trace norm has no factor 1/21/21/2, and the diamond norm ranges over all complex matrices. This reduces the norm bound to a single fixed purified input.

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

/-- Theorem 1, PDF p.2; tensor convention in footnote 10 on p.4.
Delta remains arbitrary complex-linear, with arbitrary finite output.
The fixed test purification is quantified before Delta. The source's
state-maximization assertion for arbitrary maps is not used as a definition. -/
theorem postselection (n d : ℕ) (hd : 0 < d)
    {R B : Type*} [Fintype R] [DecidableEq R] [Nonempty R]
    [Fintype B] [DecidableEq B] [Nonempty B]
    (psi : EuclideanSpace ℂ (Copies (Fin d) n × R)) (hpsi : FinitePurification psi (deFinettiState n d hd))
    (Delta : Matrix (Copies (Fin d) n) (Copies (Fin d) n) ℂ →ₗ[ℂ] Matrix B B ℂ)
    (hcov : ∀ pi : Equiv.Perm (Fin n), ∃ K : Superop B B, IsChannel K ∧
      ∀ X, Delta (permuteInput pi X) = K (Delta X)) :
    diamond Delta ≤ (factor n d : ℝ) * traceNorm (tensorId Delta (pureDensity psi)) ∧
      factor n d ≤ (n+1) ^ (d^2-1) := 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, Theorem 1: Post-Selection Theorem (seed paper result)
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, let H={0,…,d−1}nH=\{0,\ldots,d-1\}^nH={0,…,d−1}n, and let R,BR,BR,B be finite nonempty types with decidable equality. Define Ω=∫ρ⊗n dμd(ρ)\Omega=\int\rho^{\otimes n}\,d\mu_d(\rho)Ω=∫ρ⊗ndμd​(ρ), where (ρ⊗n)x,y=∏iρxi,yi(\rho^{\otimes n})_{x,y}=\prod_i\rho_{x_i,y_i}(ρ⊗n)x,y​=∏i​ρxi​,yi​​ and μd\mu_dμd​ is obtained by taking Ue0Ue_0Ue0​ for a Haar-distributed unitary in dimension d2d^2d2, reshaping this vector as v∈Cd×dv\in\mathbb C^{d\times d}v∈Cd×d using the standard finite-index bijection, and forming ρa,a′=∑bva,bva′,b‾\rho_{a,a'}=\sum_bv_{a,b}\overline{v_{a',b}}ρa,a′​=∑b​va,b​va′,b​​. Suppose ψ∈CH×R\psi\in\mathbb C^{H\times R}ψ∈CH×R satisfies ∥ψ∥=1\|\psi\|=1∥ψ∥=1 and ∑r∈Rψx,rψy,r‾=Ωx,y\sum_{r\in R}\psi_{x,r}\overline{\psi_{y,r}}=\Omega_{x,y}∑r∈R​ψx,r​ψy,r​​=Ωx,y​. Let Δ\DeltaΔ be any complex-linear map from complex matrices on HHH to complex matrices on BBB. Assume that for every permutation π\piπ of the nnn positions there is a map KKK on matrices on BBB admitting a finite Kraus representation K(Y)=∑jVjYVj∗K(Y)=\sum_jV_jYV_j^*K(Y)=∑j​Vj​YVj∗​ with ∑jVj∗Vj=I\sum_jV_j^*V_j=I∑j​Vj∗​Vj​=I, such that, for every matrix XXX on HHH, Δ(Xπ)=K(Δ(X))\Delta(X^\pi)=K(\Delta(X))Δ(Xπ)=K(Δ(X)), where Xx,yπ=Xx∘π,y∘πX^\pi_{x,y}=X_{x\circ\pi,y\circ\pi}Xx,yπ​=Xx∘π,y∘π​. Then, with g=(n+d2−1n)g=\binom{n+d^2-1}{n}g=(nn+d2−1​),

∥Δ∥⋄≤g ∥(Δ⊗id⁡R)(ψψ∗)∥1,g≤(n+1)d2−1.\|\Delta\|_\diamond \le g\,\|(\Delta\otimes\operatorname{id}_R)(\psi\psi^*)\|_1, \qquad g\le(n+1)^{d^2-1}.∥Δ∥⋄​≤g∥(Δ⊗idR​)(ψψ∗)∥1​,g≤(n+1)d2−1.

Here ∥Y∥1=Re⁡tr⁡Y∗Y\|Y\|_1=\operatorname{Re}\operatorname{tr}\sqrt{Y^*Y}∥Y∥1​=RetrY∗Y​, with the square root defined by continuous functional calculus; the diamond quantity is exactly sup⁡∥Z∥1≤1∥(id⁡H⊗Δ)(Z)∥1\sup_{\|Z\|_1\le1}\|(\operatorname{id}_H\otimes\Delta)(Z)\|_1sup∥Z∥1​≤1​∥(idH​⊗Δ)(Z)∥1​ over all complex matrices ZZZ on H×HH\times HH×H. The map Δ⊗id⁡R\Delta\otimes\operatorname{id}_RΔ⊗idR​ applies Δ\DeltaΔ separately to each matrix block with fixed row and column indices in RRR. The statement includes n=0n=0n=0 and d=1d=1d=1; in either case 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