Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5 (Method of types): all simultaneous typical-projection bounds

Open
QAlgorithms.Papers.Independent.Gap48.P38.theorem5_methodOfTypes

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

prove2quantum

Let ∣ψ⟩ABC|\psi\rangle^{ABC}∣ψ⟩ABC be a unit vector on three nonempty finite complex registers. Write H(T)H(T)H(T) for the bit entropy of its actual marginal on TTT. There is a constant c>0c>0c>0, depending on the source but independent of δ\deltaδ and the requested error, with the following property. For every ϵ,δ>0\epsilon,\delta>0ϵ,δ>0, all sufficiently large positive integers nnn admit orthogonal projections ΠA,ΠB,ΠC\Pi_A,\Pi_B,\Pi_CΠA​,ΠB​,ΠC​ on the corresponding nnn-copy registers. Put ϵn=2−ncδ2≤ϵ\epsilon_n=2^{-nc\delta^2}\le\epsilonϵn​=2−ncδ2≤ϵ. For each T=A,B,CT=A,B,CT=A,B,C,

Tr⁡[ΠT(ψT)⊗n]≥1−ϵn,2nH(T)−nδ≤Tr⁡ΠT≤2nH(T)+nδ.\operatorname{Tr}[\Pi_T(\psi^T)^{\otimes n}]\ge1-\epsilon_n,\qquad 2^{nH(T)-n\delta}\le\operatorname{Tr}\Pi_T\le2^{nH(T)+n\delta}.Tr[ΠT​(ψT)⊗n]≥1−ϵn​,2nH(T)−nδ≤TrΠT​≤2nH(T)+nδ.

Let ∣φ⟩|\varphi\rangle∣φ⟩ be the normalized, nonzero projection of ∣ψ⟩⊗n|\psi\rangle^{\otimes n}∣ψ⟩⊗n by ΠA⊗ΠB⊗ΠC\Pi_A\otimes\Pi_B\otimes\Pi_CΠA​⊗ΠB​⊗ΠC​. Its density matrix is within full trace norm ϵn\epsilon_nϵn​ of (ψABC)⊗n(\psi^{ABC})^{\otimes n}(ψABC)⊗n. For every T∈{A,B,C,AB,BC,AC}T\in\{A,B,C,AB,BC,AC\}T∈{A,B,C,AB,BC,AC}, its actual marginal satisfies all six bounds

2nH(T)−nδ≤rank⁡φTn≤2nH(T)+nδ,2^{nH(T)-n\delta}\le\operatorname{rank}\varphi^{T^n}\le2^{nH(T)+n\delta},2nH(T)−nδ≤rankφTn≤2nH(T)+nδ, 2−nH(T)−nδ≤∥φTn∥22≤2−nH(T)+nδ,2−nH(T)−nδ≤∥φTn∥∞≤2−nH(T)+nδ.2^{-nH(T)-n\delta}\le\|\varphi^{T^n}\|_2^2\le2^{-nH(T)+n\delta},\qquad 2^{-nH(T)-n\delta}\le\|\varphi^{T^n}\|_\infty\le2^{-nH(T)+n\delta}.2−nH(T)−nδ≤∥φTn∥22​≤2−nH(T)+nδ,2−nH(T)−nδ≤∥φTn∥∞​≤2−nH(T)+nδ.

The normalized, nonzero projection by IA⊗IB⊗ΠCI_A\otimes I_B\otimes\Pi_CIA​⊗IB​⊗ΠC​ alone is also within full trace norm ϵn\epsilon_nϵn​ of the original IID density matrix. Here ∥⋅∥2\|\cdot\|_2∥⋅∥2​ is the Hilbert–Schmidt norm and ∥⋅∥∞\|\cdot\|_\infty∥⋅∥∞​ the operator norm. These simultaneous bounds supply the complete typical-projection statement, rather than only a support-dimension estimate.

Formalization Note The stray DDD in one projected-vector display is interpreted as trivial, consistently with the theorem's pure tripartite domain.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P38
Formal statement
noncomputable section

open MeasureTheory

open scoped Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise

