Theorem 5 (Method of types): all simultaneous typical-projection bounds
OpenQAlgorithms.Papers.Independent.Gap48.P38.theorem5_methodOfTypesLet be a unit vector on three nonempty finite complex registers. Write for the bit entropy of its actual marginal on . There is a constant , depending on the source but independent of and the requested error, with the following property. For every , all sufficiently large positive integers admit orthogonal projections on the corresponding -copy registers. Put . For each ,
Let be the normalized, nonzero projection of by . Its density matrix is within full trace norm of . For every , its actual marginal satisfies all six bounds
The normalized, nonzero projection by alone is also within full trace norm of the original IID density matrix. Here is the Hilbert–Schmidt norm and the operator norm. These simultaneous bounds supply the complete typical-projection statement, rather than only a support-dimension estimate.
Formalization Note The stray in one projected-vector display is interpreted as trivial, consistently with the theorem's pure tripartite domain.
import Definitions.Def_QAlgorithms_Papers_Independent_Gap48_P38
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
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For any three finite, nonempty types , with specified finite enumerations and nonemptiness instances, and any vector satisfying , there exists a real constant such that, for every pair of real numbers and , there is a natural number such that, for every natural number , three complex matrices on assignments of values to coordinate exist with the properties below. Define , , and, for any matrix on coordinate assignments, , where ranges over complementary assignments and combines assignments. Put , with evaluated by continuous functional calculus using the total real logarithm, and set
Let , , and , where is the same product matrix using identities on coordinates and on coordinate . Then
The trace norm means using continuous functional calculus, the Frobenius norm is , and the Euclidean operator norm is ; powers of are real powers. The constant is chosen before , whereas may depend on both and the matrices may depend on . The positive threshold excludes , and the conclusion places no requirements on smaller .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.