QPBT definitions: Games / CondLinearTheorems
DefinitionQPBT_QPBT_Games_CondLinearTheoremsqpbt
This bundle defines prefix decomposition data for conditionally linear functions. It supplies strict-prefix marginals, coordinate restriction maps, zero-linear-contribution lifts, and the first contribution added to residual data.
Principal definitions:
MIPStarRE.QPBT.clPrefix: defines the strict-prefix marginal value.MIPStarRE.QPBT.CLData: stores prefix-indexed decomposition data.- The conditional-linear raising operation adds a level with zero contribution.
MIPStarRE.QPBT.coordinateRestrictionLinear: defines coordinate restriction linearly.MIPStarRE.QPBT.CLDataOn: refines decomposition data on a register.MIPStarRE.QPBT.clDataFirst: defines the first linear contribution.MIPStarRE.QPBT.clDataConsMarginal: adds that contribution to residual marginals.
Formalization Credit. This Lean declaration is part of the Quantum Pauli basis test formalization by Ruixuan Deng. The source code was generated by AI agents; Ruixuan Deng is the responsible maintainer.
Mathematical Source. The mathematical source is Ji, Natarajan, Vidick, Wright, and Yuen, MIP*=RE, arXiv:2001.04383v3.
Definition code
-- Generated from QPBT/Games/CondLinearTheorems.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_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
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_CommutativityPoints_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_QPBT_QPBT_Games_CondLinear
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-! # Structure and direct sums of conditionally linear functions
A conditionally linear map admits a prefix decomposition. Equal-level
representations on pairwise disjoint registers combine coordinatewise, and the
corresponding shared-seed distributions factor as products. A representation
may first be raised to a larger level by adjoining zero linear contributions.
## References
The source results are blueprint `lem:cl-kth`, `lem:cl-func-prod`, and
`lem:cl-dist-prod`, with paper origin
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-379`.
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
/-- Raise a representation of a conditionally linear function by one level,
whose linear contribution is zero. -/
private def CondLinearTerm.raiseLevel {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {ell : ℕ}
(t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) (ell + 1) :=
.succ ∅ 0 (by simp) (fun _ => t)
@[simp]
private theorem CondLinearTerm.eval_raiseLevel {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {ell : ℕ}
(t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) (x : ι → K) :
_root_.MIPStarRE.QPBT.CondLinearTerm.eval t.raiseLevel x = _root_.MIPStarRE.QPBT.CondLinearTerm.eval t x := by
simp [CondLinearTerm.raiseLevel, _root_.MIPStarRE.QPBT.CondLinearTerm.eval]
/-- Raise a representation of a conditionally linear function by a specified
number of levels, each with zero linear contribution. -/
private def CondLinearTerm.raiseBy {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] :
(d : ℕ) → {ell : ℕ} → _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell →
_root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) (ell + d)
| 0, _, t => t
| d + 1, _, t => (raiseBy d t).raiseLevel
@[simp]
private theorem CondLinearTerm.eval_raiseBy {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] (d : ℕ) {ell : ℕ}
(t : _root_.MIPStarRE.QPBT.CondLinearTerm K (ι := ι) ell) (x : ι → K) :
_root_.MIPStarRE.QPBT.CondLinearTerm.eval (CondLinearTerm.raiseBy d t) x = _root_.MIPStarRE.QPBT.CondLinearTerm.eval t x := by
induction d with
| zero => rfl
| succ d ih => simp [CondLinearTerm.raiseBy, ih]
private theorem coordinateRestriction_add {K ι : Type*} [Field K]
[DecidableEq ι] (S : Finset ι) (x y : ι → K) :
_root_.MIPStarRE.QPBT.coordinateRestriction S (x + y) =
_root_.MIPStarRE.QPBT.coordinateRestriction S x + _root_.MIPStarRE.QPBT.coordinateRestriction S y := by
ext a
by_cases ha : a ∈ S <;> simp [_root_.MIPStarRE.QPBT.coordinateRestriction, ha]
/-- Coordinate restriction as a linear endomorphism. -/
private def coordinateRestrictionLinear {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] (S : Finset ι) :
(ι → K) →ₗ[K] (ι → K) where
toFun := _root_.MIPStarRE.QPBT.coordinateRestriction S
map_add' := coordinateRestriction_add S
map_smul' c x := by
ext a
by_cases ha : a ∈ S <;> simp [_root_.MIPStarRE.QPBT.coordinateRestriction, ha]
/-- The value of the strict-prefix marginal preceding `k`. This is a
formalization-only auxiliary for blueprint
`lem:cl-kth`, paper
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-178`. -/
def clPrefix {K ι : Type*} [Zero K] {ell : ℕ}
(marginal : Fin ell → (ι → K) → (ι → K)) (k : Fin ell)
(x : ι → K) : ι → K :=
if _hk : k.val = 0 then 0
else marginal ⟨k.val - 1, lt_of_le_of_lt (Nat.sub_le _ _) k.isLt⟩ x
/-- Prefix-indexed decomposition data from `lem:cl-kth`. Factor spaces are
represented by their coordinate sets, matching the register-subspace encoding
used by `IsCondLinearOn`. Blueprint `lem:cl-kth`, paper
`references/qpbt-paper/05_conditionally_linear_functions.tex:150-178`. -/
structure CLData (K ι : Type*) [Field K] [Fintype ι] [DecidableEq ι]
(ell : ℕ) (L : (ι → K) → (ι → K)) where
/-- The marginal `L_{≤k}`. -/
marginal : Fin ell → (ι → K) → (ι → K)
/-- The factor register selected by a prefix value. -/
factor : Fin ell → (ι → K) → Finset ι
/-- The linear map selected by a prefix value. -/
linear : Fin ell → (ι → K) → ((ι → K) →ₗ[K] (ι → K))
/-- Each marginal has the corresponding conditionally linear level. -/
marginal_cl : ∀ k, _root_.MIPStarRE.QPBT.IsCondLinearOn K Finset.univ (k.val + 1) (marginal k)
/-- The selected factor registers are pairwise disjoint. -/
factor_disjoint : ∀ x i j, i ≠ j →
Disjoint (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) (factor j (_root_.MIPStarRE.QPBT.clPrefix marginal j x))
/-- The selected factor registers cover all coordinates. -/
factor_cover : ∀ x a, ∃ i, a ∈ factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
/-- Each selected linear map is supported on its factor register. -/
linear_supported : ∀ k u x a, a ∉ factor k u → linear k u x a = 0
/-- Each marginal is the sum of the preceding selected linear pieces. -/
sum_formula : ∀ k x, marginal k x =
∑ i : Fin ell, if i.val ≤ k.val then
linear i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
(_root_.MIPStarRE.QPBT.coordinateRestriction (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) x) else 0
/-- The final marginal is the original function. -/
top : ∀ h : 0 < ell,
marginal ⟨ell - 1, Nat.sub_lt h (by decide)⟩ = L
/-- Prefix decomposition data on a register `S`, refining the decomposition
in `lem:cl-kth`. -/
private structure CLDataOn (K ι : Type*) [Field K] [Fintype ι]
[DecidableEq ι] (S : Finset ι) (ell : ℕ)
(L : (ι → K) → (ι → K)) where
marginal : Fin ell → (ι → K) → (ι → K)
factor : Fin ell → (ι → K) → Finset ι
linear : Fin ell → (ι → K) → ((ι → K) →ₗ[K] (ι → K))
marginal_cl : ∀ k, _root_.MIPStarRE.QPBT.IsCondLinearOn K S (k.val + 1) (marginal k)
factor_subset : ∀ k u, factor k u ⊆ S
factor_disjoint : ∀ x i j, i ≠ j →
Disjoint (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x))
(factor j (_root_.MIPStarRE.QPBT.clPrefix marginal j x))
factor_cover : ∀ x a, a ∈ S → ∃ i, a ∈ factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
linear_supported : ∀ k u x a, a ∉ factor k u → linear k u x a = 0
sum_formula : ∀ k x, marginal k x =
∑ i : Fin ell, if i.val ≤ k.val then
linear i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)
(_root_.MIPStarRE.QPBT.coordinateRestriction (factor i (_root_.MIPStarRE.QPBT.clPrefix marginal i x)) x) else 0
top : ∀ h : 0 < ell,
marginal ⟨ell - 1, Nat.sub_lt h (by decide)⟩ = L
/-- The first linear contribution in the inductive prefix decomposition. -/
private def clDataFirst {K ι : Type*} [Field K] [Fintype ι] [DecidableEq ι]
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(x : ι → K) : ι → K :=
L₁ (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ x)
/-- Add the first contribution to each marginal of residual decomposition
data. -/
private def clDataConsMarginal {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) :
Fin (ell + 1) → (ι → K) → (ι → K) :=
Fin.cases (clDataFirst S₁ L₁) fun k x =>
clDataFirst S₁ L₁ x + (d (clDataFirst S₁ L₁ x)).marginal k x
/-- Select the first or residual factor register from a combined prefix. -/
private def clDataConsFactor {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y)) :
Fin (ell + 1) → (ι → K) → Finset ι :=
Fin.cases (fun _ => S₁) fun k u =>
(d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).factor k (_root_.MIPStarRE.QPBT.coordinateRestriction T u)
/-- Select the first or residual linear map from a combined prefix. -/
private def clDataConsLinear {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) :
Fin (ell + 1) → (ι → K) → ((ι → K) →ₗ[K] (ι → K)) :=
Fin.cases (fun _ => L₁.comp (coordinateRestrictionLinear S₁)) fun k u =>
(d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).linear k (_root_.MIPStarRE.QPBT.coordinateRestriction T u)
@[simp]
private theorem clDataConsMarginal_zero {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) (x : ι → K) :
clDataConsMarginal S₁ L₁ d 0 x = clDataFirst S₁ L₁ x := rfl
@[simp]
private theorem clDataConsMarginal_succ {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) (k : Fin ell) (x : ι → K) :
clDataConsMarginal S₁ L₁ d k.succ x =
clDataFirst S₁ L₁ x +
(d (clDataFirst S₁ L₁ x)).marginal k x := rfl
@[simp]
private theorem clDataConsFactor_zero {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y)) (u : ι → K) :
clDataConsFactor S₁ d 0 u = S₁ := rfl
@[simp]
private theorem clDataConsFactor_succ {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (d : ∀ y, CLDataOn K ι T ell (R y))
(k : Fin ell) (u : ι → K) :
clDataConsFactor S₁ d k.succ u =
(d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).factor k (_root_.MIPStarRE.QPBT.coordinateRestriction T u) := rfl
@[simp]
private theorem clDataConsLinear_zero {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) (u : ι → K) :
clDataConsLinear S₁ L₁ d 0 u =
L₁.comp (coordinateRestrictionLinear S₁) := rfl
@[simp]
private theorem clDataConsLinear_succ {K ι : Type*} [Field K]
[Fintype ι] [DecidableEq ι] {T : Finset ι} {ell : ℕ}
{R : (ι → K) → (ι → K) → (ι → K)}
(S₁ : Finset ι) (L₁ : (ι → K) →ₗ[K] (ι → K))
(d : ∀ y, CLDataOn K ι T ell (R y)) (k : Fin ell) (u : ι → K) :
clDataConsLinear S₁ L₁ d k.succ u =
(d (_root_.MIPStarRE.QPBT.coordinateRestriction S₁ u)).linear k (_root_.MIPStarRE.QPBT.coordinateRestriction T u) := rfl
end MIPStarRE.QPBT
Source