Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / PauliBasisTest

Definition
QPBT_QPBT_Test_PauliBasisTest

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

qpbt

This bundle defines the fixed parameter and question carriers for the Pauli basis test. It packages admissible numerical parameters, scalar and register carriers, the six question families, and the Boolean-cube coefficient register.

Principal definitions:

  • MIPStarRE.QPBT.AdmissibleParams: defines the numerical admissible parameter tuple.
  • MIPStarRE.QPBT.AdmissibleParams.model: defines the scalar model associated with parameters.
  • MIPStarRE.QPBT.PauliScalar: defines the scalar carrier.
  • MIPStarRE.QPBT.PauliType: defines the Pauli-test question families.
  • MIPStarRE.QPBT.PauliIndex: defines the register blocks.
  • MIPStarRE.QPBT.PauliSpace: defines the ambient coefficient space.
  • MIPStarRE.QPBT.PauliRegister: defines the Boolean-cube coefficient register.

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/PauliBasisTest.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_Algebra_Coefficients
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_Lines
import Definitions.Def_QPBT_QPBT_Algebra_LowDegreeCode
import Definitions.Def_QPBT_QPBT_Algebra_Pauli
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Definitions.Def_QPBT_QPBT_Test_MagicSquare
import Mathlib
import Theorems.Thm_LIDT_MIPStarRE_LDT_Distribution_IsProbability_map

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

/-!
# The Pauli basis test

This file supplies the finite question and answer alphabets, the typed
conditionally-linear question sampler, and the Boolean win predicate for the
Pauli basis test.  The quantitative soundness theorem is isolated in
`Soundness.lean`.

## References

The source-facing nodes are blueprint `def:admissible`,
`def:pauli-question-distribution`, and `def:pauli-win-predicate`; their paper origin is
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:908-1225`.
-/

@[expose] public section

open scoped BigOperators

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.LDT

noncomputable section

/-- The numerical admissible Pauli-test parameter tuple.  Its scalar carrier
uses the once-and-for-all model `fixedFieldModel q hq`, so the paper's fixed
self-dual-normal identification is not quantified in the test statement.  This
is blueprint
`def:admissible`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:958-961`.
-/
structure AdmissibleParams where
  q : ℕ
  m : ℕ
  d : ℕ
  hd : 1 ≤ d
  hq : _root_.MIPStarRE.QPBT.IsAdmissibleSize q
  hdvd : m ∣ q

