Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / MagicSquareTheorems / PerfectStrategy / Measurements

Definition
QPBT_QPBT_Test_MagicSquareTheorems_PerfectStrategy_Measurements

by Dengnifer · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

qpbt

This bundle defines the commuting binary measurements used in the Magic Square construction. It builds joint measurements, parity-preserving answer encodings, cell and constraint measurements, the global measurement family, and the projectivity and symmetry properties of the resulting effects.

Principal definitions:

  • MIPStarRE.QPBT.binaryJointMeasurement: defines the joint measurement of two commuting binary projective measurements.
  • MIPStarRE.QPBT.parityTriple: encodes two freely chosen bits as the unique triple with the prescribed parity.
  • MIPStarRE.QPBT.msCellMeasurement: defines the binary measurement associated with a cell of the operator table.
  • MIPStarRE.QPBT.msConstraintJoint: defines the joint measurement of the first two cells in a Magic Square constraint.
  • MIPStarRE.QPBT.msStrategyMeasurement: defines the global Magic Square measurement family induced by the nine cell measurements.
  • MIPStarRE.QPBT.postprocess_effect_eq_zero_of_notMem: states that relabeling a measurement gives zero effect to outcomes outside the relabeling image.
  • MIPStarRE.QPBT.msCellMeasurement_projective: states that each cell measurement in the Magic Square strategy is projective.
  • MIPStarRE.QPBT.msCellMeasurement_transpose: states that every cell-measurement effect is symmetric when the two local observables are symmetric.

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/MagicSquareTheorems/PerfectStrategy/Measurements.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_LIDT_MIPStarRE_Quantum_FiniteMatrix_Basic
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_LIDT_MIPStarRE_Quantum_Measurement
import Definitions.Def_QPBT_QPBT_Algebra_Pauli
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Test_MagicSquare
import Definitions.Def_QPBT_QPBT_Test_MagicSquareTheorems_PerfectStrategy_Observables

namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT

/-!
# Measurements of the perfect Magic Square strategy

This module turns the operator table of `thm:ms-from-ac` into a measurement
family.  It forms the joint measurement of two commuting binary projective
measurements, records the post-processing identities for injective
relabellings, encodes a constraint answer as the parity triple determined by
two freely chosen bits, and assembles the nine cell measurements into the
Magic Square measurement family, closing with the multiplication rule relating
a constraint outcome to the outcomes of its incident variables.

## References

