QPBT definitions: Test / MagicSquare
DefinitionQPBT_QPBT_Test_MagicSquareqpbt
This bundle defines the finite Magic Square question and answer carriers. It distinguishes constraint and cell questions, records incidence and parity data, defines the answer constructors, and supplies finite coding and relabeling infrastructure for the answer alphabet.
Principal definitions:
MIPStarRE.QPBT.MsType: defines a Magic Square question as either a row or column constraint or a cell variable.MIPStarRE.QPBT.msConstraintVars: defines the cell incident to a constraint and one of its three positions.MIPStarRE.QPBT.msParity: defines the exceptional Magic Square parity, which is nonzero only on the final constraint.MIPStarRE.QPBT.msEdges: defines the 18 constraint-variable incidence edges of the Magic Square graph.MIPStarRE.QPBT.MsAnswer: defines a Magic Square answer as a parity triple or a single cell bit.MIPStarRE.QPBT.msBitOrZero: defines the total relabeling from the global Magic Square answer alphabet to a bit.MIPStarRE.QPBT.MsAnswerCode: defines a finite code for the two Magic Square answer constructors.MIPStarRE.QPBT.msAnswerEquiv: defines the constructor-preserving code equivalence for Magic Square answers.
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/Test/MagicSquare.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_Defs
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# The Magic Square game
The Magic Square component is represented by finite constraint and variable
question types, the incidence graph, and the two corresponding answer forms.
Its rigidity theorem is outside the stage-4.1 statement closure; only the game
carrier is needed here.
## References
This file formalizes blueprint
`def:ms-game`, from
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
@[expose] public section
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
/-- A Magic Square question is either a row/column constraint or a cell
variable. This is blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
inductive MsType where
| constraint (i : Fin 6)
| var (j : Fin 9)
deriving DecidableEq, Repr, Inhabited, Fintype
/-- The cell incident to a constraint and one of its three positions in
blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msConstraintVars (i : Fin 6) (j : Fin 3) : Fin 9 :=
⟨if i.val < 3 then i.val * 3 + j.val else i.val - 3 + j.val * 3, by
by_cases h : i.val < 3 <;> simp [h] <;> omega⟩
/-- The exceptional Magic Square parity, equal to one only on the final
constraint. Blueprint `def:ms-game`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msParity (i : Fin 6) : ZMod 2 :=
if i.val = 5 then 1 else 0
/-- The 18 constraint-variable incidence edges of the Magic Square graph in
blueprint `def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msEdges : Finset (Sym2 _root_.MIPStarRE.QPBT.MsType) :=
(Finset.univ : Finset (Fin 6 × Fin 3)).image (fun ij =>
Sym2.mk (.constraint ij.1) (.var (_root_.MIPStarRE.QPBT.msConstraintVars ij.1 ij.2)))
/-- The Magic Square incidence graph has an edge, as required by the
nonempty-support API of `graphDistribution`. This is the finite carrier fact
used to instantiate blueprint `def:ms-game`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
theorem msEdges_nonempty : _root_.MIPStarRE.QPBT.msEdges.Nonempty := by
refine ⟨Sym2.mk (.constraint 0) (.var (_root_.MIPStarRE.QPBT.msConstraintVars 0 0)), ?_⟩
exact Finset.mem_image.mpr ⟨(0, 0), Finset.mem_univ _, rfl⟩
/-- A Magic Square answer is a parity triple or a single cell bit, as prescribed
by blueprint `def:ms-game`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
inductive MsAnswer where
| triple (β : Fin 3 → ZMod 2)
| bit (γ : ZMod 2)
deriving DecidableEq
/-- A formalization-only total relabeling from the global Magic Square answer
alphabet to a bit. It folds wrong-form answers into zero so that a variable
question yields a complete binary measurement. -/
def msBitOrZero : _root_.MIPStarRE.QPBT.MsAnswer → ZMod 2
| .bit b => b
| .triple _ => 0
/-- A finite code for the two Magic Square answer constructors. This is
Lean-only carrier infrastructure for blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
abbrev MsAnswerCode := (Fin 3 → ZMod 2) ⊕ ZMod 2
/-- The constructor-preserving code equivalence for `MsAnswer`; Lean-only
finite-carrier infrastructure for blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
noncomputable def msAnswerEquiv : _root_.MIPStarRE.QPBT.MsAnswer ≃ _root_.MIPStarRE.QPBT.MsAnswerCode where
toFun
| .triple β => .inl β
| .bit γ => .inr γ
invFun
| .inl β => .triple β
| .inr γ => .bit γ
left_inv := by intro x; cases x <;> rfl
right_inv := by
intro x
cases x <;> rfl
noncomputable instance instFintypeMsAnswer : Fintype _root_.MIPStarRE.QPBT.MsAnswer :=
Fintype.ofEquiv _root_.MIPStarRE.QPBT.MsAnswerCode _root_.MIPStarRE.QPBT.msAnswerEquiv.symm
instance instInhabitedMsAnswer : Inhabited _root_.MIPStarRE.QPBT.MsAnswer := ⟨.bit 0⟩
/-- The Magic Square consistency predicate. Constructor mismatches are
rejected, as required by blueprint `def:ms-game`; paper
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
def msWinPredicate :
_root_.MIPStarRE.QPBT.MsType → _root_.MIPStarRE.QPBT.MsType → _root_.MIPStarRE.QPBT.MsAnswer → _root_.MIPStarRE.QPBT.MsAnswer → Bool
| .constraint i, .constraint j, .triple β, .triple β' =>
decide (i = j ∧ β = β')
| .var i, .var j, .bit γ, .bit γ' =>
decide (i = j ∧ γ = γ')
| .constraint i, .var j, .triple β, .bit γ =>
decide
((∑ k : Fin 3, β k) = _root_.MIPStarRE.QPBT.msParity i ∧
∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j ∧ β k = γ)
| .var j, .constraint i, .bit γ, .triple β =>
decide
((∑ k : Fin 3, β k) = _root_.MIPStarRE.QPBT.msParity i ∧
∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j ∧ β k = γ)
| _, _, _, _ => false
/-- The Magic Square game as a finite `Game`. This is blueprint
`def:ms-game`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`.
-/
@[reducible] noncomputable def msGame : _root_.MIPStarRE.QPBT.Game where
QuestionA := _root_.MIPStarRE.QPBT.MsType
QuestionB := _root_.MIPStarRE.QPBT.MsType
AnswerA := _root_.MIPStarRE.QPBT.MsAnswer
AnswerB := _root_.MIPStarRE.QPBT.MsAnswer
μ := _root_.MIPStarRE.QPBT.graphDistribution _root_.MIPStarRE.QPBT.msEdges _root_.MIPStarRE.QPBT.msEdges_nonempty
μ_prob := by
apply _root_.LIDT.MIPStarRE.LDT.Distribution.uniformOnFinset_isProbability
refine ⟨(.constraint 0, .var (_root_.MIPStarRE.QPBT.msConstraintVars 0 0)), ?_⟩
simp [_root_.MIPStarRE.QPBT.msEdges]
decide := _root_.MIPStarRE.QPBT.msWinPredicate
end MIPStarRE.QPBT
Source