/-- Every admissible parameter tuple has positive ambient dimension. This
follows from positivity of the admissible field size and the divisibility
`P.m ∣ P.q` in `def:admissible`, blueprint
`blueprint/src/chapter/ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:958-961`.
-/
theorem AdmissibleParams.one_le_m (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : 1 ≤ P.m := by
  have hqpos : 0 < P.q := by
    rcases P.hq with ⟨k, _, hq⟩
    rw [hq]
    exact Nat.pow_pos (by decide)
  exact Nat.one_le_iff_ne_zero.mpr
    (ne_zero_of_dvd_ne_zero (Nat.ne_of_gt hqpos) P.hdvd)

/-- The fixed scalar model of an admissible parameter tuple.  It is a
compatibility view of the global `fixedFieldModel` selector, not an independently
quantified field representation.  This is the field representation of
`def:admissible`, blueprint `ch13_qpbt_test.tex`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:958-961`.
-/
@[reducible] noncomputable def AdmissibleParams.model
    (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : _root_.MIPStarRE.QPBT.FixedFieldModel P.q :=
  _root_.MIPStarRE.QPBT.fixedFieldModel P.q P.hq

/-- The low-degree parameter tuple determined by an admissible Pauli-test
tuple.  It is not an additional hypothesis of `thm:pauli`.  The low-degree
parameters are those of `def:ld-game`, blueprint
`blueprint/src/chapter/ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:958-961`.
-/
@[reducible] def AdmissibleParams.toLdParams (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : _root_.MIPStarRE.QPBT.LdParams where
  q := P.q
  m := P.m
  d := P.d
  k := 1
  hm := P.one_le_m
  hd := P.hd
  hk := by decide
  hq := P.hq
  hdvd := P.hdvd

/-- The scalar carrier associated with an admissible parameter tuple.  It is
the globally fixed field carrier selected by `AdmissibleParams.model` in
blueprint
`def:admissible`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:958-961`.
-/
abbrev PauliScalar (P : _root_.MIPStarRE.QPBT.AdmissibleParams) := P.model.K

/-- The six families of Pauli-test questions.  This is part of
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
inductive PauliType where
  | point (W : _root_.MIPStarRE.QPBT.PauliKind)
  | aline (W : _root_.MIPStarRE.QPBT.PauliKind)
  | dline (W : _root_.MIPStarRE.QPBT.PauliKind)
  | pauli (W : _root_.MIPStarRE.QPBT.PauliKind)
  | pairW (W : _root_.MIPStarRE.QPBT.PauliKind)
  | pair
  | ms (t : _root_.MIPStarRE.QPBT.MsType)
  deriving DecidableEq, Repr, Inhabited, Fintype

/-- The register blocks used by the Pauli question space.  These are the
coordinates displayed in blueprint
`def:pauli-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
abbrev PauliIndex (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :=
  (((((Fin P.m ⊕ Fin P.m) ⊕ Unit) ⊕ Fin P.m) ⊕ Unit) ⊕ Unit)

/-- The ambient Pauli question coefficient space (blueprint
`def:pauli-question-distribution`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`).
-/
abbrev PauliSpace (P : _root_.MIPStarRE.QPBT.AdmissibleParams) := _root_.MIPStarRE.QPBT.PauliIndex P → _root_.MIPStarRE.QPBT.PauliScalar P

/-- The coefficient register indexed by the Boolean cube in
blueprint `def:generalized-pauli`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:908-945`.
-/
abbrev PauliRegister (P : _root_.MIPStarRE.QPBT.AdmissibleParams) := _root_.MIPStarRE.QPBT.Cube P.m → _root_.MIPStarRE.QPBT.PauliScalar P

/- The nested sum is the fixed register order
`V_X ⊕ V_Z ⊕ V_I ⊕ V_V ⊕ V_{R_X} ⊕ V_{R_Z}` from the blueprint. -/
/-- The `V_X` block of an ambient Pauli vector (blueprint
`def:pauli-question-distribution`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`). -/
def pauliXBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P :=
  fun i => z (.inl (.inl (.inl (.inl (.inl i)))))

/-- The `V_Z` block of an ambient Pauli vector in blueprint
`def:pauli-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliZBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P :=
  fun i => z (.inl (.inl (.inl (.inl (.inr i)))))

/-- The scalar block `V_I` of an ambient Pauli vector in
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliScalarBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : _root_.MIPStarRE.QPBT.PauliScalar P :=
  z (.inl (.inl (.inl (.inr ()))))

/-- The direction block `V_V` of an ambient Pauli vector in
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliDirectionBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P :=
  fun i => z (.inl (.inl (.inr i)))

/-- The `r_X` scalar block in the Pauli question content from
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliRXBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : _root_.MIPStarRE.QPBT.PauliScalar P :=
  z (.inl (.inr ()))

/-- The `r_Z` scalar block in the Pauli question content from
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliRZBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : _root_.MIPStarRE.QPBT.PauliScalar P :=
  z (.inr ())

/-- Select the basis-dependent point block from a Pauli question content in
blueprint `def:pauli-question-distribution`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliPointBlock {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (W : _root_.MIPStarRE.QPBT.PauliKind) (z : _root_.MIPStarRE.QPBT.PauliSpace P) :
    Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P :=
  match W with
  | .X => _root_.MIPStarRE.QPBT.pauliXBlock z
  | .Z => _root_.MIPStarRE.QPBT.pauliZBlock z

/-- Read the low-degree register selected by a basis from an ambient Pauli
vector.  This is restriction to the basis-selected registers of
`def:pauli-question-distribution`, blueprint `ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliToLd (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind) (z : _root_.MIPStarRE.QPBT.PauliSpace P) :
    _root_.MIPStarRE.QPBT.LdSpace P.toLdParams :=
  fun i => match i with
  | .inl (.inl j) => _root_.MIPStarRE.QPBT.pauliPointBlock W z j
  | .inl (.inr _) => _root_.MIPStarRE.QPBT.pauliScalarBlock z
  | .inr j => _root_.MIPStarRE.QPBT.pauliDirectionBlock z j

