QPBT definitions: Observables / LineDefs
DefinitionQPBT_QPBT_Observables_LineDefsqpbt
This bundle gives the data structures for canonical axis and diagonal lines used by the low-degree question sampler. A line description stores its presentation kind, seed, base, direction, and represented point set, together with bounded-degree coefficient-list polynomials.
Principal definitions:
MIPStarRE.QPBT.LineKind: the axis and diagonal presentations of a line.MIPStarRE.QPBT.LineDesc: a seed-bearing canonical line description.MIPStarRE.QPBT.LineDesc.seed: the seed stored by a line description.MIPStarRE.QPBT.LineDesc.base: the canonical base point stored by a line description.MIPStarRE.QPBT.LineDesc.direction: the geometric direction represented by a line description.MIPStarRE.QPBT.DegPoly: a coefficient-list bounded-degree polynomial representation.
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/Observables/LineDefs.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_Subspaces
import Definitions.Def_QPBT_QPBT_Games_CondLinear
import Definitions.Def_QPBT_QPBT_Games_DistributionAux
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGame
import Mathlib
import Theorems.Thm_LIDT_MIPStarRE_LDT_Distribution_IsProbability_map
namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.LDT.Preliminaries
end LIDT.MIPStarRE.LDT.Preliminaries
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
/-!
# Lines, bounded line polynomials, and line-point distributions
This file provides the seed-bearing line descriptions and coefficient-list
polynomials shared by the observable and combining chapters. It also realizes
the line-point distribution directly from the conditionally linear sampler.
Over a finite coefficient field, bounded individual-degree multivariate
polynomials form a finite outcome set for the associated measurements.
## References
The line and bounded-polynomial definitions are blueprint
`def:ideg-deg-polynomials`, with source origin
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:51-58`. The
line-point sampler is `def:line-point-dist` in blueprint chapter 13, from
`08_classical_and_quantum_low_degree_tests.tex:274-287`.
-/
@[expose] public section
open scoped BigOperators
namespace MIPStarRE.QPBT
open LIDT.MIPStarRE.LDT
open LIDT.MIPStarRE.LDT.Preliminaries
noncomputable section
/-- A formalization-only identity used to construct canonical line
descriptions: applying the canonical line-representative projection twice has
the same effect as applying it once. -/
theorem lineRepMap_apply_self {K : Type*} [Field K] {m : ℕ}
(v u : Fin m → K) :
_root_.MIPStarRE.QPBT.lineRepMap v (_root_.MIPStarRE.QPBT.lineRepMap v u) = _root_.MIPStarRE.QPBT.lineRepMap v u := by
simp [_root_.MIPStarRE.QPBT.lineRepMap, _root_.MIPStarRE.QPBT.canonicalProjOfKernel, LinearMap.comp_apply]
/-- The two presentations of lines used by the low-degree question sampler. -/
inductive LineKind where
| axis
| diagonal
deriving DecidableEq
instance LineKind.instFintype : Fintype _root_.MIPStarRE.QPBT.LineKind :=
⟨{.axis, .diagonal}, by intro x; cases x <;> simp⟩
/-- A seed-bearing line description for blueprint
`def:line-point-dist`, paper
`08_classical_and_quantum_low_degree_tests.tex:143-174,243-287`.
An axis description stores its canonical base and seed. A diagonal description
stores only the projected direction, together with its prefix-zero invariant.
Both cases carry the assertion that their base is fixed by the
appropriate `lineRepMap`. Coordinates are numbered from zero; coordinate `j`
corresponds to the paper's coordinate `j + 1`. -/
inductive LineDesc (L : _root_.MIPStarRE.QPBT.LdParams) where
| axis (base : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (seed : _root_.MIPStarRE.QPBT.ScalarQ L)
(baseFixed : _root_.MIPStarRE.QPBT.lineRepMap (_root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L seed)) base = base)
| diagonal (base : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (seed : _root_.MIPStarRE.QPBT.ScalarQ L)
(direction : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)
(baseFixed : _root_.MIPStarRE.QPBT.lineRepMap direction base = base)
(prefixZero : ∀ j : Fin L.m, j.val < (_root_.MIPStarRE.QPBT.chiIndex L seed).val → direction j = 0)
deriving DecidableEq
/-- The tag of a canonical line description. -/
def LineDesc.kind {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → _root_.MIPStarRE.QPBT.LineKind
| .axis _ _ _ => .axis
| .diagonal _ _ _ _ _ => .diagonal
/-- The seed retained by a canonical line description. -/
def LineDesc.seed {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → _root_.MIPStarRE.QPBT.ScalarQ L
| .axis _ seed _ => seed
| .diagonal _ seed _ _ _ => seed
/-- The canonical base stored by a line description. -/
def LineDesc.base {L : _root_.MIPStarRE.QPBT.LdParams} : _root_.MIPStarRE.QPBT.LineDesc L → Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L
| .axis base _ _ => base
| .diagonal base _ _ _ _ => base
/-- The geometric direction represented by a canonical line description.
Diagonal descriptions already store the projected data, so this map does
not apply a second projection. -/
def LineDesc.direction {L : _root_.MIPStarRE.QPBT.LdParams} (line : _root_.MIPStarRE.QPBT.LineDesc L) :
Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L :=
match line with
| .axis _ seed _ => _root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L seed)
| .diagonal _ _ direction _ _ => direction
/-- The point set represented by a seed-bearing line description. -/
noncomputable def LineDesc.pointSet {L : _root_.MIPStarRE.QPBT.LdParams} (line : _root_.MIPStarRE.QPBT.LineDesc L) :
Set (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) :=
_root_.MIPStarRE.QPBT.linePoints line.base line.direction
/-- Coefficient-list representation of a univariate polynomial of degree at
most `c` over the scalar field of `L`. -/
abbrev DegPoly (L : _root_.MIPStarRE.QPBT.LdParams) (c : ℕ) := Fin (c + 1) → _root_.MIPStarRE.QPBT.ScalarQ L
/-- Extend a coefficient list by zero from degree bound `c` to `c'`. -/
def DegPoly.padTo {L : _root_.MIPStarRE.QPBT.LdParams} {c c' : ℕ} (_h : c ≤ c')
(f : _root_.MIPStarRE.QPBT.DegPoly L c) : _root_.MIPStarRE.QPBT.DegPoly L c' :=
fun i =>
if hi : i.val < c + 1 then f ⟨i.val, hi⟩ else 0
/-- A line polynomial evaluates to `a` at `u` when `u` has a line parameter
and every such parameter gives the same value. The universal clause handles
the zero-direction presentation without choosing a sentinel parameter. -/
def EvaluatesTo {L : _root_.MIPStarRE.QPBT.LdParams} {c : ℕ} (line : _root_.MIPStarRE.QPBT.LineDesc L)
(f : _root_.MIPStarRE.QPBT.DegPoly L c) (u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (a : _root_.MIPStarRE.QPBT.ScalarQ L) : Prop :=
(∃ t : _root_.MIPStarRE.QPBT.ScalarQ L, u = line.base + t • line.direction) ∧
∀ t : _root_.MIPStarRE.QPBT.ScalarQ L, u = line.base + t • line.direction → _root_.MIPStarRE.QPBT.evalCoefficient f t = a
/-- Partially evaluate a line polynomial at a point. The value is undefined
when the point does not determine an evaluation. This formalization-only
completion is used in blueprint chapter 14; the displayed family at paper
`14_analysis_of_the_pauli_basis_test.tex:197-206` has no bottom outcome. -/
noncomputable def evalOpt {L : _root_.MIPStarRE.QPBT.LdParams} {c : ℕ} (line : _root_.MIPStarRE.QPBT.LineDesc L)
(u : Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L) (f : _root_.MIPStarRE.QPBT.DegPoly L c) : Option (_root_.MIPStarRE.QPBT.ScalarQ L) := by
classical
exact if h : ∃ a : _root_.MIPStarRE.QPBT.ScalarQ L, _root_.MIPStarRE.QPBT.EvaluatesTo line f u a then
some (Classical.choose h)
else none
/-- Convert an axis-line CL output to its seed-bearing presentation; paper
`08_classical_and_quantum_low_degree_tests.tex:243-257,276-287`. -/
def aLineDescOf (L : _root_.MIPStarRE.QPBT.LdParams) (line : _root_.MIPStarRE.QPBT.LdSpace L) : _root_.MIPStarRE.QPBT.LineDesc L :=
let direction := _root_.MIPStarRE.QPBT.coordinateDirection (_root_.MIPStarRE.QPBT.chiIndex L line.seed)
let base := _root_.MIPStarRE.QPBT.lineRepMap direction line.point
_root_.MIPStarRE.QPBT.LineDesc.axis base line.seed (_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction line.point)
/-- Convert a diagonal-line CL output to its seed-bearing presentation; paper
`08_classical_and_quantum_low_degree_tests.tex:261-287`. -/
def dLineDescOf (L : _root_.MIPStarRE.QPBT.LdParams) (line : _root_.MIPStarRE.QPBT.LdSpace L) : _root_.MIPStarRE.QPBT.LineDesc L :=
let direction := _root_.MIPStarRE.QPBT.prefixProjection (_root_.MIPStarRE.QPBT.chiIndex L line.seed) line.direction
let base := _root_.MIPStarRE.QPBT.lineRepMap direction line.point
_root_.MIPStarRE.QPBT.LineDesc.diagonal base line.seed direction
(_root_.MIPStarRE.QPBT.lineRepMap_apply_self direction line.point) (by
intro j hj
change _root_.MIPStarRE.QPBT.prefixProjection (_root_.MIPStarRE.QPBT.chiIndex L line.seed) line.direction j = 0
rw [_root_.MIPStarRE.QPBT.prefixProjection, if_pos hj])
/-- The axis-line/point component of the low-degree line-point sampler; paper
`08_classical_and_quantum_low_degree_tests.tex:243-257,274-287`. -/
noncomputable def aLinePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
(_root_.MIPStarRE.QPBT.clDistribution (_root_.MIPStarRE.QPBT.ldALineCL L) (_root_.MIPStarRE.QPBT.ldPointCL L)).map fun sample =>
(_root_.MIPStarRE.QPBT.aLineDescOf L sample.1, _root_.MIPStarRE.QPBT.LdSpace.point sample.2)
/-- The diagonal-line/point component of the low-degree line-point sampler; paper
`08_classical_and_quantum_low_degree_tests.tex:261-287`. -/
noncomputable def dLinePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
(_root_.MIPStarRE.QPBT.clDistribution (_root_.MIPStarRE.QPBT.ldDLineCL L) (_root_.MIPStarRE.QPBT.ldPointCL L)).map fun sample =>
(_root_.MIPStarRE.QPBT.dLineDescOf L sample.1, _root_.MIPStarRE.QPBT.LdSpace.point sample.2)
/-- The equal mixture of axis and diagonal line-point samples from
`def:line-point-dist`; paper
`08_classical_and_quantum_low_degree_tests.tex:274-287`. -/
noncomputable def linePointDist (L : _root_.MIPStarRE.QPBT.LdParams) :
_root_.LIDT.MIPStarRE.LDT.Distribution (_root_.MIPStarRE.QPBT.LineDesc L × (Fin L.m → _root_.MIPStarRE.QPBT.ScalarQ L)) :=
_root_.MIPStarRE.QPBT.Distribution.mix (1 / 2) (by norm_num) (by norm_num)
(_root_.MIPStarRE.QPBT.aLinePointDist L) (_root_.MIPStarRE.QPBT.dLinePointDist L)
/-- The affine line-point component has total probability one. -/
theorem aLinePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
(_root_.MIPStarRE.QPBT.aLinePointDist L).IsProbability :=
((_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability _).map _).map _
/-- The diagonal line-point component has total probability one. -/
theorem dLinePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
(_root_.MIPStarRE.QPBT.dLinePointDist L).IsProbability :=
((_root_.LIDT.MIPStarRE.LDT.uniformDistribution_isProbability _).map _).map _
/-- The line-point mixture has total probability one. -/
theorem linePointDist_isProbability (L : _root_.MIPStarRE.QPBT.LdParams) :
(_root_.MIPStarRE.QPBT.linePointDist L).IsProbability := by
exact _root_.MIPStarRE.QPBT.Distribution.mix_isProbability _ _ _
(_root_.MIPStarRE.QPBT.aLinePointDist_isProbability L) (_root_.MIPStarRE.QPBT.dLinePointDist_isProbability L)
(by norm_num) (by norm_num)
end
end MIPStarRE.QPBT
Source