QPBT definitions: Test / MagicSquareTheorems / Rigidity / Relations
DefinitionQPBT_QPBT_Test_MagicSquareTheorems_Rigidity_Relationsqpbt
This bundle defines the mass and incidence relations used in Magic Square rigidity. It distinguishes directed constraint-variable incidences, conditions acceptance and rejection on question pairs, totalizes malformed answers, and records forward cell mismatch mass.
Principal definitions:
MIPStarRE.QPBT.MagicSquareRigidity.directedIncidence: the directed constraint-variable incidence set.MIPStarRE.QPBT.MagicSquareRigidity.rejectionMass: rejection mass conditioned on a question pair.MIPStarRE.QPBT.MagicSquareRigidity.acceptanceMass: acceptance mass conditioned on a question pair.MIPStarRE.QPBT.MagicSquareRigidity.totalRejectionMass: rejection mass averaged over the game distribution.MIPStarRE.QPBT.MagicSquareRigidity.constraintBitOrZero: the selected constraint bit with malformed answers sent to zero.MIPStarRE.QPBT.MagicSquareRigidity.wrongVariableAnswer: detects a wrong-form variable answer.MIPStarRE.QPBT.MagicSquareRigidity.wrongConstraintAnswer: detects a wrong-form constraint answer.MIPStarRE.QPBT.MagicSquareRigidity.forwardCellMismatchMass: the forward-incidence cell-bit mismatch mass.
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/Rigidity/Relations.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
import Definitions.Def_QPBT_QPBT_Test_MagicSquare
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT.MagicSquareRigidity
end MIPStarRE.QPBT.MagicSquareRigidity
/-!
# Magic Square value-to-parity relations
This file extracts the elementary probability relations used at the start of
the Magic Square rigidity argument. A strategy of value at least `1 - ε` has
total rejection mass at most `ε`. Since the question distribution is
supported on at most 36 directed incidences, the rejection mass at each
incidence is at most `36 * ε`. This controls malformed answers, consistency
of the two reported bits at every cell, and the parity product on each of the
six row or column constraints.
The arguments apply to arbitrary finite POVMs. In particular, malformed
answers remain in the event masses when `msBitOrZero` and
`constraintBitOrZero` turn the common answer alphabet into binary outcomes.
## References
The Magic Square game is defined in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:512-610`
and blueprint `def:ms-game`. These relations are the
probabilistic input to the rigidity result cited at paper lines 612-652 from
Coladangelo--Stark, Theorem 6.9.
-/
@[expose] public section
open scoped BigOperators Matrix MatrixOrder ComplexOrder
namespace MIPStarRE.QPBT.MagicSquareRigidity
open LIDT.MIPStarRE.LDT LIDT.MIPStarRE.Quantum
noncomputable section
/-! ## The directed incidence distribution -/
/-- The 36 possible directed constraint-variable incidences. -/
def directedIncidence : ((Fin 6 × Fin 3) × Bool) → _root_.MIPStarRE.QPBT.MsType × _root_.MIPStarRE.QPBT.MsType
| ((i, k), false) => (.constraint i, .var (_root_.MIPStarRE.QPBT.msConstraintVars i k))
| ((i, k), true) => (.var (_root_.MIPStarRE.QPBT.msConstraintVars i k), .constraint i)
/-! ## Rejection mass from the game value -/
instance msWinFalseDecidableRel (x y : _root_.MIPStarRE.QPBT.MsType) :
DecidableRel (fun a b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.msWinPredicate x y a b = false) :=
fun _ _ => inferInstance
private instance msWinTrueDecidableRel (x y : _root_.MIPStarRE.QPBT.MsType) :
DecidableRel (fun a b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.msWinPredicate x y a b = true) :=
fun _ _ => inferInstance
/-- The rejection mass conditioned on a question pair. -/
noncomputable def rejectionMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame) (x y : _root_.MIPStarRE.QPBT.MsType) : ℝ :=
@_root_.MIPStarRE.QPBT.outcomeEventWeight _root_.MIPStarRE.QPBT.msGame S x y
(fun a b => _root_.MIPStarRE.QPBT.msWinPredicate x y a b = false) (fun _ _ => inferInstance)
/-- The acceptance mass conditioned on a question pair. -/
noncomputable def acceptanceMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame) (x y : _root_.MIPStarRE.QPBT.MsType) : ℝ :=
@_root_.MIPStarRE.QPBT.outcomeEventWeight _root_.MIPStarRE.QPBT.msGame S x y
(fun a b => _root_.MIPStarRE.QPBT.msWinPredicate x y a b = true) (fun _ _ => inferInstance)
/-- The rejection mass averaged over the Magic Square question distribution. -/
noncomputable def totalRejectionMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame) : ℝ :=
_root_.LIDT.MIPStarRE.LDT.avgOver (_root_.MIPStarRE.QPBT.graphDistribution _root_.MIPStarRE.QPBT.msEdges _root_.MIPStarRE.QPBT.msEdges_nonempty) fun xy =>
_root_.MIPStarRE.QPBT.MagicSquareRigidity.rejectionMass S xy.1 xy.2
/-! ## Malformed answers and cell consistency -/
/-- The selected constraint bit, with a wrong-form single-bit answer folded to zero. -/
def constraintBitOrZero (k : Fin 3) : _root_.MIPStarRE.QPBT.MsAnswer → ZMod 2
| .triple β => β k
| .bit _ => 0
/-- Whether an answer has the wrong form for a variable question. -/
def wrongVariableAnswer : _root_.MIPStarRE.QPBT.MsAnswer → Bool
| .triple _ => true
| .bit _ => false
/-- Whether an answer has the wrong form for a constraint question. -/
def wrongConstraintAnswer : _root_.MIPStarRE.QPBT.MsAnswer → Bool
| .triple _ => false
| .bit _ => true
private instance wrongVariableAnswerLeftDecidableRel :
DecidableRel (fun a _ : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.wrongVariableAnswer a = true) :=
fun _ _ => inferInstance
private instance wrongVariableAnswerRightDecidableRel :
DecidableRel (fun _ b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.wrongVariableAnswer b = true) :=
fun _ _ => inferInstance
private instance wrongConstraintAnswerLeftDecidableRel :
DecidableRel (fun a _ : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.wrongConstraintAnswer a = true) :=
fun _ _ => inferInstance
private instance wrongConstraintAnswerRightDecidableRel :
DecidableRel (fun _ b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.wrongConstraintAnswer b = true) :=
fun _ _ => inferInstance
instance forwardCellMismatchDecidableRel (k : Fin 3) :
DecidableRel (fun a b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintBitOrZero k a ≠ _root_.MIPStarRE.QPBT.msBitOrZero b) :=
fun _ _ => inferInstance
instance reverseCellMismatchDecidableRel (k : Fin 3) :
DecidableRel (fun a b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.msBitOrZero a ≠ _root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintBitOrZero k b) :=
fun _ _ => inferInstance
/-- The forward-incidence mass on which the two totalized cell bits disagree. -/
noncomputable def forwardCellMismatchMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame)
(i : Fin 6) (k : Fin 3) : ℝ :=
@_root_.MIPStarRE.QPBT.outcomeEventWeight _root_.MIPStarRE.QPBT.msGame S (.constraint i) (.var (_root_.MIPStarRE.QPBT.msConstraintVars i k))
(fun a b => _root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintBitOrZero k a ≠ _root_.MIPStarRE.QPBT.msBitOrZero b) (fun _ _ => inferInstance)
/-- The reverse-incidence mass on which the two totalized cell bits disagree. -/
noncomputable def reverseCellMismatchMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame)
(i : Fin 6) (k : Fin 3) : ℝ :=
@_root_.MIPStarRE.QPBT.outcomeEventWeight _root_.MIPStarRE.QPBT.msGame S (.var (_root_.MIPStarRE.QPBT.msConstraintVars i k)) (.constraint i)
(fun a b => _root_.MIPStarRE.QPBT.msBitOrZero a ≠ _root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintBitOrZero k b) (fun _ _ => inferInstance)
/-! ## Row and column parity products -/
/-- The real sign `(-1)^b` associated with a binary answer. -/
def bitSign (b : ZMod 2) : ℝ :=
(-1 : ℝ) ^ b.val
/-- The product of the three output signs, with malformed constraint answers
assigned zero so that they remain parity failures. -/
def constraintParityProduct : _root_.MIPStarRE.QPBT.MsAnswer → ℝ
| .triple β => ∏ k : Fin 3, _root_.MIPStarRE.QPBT.MagicSquareRigidity.bitSign (β k)
| .bit _ => 0
/-- Failure of the required sign product for one row or column constraint. -/
def ConstraintParityFailure (i : Fin 6) (a : _root_.MIPStarRE.QPBT.MsAnswer) : Prop :=
_root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintParityProduct a ≠ _root_.MIPStarRE.QPBT.MagicSquareRigidity.bitSign (_root_.MIPStarRE.QPBT.msParity i)
private noncomputable instance constraintParityFailureLeftDecidableRel (i : Fin 6) :
DecidableRel (fun a _ : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i a) :=
fun a _ => Classical.propDecidable (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i a)
private noncomputable instance constraintParityFailureRightDecidableRel (i : Fin 6) :
DecidableRel (fun _ b : _root_.MIPStarRE.QPBT.MsAnswer => _root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i b) :=
fun _ b => Classical.propDecidable (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i b)
/-- Equality of the real parity signs is classically decidable on the finite
Magic Square answer alphabet. -/
noncomputable instance constraintParityFailureDecidablePred (i : Fin 6) :
DecidablePred (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i) :=
fun a => Classical.propDecidable (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i a)
/-- Alice's local failure mass for the row or column sign product. -/
noncomputable def aliceParityFailureMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame) (i : Fin 6) : ℝ :=
@_root_.MIPStarRE.QPBT.aliceEventWeight _root_.MIPStarRE.QPBT.msGame S (.constraint i) (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i)
(_root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintParityFailureDecidablePred i)
/-- Bob's local failure mass for the row or column sign product. -/
noncomputable def bobParityFailureMass (S : _root_.MIPStarRE.QPBT.Strategy _root_.MIPStarRE.QPBT.msGame) (i : Fin 6) : ℝ :=
@_root_.MIPStarRE.QPBT.bobEventWeight _root_.MIPStarRE.QPBT.msGame S (.constraint i) (_root_.MIPStarRE.QPBT.MagicSquareRigidity.ConstraintParityFailure i)
(_root_.MIPStarRE.QPBT.MagicSquareRigidity.constraintParityFailureDecidablePred i)
end
end MIPStarRE.QPBT.MagicSquareRigidity
Source