QPBT definitions: Combining / DirectLowDegree / GameValue
DefinitionQPBT_QPBT_Combining_DirectLowDegree_GameValueqpbt
This bundle defines the branch and total rejection probabilities of the directly indexed low-degree game. It separates rejection for an ordered pair of question types from the uniformly averaged game value and the weighted low-individual-degree failure probability.
Principal definitions:
MIPStarRE.QPBT.directLdBranchRejectionProbability: defines rejection probability conditioned on an ordered pair of low-degree question types and averaged over the common direct sample.MIPStarRE.QPBT.directLdRejectionProbability: defines total rejection probability for the directly indexed low-degree game averaged over its ordered type branches.MIPStarRE.QPBT.directLdLdtWeightedFailureProbability: defines the branch failure probability with the weights used by the low-individual-degree test.
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/Combining/DirectLowDegree/GameValue.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_Combining_DirectLowDegree_Game
import Definitions.Def_QPBT_QPBT_Combining_DirectLowDegree_Geometry
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Mathlib
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# Rejection probabilities for the directly indexed low-degree game
This module compares the rejection probability of the directly indexed game
with the branch weights used by the low individual degree test.
All declarations below are formalization-only support derived from the game
value; none is a paper-labelled result.
## References
The uniform distribution on the three ordered question types is specified in
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:178-186`,
and its verifier is specified in the same file at lines 320-392. The three
equal outer weights of the low individual degree test and its uniform role
choices are specified in `references/ldt-paper/test_definition.tex:10-67`.
-/
@[expose] public section
open scoped BigOperators MatrixOrder Matrix ComplexOrder
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.Quantum
noncomputable section
/-- Rejection probability conditioned on an ordered pair of low-degree
question types, averaged over the common direct sample. -/
noncomputable def directLdBranchRejectionProbability
(D : _root_.MIPStarRE.QPBT.DirectLdParams) (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.directLdGame D))
(types : _root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType) : ℝ :=
_root_.LIDT.MIPStarRE.LDT.avgOver (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.DirectLdSpace D)) fun sample =>
∑ a : (_root_.MIPStarRE.QPBT.directLdGame D).AnswerA, ∑ b : (_root_.MIPStarRE.QPBT.directLdGame D).AnswerB,
if _root_.MIPStarRE.QPBT.directLdWinPredicate D
(types.1, _root_.MIPStarRE.QPBT.directLdMap D types.1 sample)
(types.2, _root_.MIPStarRE.QPBT.directLdMap D types.2 sample) a b then
0
else _root_.MIPStarRE.QPBT.outcomeWeight S
(types.1, _root_.MIPStarRE.QPBT.directLdMap D types.1 sample)
(types.2, _root_.MIPStarRE.QPBT.directLdMap D types.2 sample) a b
/-- Total rejection probability of the directly indexed low-degree game,
averaged uniformly over its nine ordered type branches. -/
noncomputable def directLdRejectionProbability
(D : _root_.MIPStarRE.QPBT.DirectLdParams) (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.directLdGame D)) : ℝ :=
_root_.LIDT.MIPStarRE.LDT.avgOver (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.LdType × _root_.MIPStarRE.QPBT.LdType))
(_root_.MIPStarRE.QPBT.directLdBranchRejectionProbability D S)
/-- The branch failure probability with the weights used by the low
individual degree test. -/
noncomputable def directLdLdtWeightedFailureProbability
(D : _root_.MIPStarRE.QPBT.DirectLdParams) (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.directLdGame D)) : ℝ :=
let B := _root_.MIPStarRE.QPBT.directLdBranchRejectionProbability D S
((B (.aline, .point) + B (.point, .aline)) / 2 +
B (.point, .point) +
(B (.dline, .point) + B (.point, .dline)) / 2) / 3
end
end MIPStarRE.QPBT
Source