QPBT definitions: Games / Defs
DefinitionQPBT_QPBT_Games_Defsqpbt
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