attribute [local instance] Classical.propDecidable Classical.decEq

namespace QAlgorithms.Papers.Independent.Gap48.P38

/-- Theorem 5 (method of types), PDF pp.4--5, including all lower bounds, the
C-only projection, and a delta-independent positive exponential constant.
The stray ABCD in the projected-vector display is read with D trivial, as
required by the tripartite header and every other display. -/
theorem theorem5_methodOfTypes
    (I : Fin 3 → Type) [∀ i, Fintype (I i)] [∀ i, Nonempty (I i)]
    (psi : EuclideanSpace ℂ (∀ i, I i)) (hpsi : ‖psi‖ = 1) :
    ∃ c : ℝ, 0 < c ∧ ∀ epsilon delta : ℝ, 0 < epsilon → 0 < delta →
      ∃ N : ℕ, 0 < N ∧ ∀ n ≥ N,
        ∃ P : (i : Fin 3) → Matrix (Restricted (fun j => Fin n → I j) {i})
          (Restricted (fun j => Fin n → I j) {i}) ℂ,
          TypicalBounds I psi n delta (Real.rpow 2 (-(n : ℝ) * c * delta ^ 2)) P ∧
          Real.rpow 2 (-(n : ℝ) * c * delta ^ 2) ≤ epsilon := by sorry

end QAlgorithms.Papers.Independent.Gap48.P38

end
Source
Optimal quantum source coding with quantum information at the encoder and decoder, arXiv:0706.2907v2, PDF p. 4, Theorem 5 (Method of types): all simultaneous typical-projection bounds
Read-back

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

For any three finite, nonempty types I0,I1,I2I_0,I_1,I_2I0​,I1​,I2​, with specified finite enumerations and nonemptiness instances, and any vector ψ∈C∏iIi\psi\in\mathbb C^{\prod_iI_i}ψ∈C∏i​Ii​ satisfying ∥ψ∥=1\|\psi\|=1∥ψ∥=1, there exists a real constant c>0c>0c>0 such that, for every pair of real numbers ϵ>0\epsilon>0ϵ>0 and δ>0\delta>0δ>0, there is a natural number N>0N>0N>0 such that, for every natural number n≥Nn\ge Nn≥N, three complex matrices PiP_iPi​ on assignments of nnn values to coordinate iii exist with the properties below. Define Ji=Ii{0,…,n−1}J_i=I_i^{\{0,\ldots,n-1\}}Ji​=Ii{0,…,n−1}​, D(w)x,y=wxwy‾D(w)_{x,y}=w_x\overline{w_y}D(w)x,y​=wx​wy​​, and, for any matrix MMM on coordinate assignments, (Ms)x,y=∑zMx⊔sz,y⊔sz(M_s)_{x,y}=\sum_zM_{x\sqcup_s z,y\sqcup_s z}(Ms​)x,y​=∑z​Mx⊔s​z,y⊔s​z​, where zzz ranges over complementary assignments and ⊔s\sqcup_s⊔s​ combines assignments. Put HM(s)=−Re⁡tr⁡f(Ms)H_M(s)=-\operatorname{Re}\operatorname{tr}f(M_s)HM​(s)=−Retrf(Ms​), with f(x)=xlog⁡2xf(x)=x\log_2xf(x)=xlog2​x evaluated by continuous functional calculus using the total real logarithm, and set

en=2−ncδ2,ρ=D(ψ),Ψ(x)=∏t<nψ((xi(t))i=02),Qx,y=∏i=02Pi(x∣{i},y∣{i}).e_n=2^{-nc\delta^2},\qquad \rho=D(\psi),\qquad \Psi(x)=\prod_{t<n}\psi((x_i(t))_{i=0}^2),\qquad Q_{x,y}=\prod_{i=0}^2P_i(x|_{\{i\}},y|_{\{i\}}).en​=2−ncδ2,ρ=D(ψ),Ψ(x)=t<n∏​ψ((xi​(t))i=02​),Qx,y​=i=0∏2​Pi​(x∣{i}​,y∣{i}​).