The source statement is blueprint
`thm:ms-from-ac`, from
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:654-722`.
-/

@[expose] public section

open scoped BigOperators Matrix MatrixOrder ComplexOrder

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT hiding Measurement
open LIDT.MIPStarRE.Quantum

noncomputable section

/-- The joint measurement of two commuting binary projective measurements. -/
noncomputable def binaryJointMeasurement
    {V : Type*} [Fintype V] [DecidableEq V]
    (M N : _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hM : _root_.MIPStarRE.QPBT.Measurement.IsProjective M)
    (hN : _root_.MIPStarRE.QPBT.Measurement.IsProjective N)
    (hcomm : ∀ a b, Commute (M.effect a) (N.effect b)) :
    _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2 × ZMod 2) V :=
  _root_.LIDT.MIPStarRE.Quantum.Measurement.ofSumEqOne
    (fun ab => M.effect ab.1 * N.effect ab.2)
    (fun ab => (hM ab.1).mul (hN ab.2) (hcomm ab.1 ab.2) |>.nonneg)
    (by
      rw [Fintype.sum_prod_type]
      simp_rw [← Finset.mul_sum]
      rw [N.sum_eq_one]
      simp [M.sum_eq_one])

private theorem binaryJointMeasurement_projective
    {V : Type*} [Fintype V] [DecidableEq V]
    (M N : _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hM : _root_.MIPStarRE.QPBT.Measurement.IsProjective M)
    (hN : _root_.MIPStarRE.QPBT.Measurement.IsProjective N)
    (hcomm : ∀ a b, Commute (M.effect a) (N.effect b)) :
    _root_.MIPStarRE.QPBT.Measurement.IsProjective
      (_root_.MIPStarRE.QPBT.binaryJointMeasurement M N hM hN hcomm) :=
  fun ab => (hM ab.1).mul (hN ab.2) (hcomm ab.1 ab.2)





 theorem postprocess_effect_of_injective
    {α β V : Type*} [Fintype α] [Fintype β]
    [DecidableEq α] [DecidableEq β] [Fintype V] [DecidableEq V]
    (M : _root_.LIDT.MIPStarRE.Quantum.Measurement α V) (f : α → β) (hf : Function.Injective f) (a : α) :
    (M.postprocess f).effect (f a) = M.effect a := by
  simp only [_root_.LIDT.MIPStarRE.Quantum.Measurement.postprocess_effect, Finset.sum_filter]
  rw [Fintype.sum_eq_single a]
  · simp
  · intro b hba
    have hfb : f b ≠ f a := fun h => hba (hf h)
    simp [hfb]

/-- Relabeling a measurement gives zero effect to outcomes outside the image. -/
theorem postprocess_effect_eq_zero_of_notMem
    {α β V : Type*} [Fintype α] [Fintype β]
    [DecidableEq α] [DecidableEq β] [Fintype V] [DecidableEq V]
    (M : _root_.LIDT.MIPStarRE.Quantum.Measurement α V) (f : α → β) {b : β}
    (hb : b ∉ Set.range f) :
    (M.postprocess f).effect b = 0 := by
  rw [_root_.LIDT.MIPStarRE.Quantum.Measurement.postprocess_effect]
  apply Finset.sum_eq_zero
  intro a ha
  exact (hb ⟨a, (Finset.mem_filter.mp ha).2⟩).elim

private theorem postprocess_projective_of_injective
    {α β V : Type*} [Fintype α] [Fintype β]
    [DecidableEq α] [DecidableEq β] [Fintype V] [DecidableEq V]
    (M : _root_.LIDT.MIPStarRE.Quantum.Measurement α V) (hM : _root_.MIPStarRE.QPBT.Measurement.IsProjective M)
    (f : α → β) (hf : Function.Injective f) :
    _root_.MIPStarRE.QPBT.Measurement.IsProjective (M.postprocess f) := by
  intro b
  by_cases hb : b ∈ Set.range f
  · rcases hb with ⟨a, rfl⟩
    rw [postprocess_effect_of_injective M f hf a]
    exact hM a
  · rw [_root_.MIPStarRE.QPBT.postprocess_effect_eq_zero_of_notMem M f hb]
    exact IsStarProjection.zero _

/-- Encode two freely chosen bits as the unique triple of the prescribed parity. -/
def parityTriple (i : Fin 6) (ab : ZMod 2 × ZMod 2) : Fin 3 → ZMod 2 :=
  ![ab.1, ab.2, _root_.MIPStarRE.QPBT.msParity i - ab.1 - ab.2]

private theorem parityTriple_injective (i : Fin 6) :
    Function.Injective (_root_.MIPStarRE.QPBT.parityTriple i) := by
  intro ab cd h
  apply Prod.ext
  · exact congrFun h 0
  · exact congrFun h 1



 theorem bit_embedding_injective :
    Function.Injective (_root_.MIPStarRE.QPBT.MsAnswer.bit : ZMod 2 → _root_.MIPStarRE.QPBT.MsAnswer) := by
  intro a b h
  exact _root_.MIPStarRE.QPBT.MsAnswer.bit.inj h

 theorem triple_embedding_injective (i : Fin 6) :
    Function.Injective (fun ab => _root_.MIPStarRE.QPBT.MsAnswer.triple (_root_.MIPStarRE.QPBT.parityTriple i ab)) := by
  intro ab cd h
  apply parityTriple_injective i
  exact _root_.MIPStarRE.QPBT.MsAnswer.triple.inj h

/-- The binary measurement associated with a cell of the operator table. -/
noncomputable def msCellMeasurement
    {V : Type*} [Fintype V] [DecidableEq V]
    (OA OB : _root_.LIDT.MIPStarRE.Quantum.Op V) (hOA : OAᴴ = OA) (hOB : OBᴴ = OB)
    (hOA_sq : OA * OA = 1) (hOB_sq : OB * OB = 1)
    (hac : OA * OB = -(OB * OA)) (j : Fin 9) :
    _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) (V × ZMod 2) :=
  _root_.MIPStarRE.QPBT.reflectionMeasurement (_root_.MIPStarRE.QPBT.msCellObservable OA OB j)
    (_root_.MIPStarRE.QPBT.msCellObservable_conjTranspose OA OB hOA hOB hac j)
    (_root_.MIPStarRE.QPBT.msCellObservable_sq OA OB hOA_sq hOB_sq hac j)

@[simp]
private theorem msCellMeasurement_effect
    {V : Type*} [Fintype V] [DecidableEq V]
    (OA OB : _root_.LIDT.MIPStarRE.Quantum.Op V) (hOA : OAᴴ = OA) (hOB : OBᴴ = OB)
    (hOA_sq : OA * OA = 1) (hOB_sq : OB * OB = 1)
    (hac : OA * OB = -(OB * OA)) (j : Fin 9) (b : ZMod 2) :
    (_root_.MIPStarRE.QPBT.msCellMeasurement OA OB hOA hOB hOA_sq hOB_sq hac j).effect b =
      _root_.MIPStarRE.QPBT.reflectionEffect (_root_.MIPStarRE.QPBT.msCellObservable OA OB j) b :=
  rfl

/-- Formalization-only auxiliary lemma for
`exists_ms_perfect_strategy_of_anticommuting` (blueprint
`thm:ms-from-ac`): each of the nine cell measurements of the Magic
Square strategy is projective. -/
theorem msCellMeasurement_projective
    {V : Type*} [Fintype V] [DecidableEq V]
    (OA OB : _root_.LIDT.MIPStarRE.Quantum.Op V) (hOA : OAᴴ = OA) (hOB : OBᴴ = OB)
    (hOA_sq : OA * OA = 1) (hOB_sq : OB * OB = 1)
    (hac : OA * OB = -(OB * OA)) (j : Fin 9) :
    _root_.MIPStarRE.QPBT.Measurement.IsProjective
      (_root_.MIPStarRE.QPBT.msCellMeasurement OA OB hOA hOB hOA_sq hOB_sq hac j) :=
  _root_.MIPStarRE.QPBT.reflectionMeasurement_projective (_root_.MIPStarRE.QPBT.msCellObservable OA OB j)
    (_root_.MIPStarRE.QPBT.msCellObservable_conjTranspose OA OB hOA hOB hac j)
    (_root_.MIPStarRE.QPBT.msCellObservable_sq OA OB hOA_sq hOB_sq hac j)

private theorem reflectionEffect_transpose
    {V : Type*} [Fintype V] [DecidableEq V]
    (O : _root_.LIDT.MIPStarRE.Quantum.Op V) (hO : Oᵀ = O) (b : ZMod 2) :
    (_root_.MIPStarRE.QPBT.reflectionEffect O b)ᵀ = _root_.MIPStarRE.QPBT.reflectionEffect O b := by
  rcases _root_.MIPStarRE.QPBT.zmod_two_eq_zero_or_one b with rfl | rfl <;>
    simp [_root_.MIPStarRE.QPBT.reflectionEffect, Matrix.transpose_add, Matrix.transpose_sub, hO]

/-- Formalization-only auxiliary lemma for
`exists_ms_perfect_strategy_of_anticommuting` (blueprint
`thm:ms-from-ac`): every effect of a cell measurement is symmetric
whenever `OA` and `OB` are symmetric. -/
theorem msCellMeasurement_transpose
    {V : Type*} [Fintype V] [DecidableEq V]
    (OA OB : _root_.LIDT.MIPStarRE.Quantum.Op V) (hOA : OAᴴ = OA) (hOB : OBᴴ = OB)
    (hOA_sq : OA * OA = 1) (hOB_sq : OB * OB = 1)
    (hOA_t : OAᵀ = OA) (hOB_t : OBᵀ = OB)
    (hac : OA * OB = -(OB * OA)) (j : Fin 9) (b : ZMod 2) :
    ((_root_.MIPStarRE.QPBT.msCellMeasurement OA OB hOA hOB hOA_sq hOB_sq hac j).effect b)ᵀ =
      (_root_.MIPStarRE.QPBT.msCellMeasurement OA OB hOA hOB hOA_sq hOB_sq hac j).effect b := by
  rw [msCellMeasurement_effect]
  exact reflectionEffect_transpose _
    (_root_.MIPStarRE.QPBT.msCellObservable_transpose OA OB hOA_t hOB_t hac j) b

/-- The joint measurement of the first two cells in a Magic Square constraint. -/
noncomputable def msConstraintJoint
    {V : Type*} [Fintype V] [DecidableEq V]
    (P : Fin 9 → _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hP : ∀ j, _root_.MIPStarRE.QPBT.Measurement.IsProjective (P j))
    (hcomm : ∀ i k l a b,
      Commute ((P (_root_.MIPStarRE.QPBT.msConstraintVars i k)).effect a)
        ((P (_root_.MIPStarRE.QPBT.msConstraintVars i l)).effect b))
    (i : Fin 6) : _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2 × ZMod 2) V :=
  _root_.MIPStarRE.QPBT.binaryJointMeasurement (P (_root_.MIPStarRE.QPBT.msConstraintVars i 0))
    (P (_root_.MIPStarRE.QPBT.msConstraintVars i 1)) (hP _) (hP _) (hcomm i 0 1)

/-- The global Magic Square measurement family induced by the nine cell measurements. -/
noncomputable def msStrategyMeasurement
    {V : Type*} [Fintype V] [DecidableEq V]
    (P : Fin 9 → _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hP : ∀ j, _root_.MIPStarRE.QPBT.Measurement.IsProjective (P j))
    (hcomm : ∀ i k l a b,
      Commute ((P (_root_.MIPStarRE.QPBT.msConstraintVars i k)).effect a)
        ((P (_root_.MIPStarRE.QPBT.msConstraintVars i l)).effect b)) :
    _root_.MIPStarRE.QPBT.MsType → _root_.LIDT.MIPStarRE.Quantum.Measurement _root_.MIPStarRE.QPBT.MsAnswer V
  | .var j => (P j).postprocess _root_.MIPStarRE.QPBT.MsAnswer.bit
  | .constraint i =>
      (_root_.MIPStarRE.QPBT.msConstraintJoint P hP hcomm i).postprocess
        (fun ab => .triple (_root_.MIPStarRE.QPBT.parityTriple i ab))









/-- Formalization-only auxiliary lemma for
`exists_ms_perfect_strategy_of_anticommuting` (blueprint
`thm:ms-from-ac`): the global Magic Square measurement family is
projective at every question. -/
theorem msStrategyMeasurement_projective
    {V : Type*} [Fintype V] [DecidableEq V]
    (P : Fin 9 → _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hP : ∀ j, _root_.MIPStarRE.QPBT.Measurement.IsProjective (P j))
    (hcomm : ∀ i k l a b,
      Commute ((P (_root_.MIPStarRE.QPBT.msConstraintVars i k)).effect a)
        ((P (_root_.MIPStarRE.QPBT.msConstraintVars i l)).effect b))
    (x : _root_.MIPStarRE.QPBT.MsType) :
    _root_.MIPStarRE.QPBT.Measurement.IsProjective
      (_root_.MIPStarRE.QPBT.msStrategyMeasurement P hP hcomm x) := by
  cases x with
  | var j =>
      exact postprocess_projective_of_injective (P j) (hP j)
        _root_.MIPStarRE.QPBT.MsAnswer.bit bit_embedding_injective
  | constraint i =>
      apply postprocess_projective_of_injective
      · exact binaryJointMeasurement_projective _ _ (hP _) (hP _)
          (hcomm i 0 1)
      · exact triple_embedding_injective i

/-- Formalization-only auxiliary lemma for
`exists_ms_perfect_strategy_of_anticommuting` (blueprint
`thm:ms-from-ac`): post-processing a measurement along a relabelling
of outcomes preserves symmetry of its effects. -/
theorem postprocess_effect_transpose
    {α β V : Type*} [Fintype α] [Fintype β]
    [DecidableEq α] [DecidableEq β] [Fintype V] [DecidableEq V]
    (M : _root_.LIDT.MIPStarRE.Quantum.Measurement α V) (f : α → β)
    (hM : ∀ a, (M.effect a)ᵀ = M.effect a) (b : β) :
    ((M.postprocess f).effect b)ᵀ = (M.postprocess f).effect b := by
  rw [_root_.LIDT.MIPStarRE.Quantum.Measurement.postprocess_effect]
  ext r c
  simp only [Matrix.transpose_apply]
  rw [Matrix.sum_apply, Matrix.sum_apply]
  apply Finset.sum_congr rfl
  intro a _
  exact congrFun (congrFun (hM a) r) c

/-- Formalization-only auxiliary lemma for
`exists_ms_perfect_strategy_of_anticommuting` (blueprint
`thm:ms-from-ac`): the effects of the joint measurement of the first
two cells of a constraint are symmetric whenever the underlying cell effects
are. -/
theorem msConstraintJoint_effect_transpose
    {V : Type*} [Fintype V] [DecidableEq V]
    (P : Fin 9 → _root_.LIDT.MIPStarRE.Quantum.Measurement (ZMod 2) V)
    (hP : ∀ j, _root_.MIPStarRE.QPBT.Measurement.IsProjective (P j))
    (hcomm : ∀ i k l a b,
      Commute ((P (_root_.MIPStarRE.QPBT.msConstraintVars i k)).effect a)
        ((P (_root_.MIPStarRE.QPBT.msConstraintVars i l)).effect b))
    (hPt : ∀ j b, ((P j).effect b)ᵀ = (P j).effect b)
    (i : Fin 6) (ab : ZMod 2 × ZMod 2) :
    ((_root_.MIPStarRE.QPBT.msConstraintJoint P hP hcomm i).effect ab)ᵀ =
      (_root_.MIPStarRE.QPBT.msConstraintJoint P hP hcomm i).effect ab := by
  change (((P (_root_.MIPStarRE.QPBT.msConstraintVars i 0)).effect ab.1 *
    (P (_root_.MIPStarRE.QPBT.msConstraintVars i 1)).effect ab.2)ᵀ) = _
  rw [Matrix.transpose_mul, hPt, hPt]
  exact (hcomm i 0 1 ab.1 ab.2).symm.eq





end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/MagicSquareTheorems/PerfectStrategy/Measurements.lean#L34-L391

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me