LIDT definitions: LDT / SelfImprovement / Theorems / Results / CommonHelpers
DefinitionLIDT_MIPStarRE_LDT_SelfImprovement_Theorems_Results_CommonHelperslidt
This bundle collects common scalar helper bounds used by the self-improvement proof. It bounds averaged point operators, lifts consistency and SDD relations from a unit index to nonempty question types, and turns a consistency relation into a lower bound on matching mass.
Principal definitions:
averagedPointOperator_le_one: bounds the averaged point operator by the identity bound.bipartiteSSCRel_uniform_const: lifts bipartite SSC from a unit index.sddRel_uniform_const: lifts SDD from a unit index.cons_rel_uniform_full_total_match_mass_lower_bound: derives a matching-mass lower bound from consistency and completeness.
Formalization credit: Sirui Lu, Ruixuan Deng, Yanqiao Zhu, and Zhengfeng Ji (arXiv:2609.19814). Mathematical source: Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen (arXiv:2009.12982).
Definition code
-- Generated from MIPStarRE/LDT/SelfImprovement/Theorems/Results/CommonHelpers.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_Distribution
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DistributionAvg
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DistributionUniformSums
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_MeasurementLift
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OperatorExpectations
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_PMFAverages
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_PMFUniformAverages
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SqrtBounds
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SubMeasurementCore
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_SubMeasurementFamilies
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_TensorPlacement
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Operators
import Definitions.Def_LIDT_MIPStarRE_LDT_MainInductionStep_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_NaimarkCore
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Projectivization
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Statements
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_BipartiteSelfConsistency_Completion
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_BipartiteSelfConsistency_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_BipartiteSelfConsistency_Local
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_CauchySchwarz
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_ComparisonCore
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_DistanceBounds
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SelfConsistency_DataProcessing
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SelfConsistency_Extensions
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SwitchSandwichMain_Completeness
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SwitchSandwichPrep_ApproxDelta
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SwitchSandwichPrep_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_SwitchSandwichPrep_InnerProduct
import Definitions.Def_LIDT_MIPStarRE_LDT_Preliminaries_Triangles_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_SelfImprovement_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_SelfImprovement_Theorems_Statements
import Definitions.Def_LIDT_MIPStarRE_LDT_SelfImprovement_Theorems_Thresholds_Final
import Definitions.Def_LIDT_MIPStarRE_LDT_SelfImprovement_Theorems_Thresholds_Helper
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_QuantumNonneg
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyFailures
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyRole_Algebra
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyRole_Core
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_Basic
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_BlockDiagonal
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_Order
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_TracePairing
import Definitions.Def_LIDT_MIPStarRE_Quantum_Measurement
import Mathlib
import Mathlib.Analysis.MeanInequalitiesPow
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Probability.ProbabilityMassFunction.Integrals
import Mathlib.Probability.ProbabilityMassFunction.Monad
namespace LIDT
namespace MIPStarRE.LDT.Preliminaries
end MIPStarRE.LDT.Preliminaries
/-!
# Shared internal helpers for SelfImprovement results
Formerly `private` lemmas, now module-visible with internal-helper docstrings
so they can be reused across the split result-module leaves.
## Contents
- **averagedPointOperator_le_one** — the averaged point operator for any
polynomial is bounded by 1; used by self-improvement fallback estimates.
- **bipartiteSSCRel_uniform_const** — lift a bipartite SSC from `Unit` to
any nonempty question type (used by `selfImprovement`).
- **sddRel_uniform_const** — lift an SDD from `Unit` to any nonempty
question type (used by `selfImprovement`).
- **cons_rel_uniform_full_total_match_mass_lower_bound** — from `ConsRel`
with total-1 families, derive `1 - δ ≤ avgOver matchMass`; used by
`input_consistency_match_mass_lower_bound`.
## References
- `references/ldt-paper/self_improvement.tex`
- `blueprint/src/chapter/ch07_self_improvement.tex`
-/
@[expose] public section
namespace MIPStarRE.LDT.SelfImprovement
open MIPStarRE.LDT
open MIPStarRE.LDT.ExpansionHypercubeGraph
open MIPStarRE.LDT.GlobalVariance
open MIPStarRE.LDT.MakingMeasurementsProjective
open scoped BigOperators MatrixOrder _root_.Matrix ComplexOrder
variable {ι : Type*} [Fintype ι] [DecidableEq ι]
/-! ## Shared scalar bounds -/
/-- Internal helper: the averaged point operator for any polynomial is bounded by `1`. -/
lemma averagedPointOperator_le_one
(params : Parameters)
[FieldModel params.q]
(strategy : SymStrat params ι)
(g : Polynomial params) :
averagedPointOperator params strategy g ≤ 1 := by
unfold averagedPointOperator
exact averageOperatorOverDistribution_uniform_le_one
(pointConditionedOutcomeOperatorAtPolynomial params strategy g)
(fun u => by
simpa [pointConditionedOutcomeOperatorAtPolynomial] using
Measurement.outcome_le_one (strategy.pointMeasurement u).toMeasurement (g u))
/-- Internal helper: lift bipartite SSC from `Unit` to any nonempty question type. -/
lemma bipartiteSSCRel_uniform_const
{Question Outcome : Type*}
[Fintype Question] [DecidableEq Question] [Nonempty Question]
[Fintype Outcome]
(ψ : QuantumState (ι × ι))
(A : SubMeas Outcome ι) (δ : Error) :
BipartiteSSCRel ψ (uniformDistribution Unit) (constSubMeasFamily A) δ →
BipartiteSSCRel ψ (uniformDistribution Question) (fun _ : Question => A) δ := by
intro hssc
rcases hssc with ⟨hssc⟩
constructor
simpa [bipartiteSSCError, avgOver, uniformDistribution, constSubMeasFamily] using hssc
/-- Internal helper: lift SDD from `Unit` to any nonempty question type. -/
lemma sddRel_uniform_const
{κ Question Outcome : Type*}
[Fintype κ] [DecidableEq κ]
[Fintype Question] [DecidableEq Question] [Nonempty Question]
[Fintype Outcome]
(ψ : QuantumState κ)
(A B : SubMeas Outcome κ) (δ : Error) :
SDDRel ψ (uniformDistribution Unit) (constSubMeasFamily A) (constSubMeasFamily B) δ →
SDDRel ψ (uniformDistribution Question) (fun _ : Question => A)
(fun _ : Question => B) δ := by
intro hsdd
rcases hsdd with ⟨hsdd⟩
constructor
simpa [sddError, avgOver, uniformDistribution, constSubMeasFamily] using hsdd
/-- Internal helper: from `ConsRel` with total-1 families,
derive `1 - δ ≤ avgOver matchMass`. Used by `input_consistency_match_mass_lower_bound`. -/
lemma cons_rel_uniform_full_total_match_mass_lower_bound
{Question Outcome : Type*}
[Fintype Question] [DecidableEq Question] [Nonempty Question]
[Fintype Outcome]
(ψ : QuantumState (ι × ι)) (hψ : ψ.IsNormalized)
(A B : IdxSubMeas Question Outcome ι)
(δ : Error)
(hA_total : ∀ q : Question, (A q).total = 1)
(hB_total : ∀ q : Question, (B q).total = 1)
(hcons : ConsRel ψ (uniformDistribution Question) A B δ) :
1 - δ ≤ avgOver (uniformDistribution Question)
(fun q => qBipartiteMatchMass ψ (A q) (B q)) := by
let 𝒟 := uniformDistribution Question
let matchMass : Question → Error := fun q => qBipartiteMatchMass ψ (A q) (B q)
have hdefect_point :
∀ q : Question,
1 - matchMass q ≤ qBipartiteConsDefect ψ (A q) (B q) := by
intro q
unfold matchMass qBipartiteConsDefect
have htotal :
ev ψ (opTensor (A q).total (B q).total) = 1 := by
simp [hA_total q, hB_total q, opTensor, ev_one_of_isNormalized ψ hψ]
have hle :
1 - qBipartiteMatchMass ψ (A q) (B q) ≤
max 0 (1 - qBipartiteMatchMass ψ (A q) (B q)) :=
le_max_right 0 _
simp [htotal, hle]
have havg_defect :
avgOver 𝒟 (fun q => 1 - matchMass q) ≤ δ := by
calc
avgOver 𝒟 (fun q => 1 - matchMass q)
≤ avgOver 𝒟 (fun q => qBipartiteConsDefect ψ (A q) (B q)) := by
exact avgOver_mono 𝒟 _ _ hdefect_point
_ = bipartiteConsError ψ 𝒟 A B := by rfl
_ ≤ δ := hcons.offDiagonalBound
have hconst : avgOver 𝒟 (fun _ : Question => (1 : Error)) = 1 := by
simpa [𝒟] using (avgOver_uniform_const (α := Question) (c := (1 : Error)))
have hneg :
avgOver 𝒟 (fun q => -matchMass q) =
-avgOver 𝒟 matchMass := by
simpa [avgOver_const_mul, matchMass] using
(avgOver_const_mul 𝒟 (-1) matchMass)
have hsplit :
avgOver 𝒟 (fun q => 1 - matchMass q) =
1 - avgOver 𝒟 matchMass := by
calc
avgOver 𝒟 (fun q => 1 - matchMass q)
= avgOver 𝒟 (fun q => (1 : Error) + (-matchMass q)) := by
simp [sub_eq_add_neg]
_ = avgOver 𝒟 (fun _ : Question => (1 : Error)) +
avgOver 𝒟 (fun q => -matchMass q) := by
rw [avgOver_add]
_ = 1 - avgOver 𝒟 matchMass := by
rw [hconst, hneg]
ring
rw [hsplit] at havg_defect
linarith
end MIPStarRE.LDT.SelfImprovement
end
end LIDT
Source