QPBT definitions: Palomar / LowDegreeGameBridge
DefinitionQPBT_QPBT_Palomar_LowDegreeGameBridgeqpbt
This bundle bridges the compact Palomar low-degree game representation with the original typed game spaces. It defines parameter copying, equivalences for question and answer carriers, common source and question-pair spaces, and the compact seed-index map.
Principal definitions:
- MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams: copies LDT parameters into the compact domain, using
LowDegreeParams. MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv: equates compact and original question-type carriers.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv: identifies the compact and original spaces.MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv: the typed question equivalence.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv: the answer-carrier equivalence.MIPStarRE.QPBT.Palomar.lowDegreeSourceEquiv: the common-source equivalence.MIPStarRE.QPBT.Palomar.lowDegreeQuestionPairEquiv: the ordered question-pair equivalence.MIPStarRE.QPBT.Palomar.lowDegreeChiIndex_eq: identifies the compact seed index with the original map.
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/Palomar/LowDegreeGameBridge.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_Algebra_Coefficients
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Palomar_Definitions
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGameMeasurements
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT.Palomar
end MIPStarRE.QPBT.Palomar
/-!
# Exact bridge for the compact low individual degree game
This module identifies the compact product-space game with the existing
low-degree game. The bridge is by explicit equivalences of question
coordinates and answer summands. It preserves the question PMF, every branch
of the Boolean verifier, and the value of every compact strategy exactly.
## References
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:31-440`.
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT.Palomar
open LIDT.MIPStarRE.LDT
/-- Copy the original numerical parameter record into the compact domain. -/
@[reducible] def LowDegreeParams.ofLdParams
(P : _root_.MIPStarRE.QPBT.LdParams) : _root_.MIPStarRE.QPBT.Palomar.LowDegreeParams where
q := P.q
m := P.m
d := P.d
k := P.k
hm := P.hm
hd := P.hd
hk := P.hk
hq := P.hq
hdvd := P.hdvd
/-- The compact and original three-element question-type carriers are equivalent. -/
def lowDegreeTypeEquiv : _root_.MIPStarRE.QPBT.Palomar.LowDegreeType ≃ _root_.MIPStarRE.QPBT.LdType where
toFun
| .point => .point
| .aline => .aline
| .dline => .dline
invFun
| .point => .point
| .aline => .aline
| .dline => .dline
left_inv t := by cases t <;> rfl
right_inv t := by cases t <;> rfl
/-- Split-function coordinates identify the complete compact and original spaces. -/
def lowDegreeSpaceEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
_root_.MIPStarRE.QPBT.LdSpace P :=
(_root_.MIPStarRE.QPBT.ldSpaceSplit P).symm
/-- Typed questions are equivalent by the explicit type and coordinate maps. -/
def lowDegreeQuestionEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
_root_.MIPStarRE.QPBT.LdQuestion P :=
Equiv.prodCongr _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P)
/-- The three answer summands are exactly the original answer constructors. -/
@[reducible] noncomputable def lowDegreeAnswerEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
_root_.MIPStarRE.QPBT.Palomar.LowDegreeAnswer (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ≃
_root_.MIPStarRE.QPBT.LdAnswer P :=
(_root_.MIPStarRE.QPBT.ldAnswerEquiv P).symm
/-- The complete common-source spaces are equivalent coordinate by coordinate. -/
def lowDegreeSourceEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
((_root_.MIPStarRE.QPBT.Palomar.LowDegreeType × _root_.MIPStarRE.QPBT.Palomar.LowDegreeType) ×
_root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) ≃
((_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) ×
_root_.MIPStarRE.QPBT.LdSpace P) :=
Equiv.prodCongr (Equiv.prodCongr _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv _root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv)
(_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P)
/-- Equivalence of the two ordered question-pair carriers. -/
def lowDegreeQuestionPairEquiv (P : _root_.MIPStarRE.QPBT.LdParams) :
(_root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P) ×
_root_.MIPStarRE.QPBT.Palomar.LowDegreeQuestion (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) ≃
(_root_.MIPStarRE.QPBT.LdQuestion P × _root_.MIPStarRE.QPBT.LdQuestion P) :=
Equiv.prodCongr (_root_.MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv P) (_root_.MIPStarRE.QPBT.Palomar.lowDegreeQuestionEquiv P)
/-- The compact seed-index map is the original `chiIndex`. -/
@[simp] theorem lowDegreeChiIndex_eq (P : _root_.MIPStarRE.QPBT.LdParams)
(s : _root_.MIPStarRE.QPBT.ScalarQ P) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeChiIndex (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
(_root_.MIPStarRE.QPBT.binaryRepresentation P.model) s =
_root_.MIPStarRE.QPBT.chiIndex P s := by
rfl
/-- The compact prefix projection is the original prefix projection. -/
@[simp] theorem lowDegreePrefix_eq (P : _root_.MIPStarRE.QPBT.LdParams)
(i : Fin P.m) (v : Fin P.m → _root_.MIPStarRE.QPBT.ScalarQ P) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreePrefix i v = _root_.MIPStarRE.QPBT.prefixProjection i v :=
rfl
/-- The compact least nonzero coordinate is the one used by the published formula. -/
theorem lowDegreePivot_eq_linePivotIndex {K : Type} [Field K] [DecidableEq K]
{m : ℕ} (v : Fin m → K) (hv : v ≠ 0) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv = _root_.MIPStarRE.QPBT.linePivotIndex v hv := by
have hpivot_ne : v (_root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv) ≠ 0 := by
unfold _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot
change v ((Finset.univ.filter fun j : Fin m => v j ≠ 0).min' _) ≠ 0
exact (Finset.mem_filter.mp (Finset.min'_mem
(Finset.univ.filter fun j : Fin m => v j ≠ 0) _)).2
have hpivot_le (i : Fin m) (hi : v i ≠ 0) : _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot v hv ≤ i := by
unfold _root_.MIPStarRE.QPBT.Palomar.lowDegreePivot
change (Finset.univ.filter fun j : Fin m => v j ≠ 0).min' _ ≤ i
exact Finset.min'_le _ i (by simp [hi])
apply le_antisymm
· exact hpivot_le _ (_root_.MIPStarRE.QPBT.linePivotIndex_ne_zero v hv)
· apply le_of_not_gt
intro hlt
exact hpivot_ne (_root_.MIPStarRE.QPBT.linePivotIndex_zero_before v hv _ hlt)
/-- The compact elementary representative is exactly the canonical representative. -/
theorem lowDegreeLineRep_eq_lineRepMap {K : Type} [Field K] [DecidableEq K]
{m : ℕ} (u v : Fin m → K) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep u v = _root_.MIPStarRE.QPBT.lineRepMap v u := by
rw [_root_.MIPStarRE.QPBT.lineRepMap_apply_eq_explicitLineRep]
simp only [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep, _root_.MIPStarRE.QPBT.explicitLineRep]
split_ifs with hv
· rfl
· rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreePivot_eq_linePivotIndex v hv]
/-- The compact point map agrees with the original point map. -/
theorem lowDegreeMap_point_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
(_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
(_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
.point z) =
_root_.MIPStarRE.QPBT.ldPointCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
rfl
/-- The compact axis-line map agrees with the original axis-line map. -/
theorem lowDegreeMap_aline_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
(_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
(_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
.aline z) =
_root_.MIPStarRE.QPBT.ldALineCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
funext i
rcases i with (j | u) | j
· change _root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep z.1.1
(Pi.single (_root_.MIPStarRE.QPBT.chiIndex P z.1.2) 1) j =
_root_.MIPStarRE.QPBT.lineRepMap
(_root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex P z.1.2))
z.1.1 j
rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep_eq_lineRepMap]
rfl
· cases u
rfl
· rfl
/-- The compact diagonal-line map agrees with the original diagonal-line map. -/
theorem lowDegreeMap_dline_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
(_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
(_root_.MIPStarRE.QPBT.binaryRepresentation P.model)
.dline z) =
_root_.MIPStarRE.QPBT.ldDLineCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
funext i
rcases i with (j | u) | j
· change _root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep z.1.1
(_root_.MIPStarRE.QPBT.prefixProjection
(_root_.MIPStarRE.QPBT.chiIndex P z.1.2) z.2) j =
_root_.MIPStarRE.QPBT.lineRepMap
(_root_.MIPStarRE.QPBT.prefixProjection
(_root_.MIPStarRE.QPBT.chiIndex P z.1.2) z.2) z.1.1 j
rw [_root_.MIPStarRE.QPBT.Palomar.lowDegreeLineRep_eq_lineRepMap]
· cases u
rfl
· rfl
/-- All three compact question maps commute with the coordinate equivalence. -/
theorem lowDegreeMap_equiv (P : _root_.MIPStarRE.QPBT.LdParams)
(t : _root_.MIPStarRE.QPBT.Palomar.LowDegreeType)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P
(_root_.MIPStarRE.QPBT.Palomar.lowDegreeMap (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P)
(_root_.MIPStarRE.QPBT.binaryRepresentation P.model) t z) =
_root_.MIPStarRE.QPBT.ldCL P (_root_.MIPStarRE.QPBT.Palomar.lowDegreeTypeEquiv t) (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) := by
cases t with
| point => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_point_equiv P z
| aline => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_aline_equiv P z
| dline => exact _root_.MIPStarRE.QPBT.Palomar.lowDegreeMap_dline_equiv P z
/-- Polynomial coefficient evaluation is unchanged by the compact presentation. -/
@[simp] theorem lowDegreeEval_eq_evalCoefficient {K : Type} [Semiring K]
{n : ℕ} (c : Fin n → K) (t : K) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeEval c t = _root_.MIPStarRE.QPBT.evalCoefficient c t :=
rfl
/-- The point block of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_point (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.LdSpace.point (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.1.1 := by
rfl
/-- The scalar seed of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_seed (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.LdSpace.seed (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.1.2 := by
rfl
/-- The direction block of the transported ambient vector is unchanged. -/
@[simp] theorem lowDegreeSpaceEquiv_direction (P : _root_.MIPStarRE.QPBT.LdParams)
(z : _root_.MIPStarRE.QPBT.Palomar.LowDegreeSpace (_root_.MIPStarRE.QPBT.Palomar.LowDegreeParams.ofLdParams P) (_root_.MIPStarRE.QPBT.ScalarQ P)) :
_root_.MIPStarRE.QPBT.LdSpace.direction (_root_.MIPStarRE.QPBT.Palomar.lowDegreeSpaceEquiv P z) = z.2 := by
rfl
/-- Point-value answers map to the original point-value constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_point (P : _root_.MIPStarRE.QPBT.LdParams)
(a : Fin P.k → _root_.MIPStarRE.QPBT.ScalarQ P) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inl a) = .pointVals a := by
rfl
/-- Axis-line answers map to the original axis-line constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_aline (P : _root_.MIPStarRE.QPBT.LdParams)
(a : Fin P.k → Fin (P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inr (.inl a)) = .alinePolys a := by
rfl
/-- Diagonal-line answers map to the original diagonal-line constructor. -/
@[simp] theorem lowDegreeAnswerEquiv_dline (P : _root_.MIPStarRE.QPBT.LdParams)
(a : Fin P.k → Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.ScalarQ P) :
_root_.MIPStarRE.QPBT.Palomar.lowDegreeAnswerEquiv P (.inr (.inr a)) = .dlinePolys a := by
rfl
end MIPStarRE.QPBT.Palomar
Source