Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Games / Defs

Definition
QPBT_QPBT_Games_Defs

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

qpbt

This bundle defines finite two-player one-round games, tensor-product strategies, projectivity, and Born probabilities. It supplies the rectangular tensor placement, state action, joint outcome weight, and Alice and Bob marginal weights used by the QPBT tests.

Principal definitions:

  • MIPStarRE.QPBT.Game: a finite two-player one-round game with question distribution and decision predicate.
  • MIPStarRE.QPBT.Measurement.IsProjective: projectivity of every measurement effect, using Measurement.
  • MIPStarRE.QPBT.Strategy: the tensor-product strategy for a two-player game.
  • MIPStarRE.QPBT.heteroKron: the rectangular tensor placement in strategy probabilities.
  • MIPStarRE.QPBT.applyOperatorToState: applies a finite matrix to a state vector.
  • MIPStarRE.QPBT.outcomeWeight: the joint Born weight of an answer pair.
  • MIPStarRE.QPBT.aliceOutcomeWeight: Alice's marginal answer weight.
  • MIPStarRE.QPBT.bobOutcomeWeight: Bob's marginal answer weight.

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/Defs.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_LIDT_MIPStarRE_Quantum_FiniteMatrix_Basic
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_LIDT_MIPStarRE_Quantum_Measurement

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

/-!
# Games, tensor-product strategies, and value

This file provides the finite game carrier used by the Pauli basis test.  Pure
states are vectors in `EuclideanSpace`, and POVMs use the project's matrix
`Measurement` structure.

## References

The source-facing nodes are blueprint `def:game`, `def:povm-conventions`,
`def:tensor-product-strategy`, and `def:tensor-product-value`.
The paper origin is `references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:10-57`.
-/

@[expose] public section

open scoped BigOperators Matrix ComplexOrder

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.Quantum

/--
A finite two-player one-round game with a probability distribution on question
pairs and a Boolean decision predicate.  This is blueprint
`def:game`, with paper origin
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:10-24`.
-/
structure Game where
  QuestionA : Type
  QuestionB : Type
  AnswerA : Type
  AnswerB : Type
  [questionAFintype : Fintype QuestionA]
  [questionBFintype : Fintype QuestionB]
  [answerAFintype : Fintype AnswerA]
  [answerBFintype : Fintype AnswerB]
  [questionADecidableEq : DecidableEq QuestionA]
  [questionBDecidableEq : DecidableEq QuestionB]
  [answerADecidableEq : DecidableEq AnswerA]
  [answerBDecidableEq : DecidableEq AnswerB]
  μ : _root_.LIDT.MIPStarRE.LDT.Distribution (QuestionA × QuestionB)
  μ_prob : μ.IsProbability
  decide : QuestionA → QuestionB → AnswerA → AnswerB → Bool

attribute [instance] _root_.MIPStarRE.QPBT.Game.questionAFintype _root_.MIPStarRE.QPBT.Game.questionBFintype
  _root_.MIPStarRE.QPBT.Game.answerAFintype _root_.MIPStarRE.QPBT.Game.answerBFintype _root_.MIPStarRE.QPBT.Game.questionADecidableEq
  _root_.MIPStarRE.QPBT.Game.questionBDecidableEq _root_.MIPStarRE.QPBT.Game.answerADecidableEq _root_.MIPStarRE.QPBT.Game.answerBDecidableEq





/-- Projectivity of every effect in a POVM (blueprint
`def:povm-conventions`; paper origin
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:68-72`). -/
def Measurement.IsProjective {α d : Type*} [Fintype α] [Fintype d] [DecidableEq d]
    (M : _root_.LIDT.MIPStarRE.Quantum.Measurement α d) : Prop :=
  ∀ a, _root_.LIDT.MIPStarRE.Quantum.IsProj (M.effect a)