Let v=QΨv=Q\Psiv=QΨ, ϕ=D(∥v∥−1v)\phi=D(\|v\|^{-1}v)ϕ=D(∥v∥−1v), and vC=QCΨv_C=Q_C\PsivC​=QC​Ψ, where QCQ_CQC​ is the same product matrix using identities on coordinates 0,10,10,1 and P2P_2P2​ on coordinate 222. Then

en≤ϵ;∀i∈{0,1,2}:Pi†=Pi,Pi2=Pi,Re⁡tr⁡ ⁣(PiD(Ψ){i})≥1−en,2 nHρ({i})−nδ≤Re⁡tr⁡Pi≤2 nHρ({i})+nδ;∥v∥>0,∥ϕ−D(Ψ)∥tr≤en;∀s∈{{0},{1},{2},{0,1},{1,2},{0,2}},h=Hρ(s),τ=ϕs:2nh−nδ≤rank⁡τ≤2nh+nδ,2−nh−nδ≤∥τ∥F 2≤2−nh+nδ,2−nh−nδ≤∥τ∥op≤2−nh+nδ;∥vC∥>0,∥D(∥vC∥−1vC)−D(Ψ)∥tr≤en.\begin{gathered} e_n\le\epsilon;\\ \forall i\in\{0,1,2\}:\quad P_i^\dagger=P_i,\qquad P_i^2=P_i,\qquad \operatorname{Re}\operatorname{tr}\!\left(P_iD(\Psi)_{\{i\}}\right)\ge1-e_n,\\ 2^{\,nH_\rho(\{i\})-n\delta} \le\operatorname{Re}\operatorname{tr}P_i \le2^{\,nH_\rho(\{i\})+n\delta};\\ \|v\|>0,\qquad \|\phi-D(\Psi)\|_{\mathrm{tr}}\le e_n;\\ \forall s\in \bigl\{\{0\},\{1\},\{2\},\{0,1\},\{1,2\},\{0,2\}\bigr\}, \quad h=H_\rho(s),\quad \tau=\phi_s:\\ 2^{nh-n\delta}\le\operatorname{rank}\tau\le2^{nh+n\delta},\\ 2^{-nh-n\delta}\le\|\tau\|_{\mathrm F}^{\,2}\le2^{-nh+n\delta}, \qquad 2^{-nh-n\delta}\le\|\tau\|_{\mathrm{op}}\le2^{-nh+n\delta};\\ \|v_C\|>0,\qquad \bigl\|D(\|v_C\|^{-1}v_C)-D(\Psi)\bigr\|_{\mathrm{tr}}\le e_n. \end{gathered}en​≤ϵ;∀i∈{0,1,2}:Pi†​=Pi​,Pi2​=Pi​,Retr(Pi​D(Ψ){i}​)≥1−en​,2nHρ​({i})−nδ≤RetrPi​≤2nHρ​({i})+nδ;∥v∥>0,∥ϕ−D(Ψ)∥tr​≤en​;∀s∈{{0},{1},{2},{0,1},{1,2},{0,2}},h=Hρ​(s),τ=ϕs​:2nh−nδ≤rankτ≤2nh+nδ,2−nh−nδ≤∥τ∥F2​≤2−nh+nδ,2−nh−nδ≤∥τ∥op​≤2−nh+nδ;∥vC​∥>0,​D(∥vC​∥−1vC​)−D(Ψ)​tr​≤en​.​

The trace norm means Re⁡tr⁡M†M\operatorname{Re}\operatorname{tr}\sqrt{M^\dagger M}RetrM†M​ using continuous functional calculus, the Frobenius norm is ∥⋅∥F\|\cdot\|_{\mathrm F}∥⋅∥F​, and the Euclidean operator norm is ∥⋅∥op\|\cdot\|_{\mathrm{op}}∥⋅∥op​; powers of 222 are real powers. The constant ccc is chosen before ϵ,δ\epsilon,\deltaϵ,δ, whereas NNN may depend on both and the matrices may depend on nnn. The positive threshold excludes n=0n=0n=0, and the conclusion places no requirements on smaller nnn.

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

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 22, 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