/-- Embed a low-degree vector into the basis-selected Pauli blocks, clearing the
other basis and the two `r` registers.  This is extension into the
basis-selected registers of `def:pauli-question-distribution`, blueprint
`blueprint/src/chapter/ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def embedLd (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (u : _root_.MIPStarRE.QPBT.LdSpace P.toLdParams) : _root_.MIPStarRE.QPBT.PauliSpace P :=
  fun i => match i with
  | .inl (.inl (.inl (.inl (.inl j)))) =>
      match W with
      | .X => u (.inl (.inl j))
      | .Z => 0
  | .inl (.inl (.inl (.inl (.inr j)))) =>
      match W with
      | .X => 0
      | .Z => u (.inl (.inl j))
  | .inl (.inl (.inl (.inr _))) => u (.inl (.inr ()))
  | .inl (.inl (.inr j)) => u (.inr j)
  | .inl (.inr _) => 0
  | .inr _ => 0

/-- The type-4 projection retaining `V_X`, `V_Z`, `V_{R_X}`, and `V_{R_Z}` from
blueprint `def:pauli-question-distribution`, paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliSharedProjection {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (z : _root_.MIPStarRE.QPBT.PauliSpace P) : _root_.MIPStarRE.QPBT.PauliSpace P :=
  fun i => match i with
  | .inl (.inl (.inl (.inl (.inl j)))) => z (.inl (.inl (.inl (.inl (.inl j)))))
  | .inl (.inl (.inl (.inl (.inr j)))) => z (.inl (.inl (.inl (.inl (.inr j)))))
  | .inl (.inl (.inl (.inr _))) => 0
  | .inl (.inl (.inr _)) => 0
  | .inl (.inr _) => z (.inl (.inr ()))
  | .inr _ => z (.inr ())



/-- The conditionally linear map attached to each Pauli question type.  The
point and line maps are the corresponding
low-degree maps embedded in the selected basis block; Pair, Magic Square, and
Pair/W types use the shared projection; Pauli/W is the zero-level map.  This
is the direct finite-space form of blueprint
`def:pauli-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
noncomputable def pauliCL (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (t : _root_.MIPStarRE.QPBT.PauliType) :
    _root_.MIPStarRE.QPBT.PauliSpace P → _root_.MIPStarRE.QPBT.PauliSpace P :=
  match t with
  | .point W => fun z => _root_.MIPStarRE.QPBT.embedLd P W (_root_.MIPStarRE.QPBT.ldPointCL P.toLdParams (_root_.MIPStarRE.QPBT.pauliToLd P W z))
  | .aline W => fun z => _root_.MIPStarRE.QPBT.embedLd P W (_root_.MIPStarRE.QPBT.ldALineCL P.toLdParams (_root_.MIPStarRE.QPBT.pauliToLd P W z))
  | .dline W => fun z => _root_.MIPStarRE.QPBT.embedLd P W (_root_.MIPStarRE.QPBT.ldDLineCL P.toLdParams (_root_.MIPStarRE.QPBT.pauliToLd P W z))
  | .pauli _ => fun _ => 0
  | .pairW _ => _root_.MIPStarRE.QPBT.pauliSharedProjection
  | .pair => _root_.MIPStarRE.QPBT.pauliSharedProjection
  | .ms _ => _root_.MIPStarRE.QPBT.pauliSharedProjection

















/-- A finite edge set for the typed Pauli question graph.  The self-loops and
the displayed type-incidence families are the graph used by the sampler in
blueprint `def:pauli-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
def pauliEdges : Finset (Sym2 _root_.MIPStarRE.QPBT.PauliType) :=
  let loops := Finset.univ.image (fun t : _root_.MIPStarRE.QPBT.PauliType => Sym2.mk t t)
  let lineEdges :=
    (Finset.univ : Finset _root_.MIPStarRE.QPBT.PauliKind).image (fun W =>
      Sym2.mk (.point W) (.aline W)) ∪
      (Finset.univ : Finset _root_.MIPStarRE.QPBT.PauliKind).image (fun W =>
        Sym2.mk (.point W) (.dline W)) ∪
      (Finset.univ : Finset _root_.MIPStarRE.QPBT.PauliKind).image (fun W =>
        Sym2.mk (.point W) (.pauli W))
  let basisEdges :=
    (Finset.univ : Finset _root_.MIPStarRE.QPBT.PauliKind).image (fun W =>
      Sym2.mk (.point W) (.pairW W)) ∪
      ({Sym2.mk (.point .X) (.ms (.var ⟨0, by decide⟩)),
        Sym2.mk (.point .Z) (.ms (.var ⟨4, by decide⟩))} : Finset (Sym2 _root_.MIPStarRE.QPBT.PauliType))
  let pairEdges :=
    (Finset.univ : Finset _root_.MIPStarRE.QPBT.PauliKind).image (fun W =>
      Sym2.mk (.pairW W) .pair)
  let msEdges' :=
    (Finset.univ : Finset (_root_.MIPStarRE.QPBT.MsType × _root_.MIPStarRE.QPBT.MsType)).filter (fun xy =>
      Sym2.mk xy.1 xy.2 ∈ _root_.MIPStarRE.QPBT.msEdges) |>.image (fun xy =>
        Sym2.mk (.ms xy.1) (.ms xy.2))
  loops ∪ lineEdges ∪ basisEdges ∪ pairEdges ∪ msEdges'

/-- A Pauli question is a type together with a full ambient coefficient vector
(blueprint `def:pauli-question-distribution`; paper
origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`).
-/
abbrev PauliQuestion (P : _root_.MIPStarRE.QPBT.AdmissibleParams) := _root_.MIPStarRE.QPBT.PauliType × _root_.MIPStarRE.QPBT.PauliSpace P