/--
The tensor-product strategy of blueprint
`def:tensor-product-strategy` (paper origin
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:26-38`).
-/
structure Strategy (G : _root_.MIPStarRE.QPBT.Game) where
  ιA : Type
  ιB : Type
  [ιAFintype : Fintype ιA]
  [ιBFintype : Fintype ιB]
  [ιADecidableEq : DecidableEq ιA]
  [ιBDecidableEq : DecidableEq ιB]
  ψ : EuclideanSpace ℂ (ιA × ιB)
  ψ_norm : ‖ψ‖ = 1
  A : G.QuestionA → _root_.LIDT.MIPStarRE.Quantum.Measurement G.AnswerA ιA
  B : G.QuestionB → _root_.LIDT.MIPStarRE.Quantum.Measurement G.AnswerB ιB

attribute [instance] _root_.MIPStarRE.QPBT.Strategy.ιAFintype _root_.MIPStarRE.QPBT.Strategy.ιBFintype
  _root_.MIPStarRE.QPBT.Strategy.ιADecidableEq _root_.MIPStarRE.QPBT.Strategy.ιBDecidableEq

/-- The rectangular tensor placement used in strategy probabilities.  This is
the finite-matrix realization of blueprint
`def:tensor-product-strategy`; paper origin
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:26-38`.
-/
def heteroKron {ιA ιB : Type*} (A : _root_.LIDT.MIPStarRE.Quantum.Op ιA) (B : _root_.LIDT.MIPStarRE.Quantum.Op ιB) : _root_.LIDT.MIPStarRE.Quantum.Op (ιA × ιB) :=
  Matrix.kronecker A B

/-! ### Algebra of the tensor placement

The shared tensor-placement API.  These identities are used both by the perfect
Magic Square strategy (blueprint `thm:ms-from-ac`) and by the rigidity transfer
step (blueprint `thm:ms-rigidity`), so they live
with the definition rather than in either development. -/

/-- Formalization-only auxiliary lemma for `def:tensor-product-strategy`
(blueprint `def:tensor-product-strategy`, paper
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:26-38`): the tensor
placement is multiplicative, `(A ⊗ C) * (B ⊗ D) = (A * B) ⊗ (C * D)`. -/
theorem heteroKron_mul {ιA ιB : Type*} [Fintype ιA] [Fintype ιB]
    (A B : _root_.LIDT.MIPStarRE.Quantum.Op ιA) (C D : _root_.LIDT.MIPStarRE.Quantum.Op ιB) :
    _root_.MIPStarRE.QPBT.heteroKron A C * _root_.MIPStarRE.QPBT.heteroKron B D = _root_.MIPStarRE.QPBT.heteroKron (A * B) (C * D) := by
  unfold _root_.MIPStarRE.QPBT.heteroKron Matrix.kronecker
  exact (Matrix.mul_kronecker_mul A B C D).symm

/-- Formalization-only auxiliary lemma for `def:tensor-product-strategy`
(blueprint `def:tensor-product-strategy`): the tensor
placement of the two identity operators is the identity operator on the product
space. -/
theorem heteroKron_one_one {ιA ιB : Type*} [DecidableEq ιA] [DecidableEq ιB] :
    _root_.MIPStarRE.QPBT.heteroKron (1 : _root_.LIDT.MIPStarRE.Quantum.Op ιA) (1 : _root_.LIDT.MIPStarRE.Quantum.Op ιB) = 1 := by
  unfold _root_.MIPStarRE.QPBT.heteroKron Matrix.kronecker
  exact Matrix.one_kronecker_one

/-- Formalization-only auxiliary lemma for `def:tensor-product-strategy`
(blueprint `def:tensor-product-strategy`): tensor placement
respects negation in the left factor. -/
theorem heteroKron_neg_left {ιA ιB : Type*} (A : _root_.LIDT.MIPStarRE.Quantum.Op ιA) (C : _root_.LIDT.MIPStarRE.Quantum.Op ιB) :
    _root_.MIPStarRE.QPBT.heteroKron (-A) C = -_root_.MIPStarRE.QPBT.heteroKron A C := by
  ext p q
  simp [_root_.MIPStarRE.QPBT.heteroKron, Matrix.kronecker]

/-- Formalization-only auxiliary lemma for `def:tensor-product-strategy`
(blueprint `def:tensor-product-strategy`): tensor placement
respects negation in the right factor. -/
theorem heteroKron_neg_right {ιA ιB : Type*} (A : _root_.LIDT.MIPStarRE.Quantum.Op ιA) (C : _root_.LIDT.MIPStarRE.Quantum.Op ιB) :
    _root_.MIPStarRE.QPBT.heteroKron A (-C) = -_root_.MIPStarRE.QPBT.heteroKron A C := by
  ext p q
  simp [_root_.MIPStarRE.QPBT.heteroKron, Matrix.kronecker]













/- The Euclidean linear map is the shared action used by the value and distance
functionals.  Keeping it at the Euclidean-space level avoids accidentally
using the function-space supremum norm of `Matrix.mulVec`. -/
/-- Apply a finite matrix to a Euclidean-space state.  This is the Hilbert-space
action underlying `def:tensor-product-value`, paper
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:219-271`. -/
noncomputable def applyOperatorToState {ι : Type*} [Fintype ι] [DecidableEq ι]
    (M : _root_.LIDT.MIPStarRE.Quantum.Op ι) (ψ : EuclideanSpace ℂ ι) : EuclideanSpace ℂ ι :=
  Matrix.toEuclideanLin M ψ

/-- The Born weight of an answer pair for a strategy.  Lean-only support for
blueprint `def:tensor-product-value`, paper
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:40-48`. -/
noncomputable def outcomeWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (x : G.QuestionA) (y : G.QuestionB) (a : G.AnswerA) (b : G.AnswerB) : ℝ :=
  let M : _root_.LIDT.MIPStarRE.Quantum.Op (S.ιA × S.ιB) :=
    _root_.MIPStarRE.QPBT.heteroKron ((S.A x).effect a) ((S.B y).effect b)
  let acted := _root_.MIPStarRE.QPBT.applyOperatorToState M S.ψ
  (inner ℂ S.ψ acted).re

/-- Alice's marginal Born weight for an answer at a fixed question. -/
noncomputable def aliceOutcomeWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (x : G.QuestionA) (a : G.AnswerA) : ℝ :=
  let M : _root_.LIDT.MIPStarRE.Quantum.Op (S.ιA × S.ιB) :=
    _root_.MIPStarRE.QPBT.heteroKron ((S.A x).effect a) 1
  (inner ℂ S.ψ (_root_.MIPStarRE.QPBT.applyOperatorToState M S.ψ)).re

/-- Bob's marginal Born weight for an answer at a fixed question. -/
noncomputable def bobOutcomeWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (y : G.QuestionB) (b : G.AnswerB) : ℝ :=
  let M : _root_.LIDT.MIPStarRE.Quantum.Op (S.ιA × S.ιB) :=
    _root_.MIPStarRE.QPBT.heteroKron 1 ((S.B y).effect b)
  (inner ℂ S.ψ (_root_.MIPStarRE.QPBT.applyOperatorToState M S.ψ)).re

/-- The Born weight of a decidable event on the two answers at fixed questions. -/
noncomputable def outcomeEventWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (x : G.QuestionA) (y : G.QuestionB)
    (E : G.AnswerA → G.AnswerB → Prop) [DecidableRel E] : ℝ :=
  ∑ a : G.AnswerA, ∑ b : G.AnswerB,
    if E a b then _root_.MIPStarRE.QPBT.outcomeWeight S x y a b else 0

/-- The marginal Born weight of a decidable event on Alice's answer. -/
noncomputable def aliceEventWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (x : G.QuestionA) (E : G.AnswerA → Prop) [DecidablePred E] : ℝ :=
  ∑ a : G.AnswerA, if E a then _root_.MIPStarRE.QPBT.aliceOutcomeWeight S x a else 0

/-- The marginal Born weight of a decidable event on Bob's answer. -/
noncomputable def bobEventWeight {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G)
    (y : G.QuestionB) (E : G.AnswerB → Prop) [DecidablePred E] : ℝ :=
  ∑ b : G.AnswerB, if E b then _root_.MIPStarRE.QPBT.bobOutcomeWeight S y b else 0




















/--
The tensor-product value, expressed as the distribution average of the Born
probabilities.  This is blueprint
`def:tensor-product-value`, with paper origin
`references/qpbt-paper/06_nonlocal_games_and_mipstar.tex:40-57`.
-/
noncomputable def Strategy.value {G : _root_.MIPStarRE.QPBT.Game} (S : _root_.MIPStarRE.QPBT.Strategy G) : ℝ :=
  _root_.LIDT.MIPStarRE.LDT.avgOver G.μ (fun xy =>
    ∑ a : G.AnswerA, ∑ b : G.AnswerB,
      if G.decide xy.1 xy.2 a b then _root_.MIPStarRE.QPBT.outcomeWeight S xy.1 xy.2 a b else 0)






end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Games/Defs.lean#L30-L496

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