QPBT definitions: Test / PauliBasisTest
DefinitionQPBT_QPBT_Test_PauliBasisTestqpbt
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