QPBT definitions: Games / TypedCondLinear
DefinitionQPBT_QPBT_Games_TypedCondLinearqpbt
This bundle defines the typed conditionally linear distribution for a pair of question types. It samples a type pair from the graph distribution, binds the corresponding conditional-linear law, and records symmetry under exchanging the two players.
Principal definitions:
MIPStarRE.QPBT.typedCLDistribution: defines the typed conditionally linear distribution by sampling a type pair and binding the selected conditional-linear distribution.MIPStarRE.QPBT.typedCLDistribution_symm: states that a typed conditionally linear distribution built from one family is symmetric under exchanging the players.
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/TypedCondLinear.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_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
import Definitions.Def_QPBT_QPBT_Games_DistributionAux
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-! # Typed conditionally linear distributions
Typed question distributions first sample an ordered edge of the type graph and
then sample the corresponding pair of conditionally linear images of one common
uniform seed.
## References
These are blueprint `def:typed-cl-functions` and `def:typed-cl-distributions`,
with paper origin
`references/qpbt-paper/07_types.tex:57-94`.
-/
@[expose] public section
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
/-- The typed CL distribution: sample a type pair from the graph distribution,
then bind it to the CL distribution selected by those two types. This is
blueprint `def:typed-cl-distributions`, paper
`references/qpbt-paper/07_types.tex:84-94`. -/
noncomputable def typedCLDistribution {K T ι : Type*}
[Field K] [Fintype K] [DecidableEq K]
[Fintype T] [DecidableEq T] [Fintype ι] [DecidableEq ι]
(E : Finset (Sym2 T)) (hE : E.Nonempty)
(L R : T → (ι → K) → (ι → K)) :
_root_.LIDT.MIPStarRE.LDT.Distribution ((T × (ι → K)) × (T × (ι → K))) :=
_root_.MIPStarRE.QPBT.Distribution.bind (_root_.MIPStarRE.QPBT.graphDistribution E hE) fun uv =>
(_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (R uv.2)).map fun xy =>
((uv.1, xy.1), (uv.2, xy.2))
/-- A typed conditionally linear distribution built from a single family is
symmetric under exchanging the two players: the edge law of
`def:graph-distribution` is symmetric, and exchanging the two types exchanges
the two images of the common seed. This is not a named statement of the source
article; it is `lem:typed-cl-distribution-symm` in
`blueprint/src/chapter/ch12_qpbt_games.tex`. -/
theorem typedCLDistribution_symm {K T ι : Type*}
[Field K] [Fintype K] [DecidableEq K]
[Fintype T] [DecidableEq T] [Fintype ι] [DecidableEq ι]
(E : Finset (Sym2 T)) (hE : E.Nonempty)
(L : T → (ι → K) → (ι → K))
(c : (T × (ι → K)) × (T × (ι → K))) :
(_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight c =
(_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight c.swap := by
classical
have hinner : ∀ (u v : T) (w : (T × (ι → K)) × (T × (ι → K))),
((_root_.MIPStarRE.QPBT.clDistribution (L u) (L v)).map fun xy => ((u, xy.1), (v, xy.2))).weight w =
(((Finset.univ : Finset (ι → K)).filter
fun z => ((u, L u z), (v, L v z)) = w).card : _root_.LIDT.MIPStarRE.LDT.Error) *
(1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error)) := by
intro u v w
have hmap : ((_root_.MIPStarRE.QPBT.clDistribution (L u) (L v)).map fun xy => ((u, xy.1), (v, xy.2))) =
(_root_.LIDT.MIPStarRE.LDT.uniformDistribution (ι → K)).map fun z => ((u, L u z), (v, L v z)) := by
rw [_root_.MIPStarRE.QPBT.clDistribution]
exact _root_.MIPStarRE.QPBT.Distribution.map_map _ _ _
rw [hmap, _root_.MIPStarRE.QPBT.uniformDistribution_map_weight]
have hfib : ∀ (u v : T) (w : (T × (ι → K)) × (T × (ι → K))),
((Finset.univ : Finset (ι → K)).filter
fun z => ((u, L u z), (v, L v z)) = w) =
((Finset.univ : Finset (ι → K)).filter
fun z => ((v, L v z), (u, L u z)) = w.swap) := by
rintro u v ⟨w₁, w₂⟩
apply Finset.filter_congr
intro z _
exact Prod.swap_inj.symm
have hbind : ∀ w : (T × (ι → K)) × (T × (ι → K)),
(_root_.MIPStarRE.QPBT.typedCLDistribution E hE L L).weight w =
∑ uv : T × T, (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
((((Finset.univ : Finset (ι → K)).filter
fun z => ((uv.1, L uv.1 z), (uv.2, L uv.2 z)) = w).card : _root_.LIDT.MIPStarRE.LDT.Error) *
(1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error))) := by
intro w
have hsupport : (∑ uv ∈ (_root_.MIPStarRE.QPBT.graphDistribution E hE).support,
(_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w) =
∑ uv : T × T, (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w := by
refine Finset.sum_subset (Finset.subset_univ _) fun uv _ huv => ?_
rw [(_root_.MIPStarRE.QPBT.graphDistribution E hE).outsideSupport uv huv, zero_mul]
change (∑ uv ∈ (_root_.MIPStarRE.QPBT.graphDistribution E hE).support,
(_root_.MIPStarRE.QPBT.graphDistribution E hE).weight uv *
((_root_.MIPStarRE.QPBT.clDistribution (L uv.1) (L uv.2)).map
fun xy => ((uv.1, xy.1), (uv.2, xy.2))).weight w) = _
rw [hsupport]
exact Finset.sum_congr rfl fun uv _ => by rw [hinner uv.1 uv.2 w]
rw [hbind c, hbind c.swap]
refine Fintype.sum_equiv (Equiv.prodComm T T) _ _ ?_
rintro ⟨u, v⟩
change (_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (u, v) *
((((Finset.univ : Finset (ι → K)).filter
fun z => ((u, L u z), (v, L v z)) = c).card : _root_.LIDT.MIPStarRE.LDT.Error) *
(1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error))) =
(_root_.MIPStarRE.QPBT.graphDistribution E hE).weight (v, u) *
((((Finset.univ : Finset (ι → K)).filter
fun z => ((v, L v z), (u, L u z)) = c.swap).card : _root_.LIDT.MIPStarRE.LDT.Error) *
(1 / (Fintype.card (ι → K) : _root_.LIDT.MIPStarRE.LDT.Error)))
rw [_root_.MIPStarRE.QPBT.graphDistribution_symm E hE u v, hfib u v c]
end MIPStarRE.QPBT
Source