/-- The Pauli question carrying no additional coefficient data, as in
blueprint `def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1006-1008`.
Its ambient coefficient vector is zero. -/
def pauliQuestion (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind) : _root_.MIPStarRE.QPBT.PauliQuestion P :=
  (.pauli W, 0)

/-- The ordered-edge subtype used by the Pauli question sampler.  This is
the finite carrier underlying `graphDistribution pauliEdges`, used to state
`def:pauli-question-distribution`, blueprint
`ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1120`.
-/
abbrev PauliEdge :=
  {e : _root_.MIPStarRE.QPBT.PauliType × _root_.MIPStarRE.QPBT.PauliType // Sym2.mk e.1 e.2 ∈ _root_.MIPStarRE.QPBT.pauliEdges}

/-- The Pauli graph has a loop, so its ordered-edge subtype is nonempty.  This
is a finite-carrier fact used only to instantiate the uniform source sampler
for `def:pauli-question-distribution`; the graph itself is the source-facing
object `pauliEdges` above (same blueprint and paper references).
-/
theorem pauliEdge_nonempty : Nonempty _root_.MIPStarRE.QPBT.PauliEdge := by
  refine ⟨⟨(.point .X, .point .X), ?_⟩⟩
  simp [_root_.MIPStarRE.QPBT.pauliEdges]



/-- The Pauli question distribution from blueprint
`def:pauli-question-distribution`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1070-1120`.
-/
noncomputable def pauliQuestionDistribution (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
    _root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.PauliQuestion P × _root_.MIPStarRE.QPBT.PauliQuestion P) :=
  by
    classical
    letI : Nonempty _root_.MIPStarRE.QPBT.PauliEdge := _root_.MIPStarRE.QPBT.pauliEdge_nonempty
    exact
      _root_.LIDT.MIPStarRE.LDT.Distribution.map
        (_root_.LIDT.MIPStarRE.LDT.uniformDistribution (_root_.MIPStarRE.QPBT.PauliEdge × _root_.MIPStarRE.QPBT.PauliSpace P))
        (fun s =>
          ((s.1.1.1, _root_.MIPStarRE.QPBT.pauliCL P s.1.1.1 s.2),
            (s.1.1.2, _root_.MIPStarRE.QPBT.pauliCL P s.1.1.2 s.2)))

/-- The finite answer alphabet for the Pauli basis test.  Its constructors are
the seven answer forms in blueprint `def:pauli-win-predicate`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
inductive PauliAnswer (P : _root_.MIPStarRE.QPBT.AdmissibleParams) where
  | value (a : _root_.MIPStarRE.QPBT.PauliScalar P)
  | alinePoly (a : Fin (P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P)
  | dlinePoly (a : Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P)
  | pairBits (a : ZMod 2 × ZMod 2)
  | bit (a : ZMod 2)
  | msTriple (a : Fin 3 → ZMod 2)
  | pauliOutcome (a : _root_.MIPStarRE.QPBT.PauliRegister P)
  deriving DecidableEq

/-- A formalization-only total relabeling from the global Pauli-test answer
alphabet to a Pauli register. It folds wrong-form answers into zero so that a
Pauli question yields a complete `PauliRegister`-indexed measurement. -/
def pauliAnswerOrZero {P : _root_.MIPStarRE.QPBT.AdmissibleParams} : _root_.MIPStarRE.QPBT.PauliAnswer P → _root_.MIPStarRE.QPBT.PauliRegister P
  | .pauliOutcome u => u
  | _ => 0

/-- A finite sum code used only to construct the `Fintype` instance for the
answer alphabet in blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
abbrev PauliAnswerCode (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :=
  _root_.MIPStarRE.QPBT.PauliScalar P ⊕
    ((Fin (P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P) ⊕
      ((Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P) ⊕
        ((ZMod 2 × ZMod 2) ⊕
          (ZMod 2 ⊕ ((Fin 3 → ZMod 2) ⊕ _root_.MIPStarRE.QPBT.PauliRegister P)))))

/-- The constructor-preserving finite-code equivalence for `PauliAnswer`.  It
is the finite encoding used to state `def:pauli-win-predicate`, blueprint
`ch13_qpbt_test.tex`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
noncomputable def pauliAnswerEquiv (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
    _root_.MIPStarRE.QPBT.PauliAnswer P ≃ _root_.MIPStarRE.QPBT.PauliAnswerCode P where
  toFun
    | .value a => .inl a
    | .alinePoly a => .inr (.inl a)
    | .dlinePoly a => .inr (.inr (.inl a))
    | .pairBits a => .inr (.inr (.inr (.inl a)))
    | .bit a => .inr (.inr (.inr (.inr (.inl a))))
    | .msTriple a => .inr (.inr (.inr (.inr (.inr (.inl a)))))
    | .pauliOutcome a => .inr (.inr (.inr (.inr (.inr (.inr a)))))
  invFun
    | .inl a => .value a
    | .inr (.inl a) => .alinePoly a
    | .inr (.inr (.inl a)) => .dlinePoly a
    | .inr (.inr (.inr (.inl a))) => .pairBits a
    | .inr (.inr (.inr (.inr (.inl a)))) => .bit a
    | .inr (.inr (.inr (.inr (.inr (.inl a))))) => .msTriple a
    | .inr (.inr (.inr (.inr (.inr (.inr a))))) => .pauliOutcome a
  left_inv := by
    intro x
    cases x <;> rfl
  right_inv := by
    intro x
    cases x with
    | inl a => rfl
    | inr x =>
        cases x with
        | inl a => rfl
        | inr x =>
            cases x with
            | inl a => rfl
            | inr x =>
                cases x with
                | inl a => rfl
                | inr x =>
                    cases x with
                    | inl a => rfl
                    | inr x =>
                        cases x with
                        | inl a => rfl
                        | inr a => rfl

noncomputable instance instFintypePauliAnswer (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : Fintype (_root_.MIPStarRE.QPBT.PauliAnswer P) :=
  Fintype.ofEquiv (_root_.MIPStarRE.QPBT.PauliAnswerCode P) (_root_.MIPStarRE.QPBT.pauliAnswerEquiv P).symm

instance instInhabitedPauliAnswer (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : Inhabited (_root_.MIPStarRE.QPBT.PauliAnswer P) :=
  ⟨.bit 0⟩

/-- The phase bit `γ(u_X,u_Z,r_X,r_Z)` from `eq:gamma-value`.  It uses the
fixed trace selected by `P.model`, as required by the paper's fixed
self-dual-normal representation.  Blueprint
`eq:gamma-value`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1198-1212`.
-/
noncomputable def gammaValue (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (uX uZ : Fin P.m → _root_.MIPStarRE.QPBT.PauliScalar P)
    (rX rZ : _root_.MIPStarRE.QPBT.PauliScalar P) : ZMod 2 :=
  _root_.MIPStarRE.QPBT.fixedBinTrace P.model
    (dotProduct (rX • _root_.MIPStarRE.QPBT.indicatorVec uX) (rZ • _root_.MIPStarRE.QPBT.indicatorVec uZ))

/-- The commutation bit attached to a full Pauli ambient question, from
`eq:gamma-value` in blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1198-1212`.
-/
noncomputable def pauliPairGamma (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (z : _root_.MIPStarRE.QPBT.PauliSpace P) : ZMod 2 :=
  _root_.MIPStarRE.QPBT.gammaValue P (_root_.MIPStarRE.QPBT.pauliXBlock z) (_root_.MIPStarRE.QPBT.pauliZBlock z)
    (_root_.MIPStarRE.QPBT.pauliRXBlock z) (_root_.MIPStarRE.QPBT.pauliRZBlock z)

/-- The answer constructor prescribed by each Pauli question type; this is the
well-formedness part of blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def validPauliAnswer {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (t : _root_.MIPStarRE.QPBT.PauliType) (a : _root_.MIPStarRE.QPBT.PauliAnswer P) : Bool :=
  match t, a with
  | .point _, .value _ => true
  | .aline _, .alinePoly _ => true
  | .dline _, .dlinePoly _ => true
  | .pauli _, .pauliOutcome _ => true
  | .pairW _, .bit _ => true
  | .pair, .pairBits _ => true
  | .ms (.constraint _), .msTriple _ => true
  | .ms (.var _), .bit _ => true
  | _, _ => false

/-- The axis-line versus point relation used by blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliAlinePointCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (line point : _root_.MIPStarRE.QPBT.PauliSpace P) (f : Fin (P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P)
    (a : _root_.MIPStarRE.QPBT.PauliScalar P) : Prop :=
  -- The universal form preserves the source's zero-direction convention.
  ∀ t : _root_.MIPStarRE.QPBT.PauliScalar P,
    _root_.MIPStarRE.QPBT.pauliPointBlock W point =
        _root_.MIPStarRE.QPBT.pauliPointBlock W line + t • _root_.MIPStarRE.QPBT.coordinateDirection
          (_root_.MIPStarRE.QPBT.chiIndex P.toLdParams (_root_.MIPStarRE.QPBT.pauliScalarBlock line)) →
      _root_.MIPStarRE.QPBT.evalCoefficient f t = a

/-- The diagonal-line versus point relation used by blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliDlinePointCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (line point : _root_.MIPStarRE.QPBT.PauliSpace P) (f : Fin (P.m * P.d + 1) → _root_.MIPStarRE.QPBT.PauliScalar P)
    (a : _root_.MIPStarRE.QPBT.PauliScalar P) : Prop :=
  ∀ t : _root_.MIPStarRE.QPBT.PauliScalar P,
    _root_.MIPStarRE.QPBT.pauliPointBlock W point = _root_.MIPStarRE.QPBT.pauliPointBlock W line +
        t • _root_.MIPStarRE.QPBT.pauliDirectionBlock line →
      _root_.MIPStarRE.QPBT.evalCoefficient f t = a

/-- The raw Pauli-versus-point consistency relation from blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliPointPauliCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (point : _root_.MIPStarRE.QPBT.PauliSpace P) (h : _root_.MIPStarRE.QPBT.PauliRegister P) (a : _root_.MIPStarRE.QPBT.PauliScalar P) : Prop :=
  _root_.MIPStarRE.QPBT.lowDegreeEnc h (_root_.MIPStarRE.QPBT.pauliPointBlock W point) = a

/-- The Pair/W consistency relation, including the one-sided gamma gate, from
blueprint `def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliPairCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (z : _root_.MIPStarRE.QPBT.PauliSpace P) (β : ZMod 2) (bits : ZMod 2 × ZMod 2) : Prop :=
  _root_.MIPStarRE.QPBT.pauliPairGamma P z ≠ 0 ∨
    (match W with
    | .X => bits.1 = β
    | .Z => bits.2 = β)

/-- The point/Pair/W trace consistency relation from blueprint
`def:pauli-win-predicate`, paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliPointPairCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (z : _root_.MIPStarRE.QPBT.PauliSpace P) (a : _root_.MIPStarRE.QPBT.PauliScalar P) (β : ZMod 2) : Prop :=
  _root_.MIPStarRE.QPBT.pauliPairGamma P z ≠ 0 ∨
    _root_.MIPStarRE.QPBT.fixedBinTrace P.model
      (a * (match W with
      | .X => _root_.MIPStarRE.QPBT.pauliRXBlock z
      | .Z => _root_.MIPStarRE.QPBT.pauliRZBlock z)) = β

/-- The Point/Variable consistency clause of `def:pauli-win-predicate`.
The check is gated by `gamma = 0` and only uses Variable 1 in the X basis or
Variable 5 in the Z basis.  Blueprint
`def:pauli-win-predicate`; paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
def pauliPointVariableCondition (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (W : _root_.MIPStarRE.QPBT.PauliKind)
    (z : _root_.MIPStarRE.QPBT.PauliSpace P) (j : Fin 9) (a : _root_.MIPStarRE.QPBT.PauliScalar P) (β : ZMod 2) : Prop :=
  _root_.MIPStarRE.QPBT.pauliPairGamma P z = 0 ∨
    (j = ⟨0, by decide⟩ ∧ W = .X ∧
        _root_.MIPStarRE.QPBT.fixedBinTrace P.model (a * _root_.MIPStarRE.QPBT.pauliRXBlock z) = β) ∨
    (j = ⟨4, by decide⟩ ∧ W = .Z ∧
        _root_.MIPStarRE.QPBT.fixedBinTrace P.model (a * _root_.MIPStarRE.QPBT.pauliRZBlock z) = β)

/-- The Pauli win predicate, with constructor-shape rejection.  This is
blueprint `def:pauli-win-predicate`,
paper origin `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1126-1225`.
-/
noncomputable def pauliWinPredicate (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
    _root_.MIPStarRE.QPBT.PauliQuestion P → _root_.MIPStarRE.QPBT.PauliQuestion P → _root_.MIPStarRE.QPBT.PauliAnswer P → _root_.MIPStarRE.QPBT.PauliAnswer P → Bool :=
  open Classical in
  fun (tA, xA) (tB, xB) a b =>
    if _root_.MIPStarRE.QPBT.validPauliAnswer tA a && _root_.MIPStarRE.QPBT.validPauliAnswer tB b then
      if tA = tB then
        decide (a = b)
      else
        match tA, tB, a, b with
      | .aline W, .point W', .alinePoly f, .value u =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliAlinePointCondition P W xA xB f u) else true
      | .point W, .aline W', .value u, .alinePoly f =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliAlinePointCondition P W xB xA f u) else true
      | .dline W, .point W', .dlinePoly f, .value u =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliDlinePointCondition P W xA xB f u) else true
      | .point W, .dline W', .value u, .dlinePoly f =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliDlinePointCondition P W xB xA f u) else true
      | .point W, .pauli W', .value u, .pauliOutcome h =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliPointPauliCondition P W xA h u) else true
      | .pauli W, .point W', .pauliOutcome h, .value u =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliPointPauliCondition P W xB h u) else true
      | .pairW W, .pair, .bit β, .pairBits bits =>
          decide (_root_.MIPStarRE.QPBT.pauliPairCondition P W xA β bits)
      | .pair, .pairW W, .pairBits bits, .bit β =>
          decide (_root_.MIPStarRE.QPBT.pauliPairCondition P W xB β bits)
      | .point W, .pairW W', .value u, .bit β =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliPointPairCondition P W xB u β) else true
      | .pairW W, .point W', .bit β, .value u =>
          if W = W' then decide (_root_.MIPStarRE.QPBT.pauliPointPairCondition P W xA u β) else true
      | .ms (.constraint i), .ms (.var j), .msTriple β, .bit γ =>
          if ∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j then
            decide (_root_.MIPStarRE.QPBT.pauliPairGamma P xA = 0 ∨
              _root_.MIPStarRE.QPBT.msWinPredicate (.constraint i) (.var j) (.triple β) (.bit γ))
          else true
      | .ms (.var j), .ms (.constraint i), .bit γ, .msTriple β =>
          if ∃ k : Fin 3, _root_.MIPStarRE.QPBT.msConstraintVars i k = j then
            decide (_root_.MIPStarRE.QPBT.pauliPairGamma P xB = 0 ∨
              _root_.MIPStarRE.QPBT.msWinPredicate (.var j) (.constraint i) (.bit γ) (.triple β))
          else true
      | .point W, .ms (.var j), .value u, .bit β =>
          decide (_root_.MIPStarRE.QPBT.pauliPointVariableCondition P W xB j u β)
      | .ms (.var j), .point W, .bit β, .value u =>
          decide (_root_.MIPStarRE.QPBT.pauliPointVariableCondition P W xA j u β)
        | _, _, _, _ => true
    else false

/-- The Pauli basis test determined by the question distribution
`pauliQuestionDistribution` and the win predicate `pauliWinPredicate`.  These
are `def:pauli-question-distribution` and `def:pauli-win-predicate` in
`blueprint/src/chapter/ch13_qpbt_test.tex`, with paper origin
`references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:964-1225`.
-/
@[reducible] noncomputable def pauliBasisTest (P : _root_.MIPStarRE.QPBT.AdmissibleParams) : _root_.MIPStarRE.QPBT.Game where
  QuestionA := _root_.MIPStarRE.QPBT.PauliQuestion P
  QuestionB := _root_.MIPStarRE.QPBT.PauliQuestion P
  AnswerA := _root_.MIPStarRE.QPBT.PauliAnswer P
  AnswerB := _root_.MIPStarRE.QPBT.PauliAnswer P
  μ := _root_.MIPStarRE.QPBT.pauliQuestionDistribution P
  μ_prob := by
    classical
    letI : Nonempty _root_.MIPStarRE.QPBT.PauliEdge := _root_.MIPStarRE.QPBT.pauliEdge_nonempty
    exact _root_.LIDT.MIPStarRE.LDT.Distribution.IsProbability.map
      (_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability (_root_.MIPStarRE.QPBT.PauliEdge × _root_.MIPStarRE.QPBT.PauliSpace P)) _
  decide := _root_.MIPStarRE.QPBT.pauliWinPredicate P

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/PauliBasisTest.lean#L34-L754

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